![]() |
![]() ![]() |
![]() |
DarkWishmaster |
![]()
Сообщение
#1
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: ![]() ![]() ![]() |
Здравствуйте, тут попалась задача "Ханойские Башни" вроде бы классика, легко реализуемая рекурсией, но в задачи указано что для 1<=N<=20 время выполнения не должно превышать 1 сек. Существуют вообще такой алгоритм? С рекурсией больше 10 сек выдает, пробовал нерекурсивный ( с форума) тот тоже очень медленный. В гугле ничего не нашел.
Сообщение отредактировано: DarkWishmaster - 28.05.2011 14:49 |
IUnknown |
![]()
Сообщение
#2
|
![]() a.k.a. volvo877 ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: ![]() ![]() ![]() |
Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?
|
DarkWishmaster |
![]()
Сообщение
#3
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: ![]() ![]() ![]() |
|
IUnknown |
![]()
Сообщение
#4
|
![]() a.k.a. volvo877 ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: ![]() ![]() ![]() |
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
|
DarkWishmaster |
![]()
Сообщение
#5
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: ![]() ![]() ![]() |
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб... Значит задача неправильно сформулирована, посмотрю ещё раз. Спасибо за ответ. Даже в файле для 20 диском время выполнения около 3 сек. Сообщение отредактировано: DarkWishmaster - 29.05.2011 12:07 |
Гость |
![]()
Сообщение
#6
|
Гость ![]() |
для Н=1 ответ 1 иначе...
s=2; for i:=1 to n-1 do s:=s*2+1; write(s); for(int i=0;i<n-1;i++) s=s*2+1; cout<<s; вроде как то так.. должно быстро работать... |
Гость |
![]()
Сообщение
#7
|
Гость ![]() |
|
Lapp |
![]()
Сообщение
#8
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
и все сойдется Гость, извини, ты прочел вопрос в теме? Он был не про общее решение, а про скорость. Напиши прогу, замерь время выполнения (или оцени его другим способом) - и тогда отвечай. Хорошо? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
![]() |
Текстовая версия | 30.08.2024 2:41 |