поиск чисел фибоначи рекурсией, я нечего непонел и незнаю с чего начать помогите Опции

[maksimla]

Фибоначчо числа можно общетать рекурсией. Рекурсивные запросы можно увидить как на двоичном дереве


Можно увидить что некоторые Фибоначчо числа находят несколько раз, что это неэфективно.
Напишите функцию на которой каждое фибоначчи число было рекурсивно общитано только один раз о его значение будущим высчитываниям было держано в массиве.


непонел что надо зделать и какие значения будут в функцию поступать

[volvo]

Ну неужели же это настолько сложно??? Смотри:

{ здесь будем хранить уже вычисленные результаты }
var arr: array[0 .. 23] of integer;

function fib(n: integer): integer;
var f: integer;
begin
  { это потом уберешь, только чтобы показать, как и что вызывается }
  writeln('calculating fib(', n, ')');

  { результат для текущего n уже есть? значит, сразу возвращаем его }
  if arr[n] > -1 then fib := arr[n]
  else begin
    { нет, arr[ n ] был равен -1, значит, N-ое число Фибоначчи
       еще не вычислено... Вот и вычисляем. Так же, как и обычно }
    if n < 2 then arr[n] := n
    else arr[n] := fib(n - 1) + fib(n - 2);
    { а вот теперь - возвращаем то, что вычислили }
    fib := arr[n];
  end;

end;

var i: integer;
begin
  { чтобы функция работала правильно, заполняем весь массив
     значениями (-1). Это будет признаком, что соответствующее
     число Фибоначчи еще ни разу не было найдено функцией }
  for i := 0 to 23 do arr[i] := -1;
  writeln('result = ', fib(7));
end.

Вот и все...

Сообщение отредактировано: volvo - 3.02.2009 1:24