Новая тема

Вы не можете создавать новые темы.
Т.к. вы неавторизованы на сайте. Пожалуйста назовите себя или зарегистрируйтесь.

Список тем

Алгоритм (Перестановка) как?

С друзьями на NN.RU

У вас пока нет друзей на NN.RU, поэтому ссылка на тему не может быть отправлена.

Воспользуйтесь поиском, чтобы найти новых друзей.

В социальных сетях

Idol

11.05.2004

Господа!!!

Вот требуется мне сделать такую вещь:
реализовать перестановку чисел от 1 до 16 в квадрате 4x4 ... причем так .. что-бы получить все возможные варианты ...

Хотелось-бы сделать через несколько циклов ... вот ... думаю как ...
может кто может предложить оптимальный по скорости вариант???

P.S. реализация будет на ASM`е ... -> хочется получить протую и быструю реализаию ...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity_блин_с_проблеммами_с_ником

12.05.2004

Ну, не знаю как на асме, но общий алгоритм мне видится таким.
1. Создаешь массив из 16 ячеек (Массив_16), куда вписываешь числа из квадрата, по очереди. Т.е. если квадрат
1,2,3,4
2,3,4,5
3,4,5,6
4,5,6,7
то Массив_16 будет 1,2,3,4,2,3,4,5,3... и т.д.
2. Далее пишешь в зависимости от желания и реализации одну или 14 конструкций, назовем ее "цикл с исключениями", которая работает как обычный цикл от 1(0) до 16(15), но при переборе чисел исключает из списка указанные в качестве дополнительных аргументов. Я буду писать ее как Цикл_С_Исключениями_1-16(переменная, Исключения = a,b,c...)
3. Алгоритм соответственно будет такой
Цикл_1-16(a)
..Цикл_С_Исключениями_1-16(b,Исключения = a)
....Цикл_С_Исключениями_1-16(c,Исключения = a,b)
......Цикл_С_Исключениями_1-16(d,Исключения = a,b,c)
... и.т.д.
.............Цикл_С_Исключениями_1-16(o,Исключения = a,b,c,d,e,f,g,h,i,j,k,l,m,n)
.............Твой обработчик.
3. В момент вызова твоего обработчика нужный тебе квадрат будет выглядеть так:
Массив_16[a],Массив_16,Массив_16[c],Массив_16[d],
Массив_16[e],Массив_16[f],Массив_16[g],Массив_16[h],
ну и т.д.

Это красивый вариант :)
Есть еще простой. П.1 оставляешь. Далее пишешь конструкцию
for(a=1,a<17,a=a+1)
..for(b=1,b<17,b=b+1)
....for(c=1,c<17,c=c+1)
........
..........for(o=1,o<17,o=o+1)
Далее если среди переменных a-o нет ни одной пары с одинаковыми значениями выполняешь свой обработчик (см п.3), если есть - просто делаешь следующую итерацию.

Это вариант современный.

Теперь по производительности. В варианте 1 нужно будет сделать 16! итераций, а в варианте 2 - 16^16 и это только по циклам. Так что реализуемость этой затеи вызывает у меня определенные сомнения.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

Чего-то как-то больно геморойно ....
ведь наверняка есть иной способ ....
вот например ... по предложенному тобой ... делаем упрощение:
(по варианту 1.)

заполняем массив
__Цикл от 1 до 16 (по K)
запонимаем массив
__Цикл от 1 до 16 (по Z) ...
делаем увелечение всех значений ячеек кроме Z`ой ...
послед. ячейку (которая получит номер 17) ставим на место первой (т.е.) сдвигаем массив ...
--
востанавливаем запомненный массив в первом цикле
--

Думаю подобный метод тоже переберет все возможные варианты ...
-> скорость перебора составляет:
16^16 вариантов...

только плгоритм покрасивее ... ;))

Но вот только ...
как бы приблизится к 16! вариантов перебора ... и при этом с не большим алгоритмом ...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

Мда ...
правильнее вот что:

(опечатка вышла)
делаем увелечение всех значений ячеек кроме K`ой ...
послед. ячейку (которая получит номер 17) ставим на место первой (т.е.) сдвигаем массив .

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

nykt

12.05.2004

На ум приходит вычисление n! рекурсией... Может здесь имеет смысл покопать?!

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity original

12.05.2004

Да я тут репу почесал, и решил, что первый вариант только выглядит страшно, а на самом деле реализуется довольно быстро (хотя конечно целиком в асме я бы делать не стал), так что если нужно для _дела_, то вполне выполнимо (в том же асме насколько я понимаю у тебя цикл с исключениями будет отличаться от обычного цикла на один условный переход и передачу параметров). А если лабу какую сдать - подавай второй вариант и шли всех недовольных в пешее эротическое.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

Ды тут не лаба ... тут для дела хитрого ...

но намеки понял ...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

trinity original

12.05.2004

Ну на тогда еще намек :)
К циклу с исключениями прилагаешь массивчик из 16 байт, заполненный нулями. При передаче исключений соответствующие ячейки заполняешь единицами. А в цикле ставишь условный переход если ячейка с адресом адрес_массива + текущий счетчик не равна нулю.
Причем эту идею наверное можно расширить на матрицу 16х16 (раз уж ты красоту алгоритма ищешь), но на это ВМКшное образование требуется, а у меня его нет :)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Сейчас читают

Тема Просмотров

Фиалка Ness orange pekoe 2200

Перелом руки и отдых на море 2015

Проверка газового оборудования в доме. 5005

Домик на море. Спорные моменты. 245

Виноград арочный, на вино, на беседку, на еду и компоты, саженцы этого года! 5920

Подработка/стажировка летом для подростка - где? 3706

Мимо иду

12.05.2004

Посмотрим на задачу с другой стороны:
Каждая из 16 ячеек квадрата может принимать значения от 1 до 16 ( а может лучше от 0 до 15, т.е. от 0x00 до 0x0F), т.е. может быть закодирована в полубайт. Из этой маааленькой перемены в постановке задачи видно, что искомый перебор - это все возможные значения 64-битного целого числа кроме чисел с повторяющимися полубайтами. Такая постановка задачи больше подходит для ассемблерной реализации ;)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

Это конечно да ...
но стоит учитывать то что:
размер 4x4 задан условно ... и теоретически должен просто и без смены алгоритма расширяться ...

именно по этому я и ищу алгоритм понятный и простой!

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Мимо иду

12.05.2004

Пардоньте,
но ежели больше, чем 4х4, тогда и в каждой ячейке уже не от 1 до 16? Ни один из предложенных здесь алгоритмов на это не способен.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity original

12.05.2004

Все способны, просто не надо путать алгоритмы и реализации, с помощью которых алгоритмы описаны.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity original

12.05.2004

Так ведь и фокус в том, что перебирать 2^64 чисел и искать у них одинаковые полубайты хлопотно и долго. :)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity original

12.05.2004

Так ведь и фокус в том, что перебирать 2^64 чисел и искать у них одинаковые полубайты хлопотно и долго. :)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

А то ... очень долго ....

-> ASM ...

и по этому ищу самую быструю реализацию ...

посмотрите пред. мой метод .. вверху ...
он позволяет получать варианты для любых значений (размерностей квадрата).

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Trinity original

12.05.2004

1. Хм... а я че то и не заметил, что у тебя действительно значения ограничены, тогда п.1 не нужен.
2. Нифига я не понял в твоем алгоритме :) зачем сдвигать? откуда 17ая ячейка появляется? чем цикл по K отличается от цикла по Z?

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

12.05.2004

;)
17ое значение появится за счет increment`а значений
("делаем увелечение всех значений ячеек кроме K`ой")

Общими словами:
берем одну клетку (значение) ... и переставляем все другие по циклы ...
потом берем следующее значние .. и переставляем все элементы далее ...
итд ...

пока не пройдем по всем значениям

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

13.05.2004

Гыы ....
у народа идеи кончилися ... ;)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Idol

17.05.2004

Народ ...

а я тут разродился идеей ... и даже реализовал ... на asm`е ...

прога весит 259 байтов .. ;))

Могу исх. код выдать .. еоли кому надо ...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Новая тема

Список тем

Последние темы форумов

Форум Тема (Автор) Последний ответ Ответов

Техно-форум Полировка крышки винилового проигрывателя - Уступите парню лыжню 17.06.2025 в 10:48:34 7

Объявления на НН.РУ - Техника

Добавить объявление

Принтер лазерный HEWLETT PACKARD HP-6L

Принтер лазерный HEWLETT PACKARD HP-6L Отправка в регионы после оплаты. 3штуки БУ. Внешний вид из магазина простояли на складе...
Цена: 4 500 руб.

Оперативная память Corsair XMS3 CMX8GX3M2A1600C9

Оперативная память Corsair XMS3 CMX8GX3M2A1600C9 Отправка в регионы после оплаты. Продаются сразу обе. Цена за обе 2000 руб....
Цена: 1 000 руб.

Сетевой фильтр APC Surge Arrest

Сетевой фильтр APC Surge Arrest для радиолюбителя.и не только Отправка в регионы после оплаты. ЦЕНА 3000 руб. В рабочем состоянии....
Цена: 3 000 руб.

Материнские платы на запчасти и не только

Материнские платы на запчасти и не только Материнские платы и другие комплектующие Отправка в регионы после оплаты. Транспортной...
Цена: 3 000 руб.