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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Ищущий истину
******

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

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


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

Код


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.


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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

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

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


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;
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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