Форум «Всё о Паскале» > От рекурсии к итерации

Помощь - Поиск - Пользователи - Календарь

Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи

Atos

8.04.2004 9:42

Когда увидел прогу старой доброй Ханойской башни в теме "Рекурсия", не мог не вспомнить, про задачку, которую некоторым продвинутым прикладникам у нас давали на годовом экзамене на 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.

+
см. Ханойские башни.

Altair

9.04.2004 11:24

Да, здорово!
А я тоже решил переделать рекурсивную процедуру!
(в теме рекурсия- я выложил процедуру возведения в степень, вот ее не рекурсивный вариант (работает быстрее, т.к. рекурсия - медленная штука!)

Код

procedure S(m:real; n:integer; var k:real);
begin
If n>=0 then
begin
k:=1;
while n>=1 do
begin
k:=k*m;
dec(n);
end;
end else
begin
n:=n*(-1);
k:=1;
while n>=1 do
begin
k:=k*m;
dec(n);
end;
k:=1/k;
end
end;

var
a:real;
b:integer;
c:real;
begin
readln(a,b);
s(a,b,c);
writeln(c);
end.

причем она универсальная!
все что угодно возводит , и даже в отрицательную степень!

zx1024

9.04.2004 18:11

Oleg_Z, говоря по правде рекурсия в таком методе возведения в степень абсолютно лишняя.
Возведение в степень, используемое при арифметике с большими числами (здесь хоть рекурсия нужна).

Код

function POW (a : real; n : integer) : real;
var b : real;
begin
if n = 1 then
POW := a
else begin
b := POW (a, n shr 1);
if (n and 1) = 0 then
POW := b*b
else
POW := b*b*a
end;
end;

Без рекурсии

Код

function POW (a : real; n : integer) : real;
var b, c : real;
begin
c := a;
b := 1;
while n > 1 do
begin
if (n and 1) = 1 then
b := b * c;
n := n shr 1;
c := c * c;
end;
POW := b * c
end;

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.