"Ханойские Башни" и скорость выполнения. |
"Ханойские Башни" и скорость выполнения. |
DarkWishmaster |
28.05.2011 14:48
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Здравствуйте, тут попалась задача "Ханойские Башни" вроде бы классика, легко реализуемая рекурсией, но в задачи указано что для 1<=N<=20 время выполнения не должно превышать 1 сек. Существуют вообще такой алгоритм? С рекурсией больше 10 сек выдает, пробовал нерекурсивный ( с форума) тот тоже очень медленный. В гугле ничего не нашел.
Сообщение отредактировано: DarkWishmaster - 28.05.2011 14:49 |
IUnknown |
29.05.2011 10:07
Сообщение
#2
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
|
DarkWishmaster |
29.05.2011 10:18
Сообщение
#3
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб... Значит задача неправильно сформулирована, посмотрю ещё раз. Спасибо за ответ. Даже в файле для 20 диском время выполнения около 3 сек. Сообщение отредактировано: DarkWishmaster - 29.05.2011 12:07 |
Текстовая версия | 26.05.2024 0:47 |