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

> поиск пути для кубика, в матрице nxn
Тёмный Эльф
сообщение 24.11.2007 17:45
Сообщение #1


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

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

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


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

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

Может, существует общий алгоритм нахождения этого пути?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Rian
сообщение 26.11.2007 16:17
Сообщение #2


Знаток
****

Группа: Пользователи
Сообщений: 394
Пол: Мужской

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


А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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


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

 



- Текстовая версия 22.06.2025 1:13
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"