Версия для печати темы

Автор: compiler 15.05.2008 19:43

Добрый день!
Есть следующие функция:

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 получаем: То есть мы имеем цифры идущие парами, но через 3 или 5 хода встречается "цифра-одиночка".

Что с этим делать - не знаю. Буду рад помощи.

Автор: volvo 15.05.2008 19:49

Последовательность Хольфштадтера?

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

, если не ошибаюсь...

Автор: Michael_Rybak 15.05.2008 19:57

в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.

Автор: compiler 15.05.2008 20:04

И откуда ты это знаешь?
То есть, вместо рекурсивного вызова функции мы получаем рекурсивное обращение к элементам массива.. Где-то я такое уже видел, да подзабыл уже...

Спасибо!

Автор: Michael_Rybak 15.05.2008 21:27

да, вроде того

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

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

а в самом начале процедуры смотришь, не вызывалась ли она раньше с такими же параметрами (и если да - не считаешь ничего, а возвращаешь полученный ранее ответ).

Автор: compiler 15.05.2008 21:59

интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.

Автор: hardcase 16.05.2008 21:01

Это еще называется динамическим программированием.

Автор: compiler 16.05.2008 23:14

буду знать, спасибо..