IPB
ЛогинПароль:

> поиск пути для кубика, в матрице nxn
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной).
В самом начале пути эта запрещенная сторона находится сверху.

Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю!

Может, существует общий алгоритм нахождения этого пути?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Тёмный Эльф   поиск пути для кубика   24.11.2007 21:45
xds   Решение "в лоб" - катать по всякому куби…   24.11.2007 22:33
Тёмный Эльф   Решение "в лоб" - катать по всякому куб…   24.11.2007 22:41
Lapp   Да, я думала над этим. Но, по-моему, это будет вып…   25.11.2007 17:49
hardcase   Решение "в лоб" - катать по всякому куб…   25.11.2007 18:35
Lapp   Только сейчас обратил внимание, что тема абсолютно…   25.11.2007 18:23
xds   Для n > 9 уже довольно долго. Добавлено через …   25.11.2007 19:21
hardcase   Написал программу. Правда, на С# (паскаля нету на …   25.11.2007 21:09
xds   Для 8x8 и 9x9 тоже. 10x10 лень дожидаться :)   25.11.2007 21:41
Тёмный Эльф   :yes2: дольше чем полчаса.. (здесь то и встает в…   25.11.2007 23:21
Lapp   думается мне, что задача при n>3 не имеет решен…   26.11.2007 9:19
xds   AMD Duron @ 800 MHz: n = 8 - 1,43 с; n = 9 - 18,84…   26.11.2007 11:58
hardcase   Ставлю свою софтину (C# .NET 2.0, без распараллели…   26.11.2007 17:25
Lapp   После чистки очевидных несуразностей на компе Athl…   26.11.2007 19:50
feniks25   А можно исходники посмотреть. Уж больно интересно-…   26.11.2007 20:17
hardcase   А можно исходники посмотреть. Уж больно интересно…   26.11.2007 23:09
xds   После чистки очевидных несуразностей на компе Ath…   26.11.2007 21:01
hardcase   Как то даже незаметно закончился расчет "в ло…   27.11.2007 1:18
Тёмный Эльф   Времени ушло 7ч 25м. Вот это да-а-а :mega_chok: З…   27.11.2007 1:29
hardcase   Судя по ответам xds'а, его программа справится…   27.11.2007 1:47
Тёмный Эльф   Программа, откомпилированная на Microsoft Visual S…   27.11.2007 2:39
hardcase   Программа, откомпилированная на Microsoft Visual …   27.11.2007 3:11
Тёмный Эльф   Это какая такая программа?? Это программа xds. В…   27.11.2007 3:35
xds   Вот мой оригинальный вариант (BP 7.0), только доба…   27.11.2007 11:00
spill   Есть поиск в ширину: 1. Первую клетку пометить чис…   14.03.2008 17:44


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.10.2020 1:56
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name