У нас экзамен был после них, и я зарнее написал эту прогу(хотя так и не досталась). Поднапрягся и за полчаса набросал алгоритм. Но, скажу я, это было для меня тогда далеко не очевидно, да и теперь не знаю, сколько бы у меня ушло.
Ниже мой код. Всего строчек 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.
+
см. Ханойские башни.