Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Алгоритмы _ "Ханойские Башни" и скорость выполнения.
Автор: DarkWishmaster 28.05.2011 14:48
Здравствуйте, тут попалась задача "Ханойские Башни" вроде бы классика, легко реализуемая рекурсией, но в задачи указано что для 1<=N<=20 время выполнения не должно превышать 1 сек. Существуют вообще такой алгоритм? С рекурсией больше 10 сек выдает, пробовал нерекурсивный ( с форума) тот тоже очень медленный. В гугле ничего не нашел.
Автор: IUnknown 28.05.2011 22:58
Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?
Автор: DarkWishmaster 29.05.2011 9:33
Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?
Да, для 20 дисков меньше 1 сек.
Автор: IUnknown 29.05.2011 10:07
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
Автор: DarkWishmaster 29.05.2011 10:18
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
Значит задача неправильно сформулирована, посмотрю ещё раз. Спасибо за ответ.
Даже в файле для 20 диском время выполнения около 3 сек.
Автор: Гость 15.06.2011 22:09
для Н=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;
вроде как то так.. должно быстро работать...
Автор: Гость 15.06.2011 23:08
для Н=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;
вроде как то так.. должно быстро работать...
s=0;
просто цикл от 1 до Н
и все сойдется
Автор: Lapp 15.06.2011 23:14
Гость, извини, ты прочел вопрос в теме? Он был не про общее решение, а про скорость.
Напиши прогу, замерь время выполнения (или оцени его другим способом) - и тогда отвечай. Хорошо?