Помощь - Поиск - Пользователи - Календарь
Полная версия: избавиться от рекурсии
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
compiler
Добрый день!
Есть следующие функция:
function f_a(const n : integer): longint;
begin
if n <= 1 then f_a:=1 else
f_a:=n - f_a(f_a(n-1));
end; { f_a }

Необходимо переписать функцию, избавившись от рекурсии.

Для n>=0 получаем:
Код
  1   1   2   3   3   4   4   5   6   6   7   8   8   9   9  10  11  11  12  12  13  14  14  15  16  16  17  17  18  19  19  20  21  21  22  22  23  24  24  25...
То есть мы имеем цифры идущие парами, но через 3 или 5 хода встречается "цифра-одиночка".

Что с этим делать - не знаю. Буду рад помощи.
volvo
Последовательность Хольфштадтера? smile.gif

function myFa(n: integer): longint;
function sigma: real;
begin
sigma := (sqrt(5)-1) / 2;
end;
begin
myFa := trunc(sigma*(n + 1));
end;

, если не ошибаюсь...
Michael_Rybak
в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.
compiler
Цитата(volvo @ 15.05.2008 15:49) *
Последовательность Хольфштадтера? smile.gif
И откуда ты это знаешь?smile.gif
Цитата
в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.
То есть, вместо рекурсивного вызова функции мы получаем рекурсивное обращение к элементам массива.. Где-то я такое уже видел, да подзабыл уже...

Спасибо!
Michael_Rybak
Цитата
получаем рекурсивное обращение к элементам массива


да, вроде того smile.gif

есть еще рекурсия с запоминанием промежуточных результатов.

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

а в самом начале процедуры смотришь, не вызывалась ли она раньше с такими же параметрами (и если да - не считаешь ничего, а возвращаешь полученный ранее ответ).
compiler
Цитата(Michael_Rybak @ 15.05.2008 17:27) *
есть еще рекурсия с запоминанием промежуточных результатов. ...
интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.
hardcase
Цитата(compiler @ 15.05.2008 18:59) *
интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.
Это еще называется динамическим программированием.
compiler
Цитата(hardcase @ 16.05.2008 17:01) *
Это еще называется динамическим программированием.
буду знать, спасибо..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.