Помощь - Поиск - Пользователи - Календарь
Полная версия: "Ханойские Башни" и скорость выполнения.
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
DarkWishmaster
Здравствуйте, тут попалась задача "Ханойские Башни" вроде бы классика, легко реализуемая рекурсией, но в задачи указано что для 1<=N<=20 время выполнения не должно превышать 1 сек. Существуют вообще такой алгоритм? С рекурсией больше 10 сек выдает, пробовал нерекурсивный ( с форума) тот тоже очень медленный. В гугле ничего не нашел.
IUnknown
Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?
DarkWishmaster
Цитата(IUnknown @ 28.05.2011 22:58) *

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

Да, для 20 дисков меньше 1 сек.
IUnknown
20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
DarkWishmaster
Цитата(IUnknown @ 29.05.2011 10:07) *

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

Значит задача неправильно сформулирована, посмотрю ещё раз. Спасибо за ответ.
Даже в файле для 20 диском время выполнения около 3 сек.
Гость
для Н=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 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;

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

s=0;
просто цикл от 1 до Н

и все сойдется
Lapp
Цитата(Гость @ 16.06.2011 0:08) *
и все сойдется

Гость, извини, ты прочел вопрос в теме? Он был не про общее решение, а про скорость.
Напиши прогу, замерь время выполнения (или оцени его другим способом) - и тогда отвечай. Хорошо?
Pinyin Nup
Exclusive offer for women only.
Get 5 Crore Life cover at Rs.99 per month.

Contact any of our representatives:

col_mail@yahoo.com
richardwaikhom91@yahoo.com
sadmawaikhom93@yahoo.com
steffiwaikhom96@yahoo.com
rakesh.soibam@yandex.com
johnson.sarubam@yandex.com
inielitimp@yahoo.com
khaidemibimcha@yahoo.com
tomtakhellambam@yahoo.com
remmeijenpui@yahoo.com
joysanakhumukcham@yandex.com
linthoi724@yahoo.com
zam.pm@yandex.com
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.