"Ханойские Башни" и скорость выполнения. Опции

[DarkWishmaster]

Здравствуйте, тут попалась задача "Ханойские Башни" вроде бы классика, легко реализуемая рекурсией, но в задачи указано что для 1<=N<=20 время выполнения не должно превышать 1 сек. Существуют вообще такой алгоритм? С рекурсией больше 10 сек выдает, пробовал нерекурсивный ( с форума) тот тоже очень медленный. В гугле ничего не нашел.

Сообщение отредактировано: DarkWishmaster - 28.05.2011 18:49

[IUnknown]

Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?

[DarkWishmaster]

Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?

Да, для 20 дисков меньше 1 сек.

[IUnknown]

20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...

[DarkWishmaster]

20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...

Значит задача неправильно сформулирована, посмотрю ещё раз. Спасибо за ответ.
Даже в файле для 20 диском время выполнения около 3 сек.

Сообщение отредактировано: DarkWishmaster - 29.05.2011 16:07

[Гость]

для Н=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;

вроде как то так.. должно быстро работать...

[Гость]

для Н=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]

и все сойдется

Гость, извини, ты прочел вопрос в теме? Он был не про общее решение, а про скорость.
Напиши прогу, замерь время выполнения (или оцени его другим способом) - и тогда отвечай. Хорошо?