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

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> От рекурсии к итерации, Достоинства и недостатки
сообщение
Сообщение #1


Прогрессор
****

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

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


Когда увидел прогу старой доброй Ханойской башни в теме "Рекурсия", не мог не вспомнить, про задачку, которую некоторым продвинутым прикладникам у нас давали на годовом экзамене на 1 курсе: написать её НЕрекурсивную реализацию. Некоторые, в общем-то, неглупые люди тогда сидели над ней часа по три, так и не решив.
У нас экзамен был после них, и я зарнее написал эту прогу(хотя так и не досталась). Поднапрягся и за полчаса набросал алгоритм. Но, скажу я, это было для меня тогда далеко не очевидно, да и теперь не знаю, сколько бы у меня ушло.
Ниже мой код. Всего строчек 15-20. Но очень советую - ради интереса, попробуйте сначала сами реализовать его - очень неплохая разминка для мозгов!
За сколько времени получится?

Вообще , Ханойская башня, числа Фибоначчи и т. п. - задачи, для который рекурсивное решение "само напрашивается", наиболее понятно, удобно и быстро пишется. Но попробуйте-ка запустить рекурсивную и итерационную прогу той же Башни для большого числа колец, да хотя бы 10-15. В данном случае, итерация хотя во много раз сложнее, но и во много раз быстрее.
Есть ещё рекурсивные АТД, например, деревья. Для них, хотя и с трудом, то тоже можно писать итерационные процедуры, скажем, поика и заполнения.
Я одном своём проекте столкнулся с прямой необходимостью этого - просто при небольшом увеличении одного параметра прога может выполняться больше часа, а потом вылететь от переполнения. Так что рано или поздно этому придётся учиться каждому.

Предлагаю: присылайте интересные итерационные варианты рекурсивных прог, а главное, идеи относительно методов перехода от рекурсии к итерации.
У меня есть некоторые мысли, например, метод выделения инвариантов (которым, в принципе, и воспользовался в HanoyTower).




Код

                        program HanoyTower;
type TInt=longint;
procedure Tower(n:TInt);
var m,k,l,s:TInt;
    iz,v,c,x:byte;
begin
n:=longint(round(exp(n*ln(2))))-1;
for m:=1 to n do
  begin
  iz:=1; c:=2; v:=3; k:=1; l:=n; s:=(k+l) div 2;
  repeat
  if m<s then begin x:=v;  v:=c;  c:=x; l:=s-1; end;
  if m>s then begin x:=iz; iz:=c; c:=x; k:=s+1; end;
  if m=s then begin writeln(iz,'-',v); break; end;
  s:=(k+l) div 2;
  until 2*2=5;
  end;
end;

var n:TInt;
begin
n:=4;
Tower(n);
readln;
end.


+
см. Ханойские башни.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


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

 





- Текстовая версия 27.02.2021 4:29
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name