IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> "Ханойские Башни" и скорость выполнения.
DarkWishmaster
сообщение 28.05.2011 14:48
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


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

Сообщение отредактировано: DarkWishmaster - 28.05.2011 14:49
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 28.05.2011 22:58
Сообщение #2


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Что именно должно быть сделано за эту секунду? Напечатана последовательность перемещений?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 29.05.2011 9:33
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(IUnknown @ 28.05.2011 22:58) *

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

Да, для 20 дисков меньше 1 сек.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 29.05.2011 10:07
Сообщение #4


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


20 дисков - это 1048575 перемещений. Вывести на экран такое количество информации меньше чем за секунду - нереально при любом алгоритме. В файл сбрасывается за секунду элементарно, самым простым рекурсивным решением. А потом даже прочесть из файла и вывести на экран уже записанное решение ты не успеешь за секунду. Размер файла - больше 4Мб...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 29.05.2011 10:18
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(IUnknown @ 29.05.2011 10:07) *

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

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

Сообщение отредактировано: DarkWishmaster - 29.05.2011 12:07
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Гость
сообщение 15.06.2011 22:09
Сообщение #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;

вроде как то так.. должно быстро работать...
 К началу страницы 
+ Ответить 
Гость
сообщение 15.06.2011 23:08
Сообщение #7


Гость






Цитата(Гость @ 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
сообщение 15.06.2011 23:14
Сообщение #8


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 29.03.2024 2:57
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"