 поиск пути для кубика, в матрице nxn |
| Тёмный Эльф |
  24.11.2007 17:45
Сообщение
#1
|
 Влюблённый псих  Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация:  1   |
Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной). В самом начале пути эта запрещенная сторона находится сверху. Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю! Может, существует общий алгоритм нахождения этого пути? |
   |
 
|
  |
Ответов
| hardcase |
26.11.2007 21:47
Сообщение
#2
|
 code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Судя по ответам xds'а, его программа справится с задачей часа за 3.
-------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
|
|
|
| Тёмный Эльф |
26.11.2007 22:39
Сообщение
#3
|
|
Влюблённый псих Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: 1 |
Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды
 (Процессор Intel Pentium 4 CPU 2.80GHz) Сообщение отредактировано: Тёмный Эльф - 26.11.2007 22:44 |
|
|
|
| hardcase |
26.11.2007 23:11
Сообщение
#4
|
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Цитата(Тёмный Эльф @ 26.11.2007 22:39)  Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды Это какая такая программа?? (Процессор Intel Pentium 4 CPU 2.80GHz) -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
|
|
|
Сообщений в этой теме
Тёмный Эльф поиск пути для кубика 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 Тёмный Эльф
Это какая такая программа??
Это программа 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 18:39 |