Рекурсия.Вычисление n-го элемента посл-ти, Вычисление n-го элемента посл-ти чисел Фибоначчи Опции

[BSS]

Очень нужна рекурсивная реализация для вычисления n-го элемента последовательности чисел Фибоначчи с использованием вспомогательного массива для хранения вычисленных значений
Помогите пожалуйста решить.

[BSS]

Вычислить n-й член последовательности Фибоначчи обычным способом и ускоренным (порядка С logn)
---------------

program fibona4i;
var n,k:longint;
procedure f1_usk;
 var a11,a12,a22,a21,d11,d12,d21,d22,c11,c12,c21,c22:longint;
  begin
  a11:=1;
  a12:=1;
  a21:=1;
  a22:=0;
  c11:=a11;
  c12:=a12;
  c21:=a21;
  c22:=a22;
  while n>2 do begin
  dec(n);
  d11:=a11*c11+a12*c21;
  d12:=a11*c12+a12*c22;
  d21:=a21*c11+a22*c21;
  d22:=a21*c12+a22*c22;
  c11:=d11; c12:=d12; c21:=d21; c22:=d22;
  end;
  writeln(d11);
  end;
procedure f2;
 var i,c,fpr,fsl:longint;
  begin
  fpr:=1;
  fsl:=1;
  for i:=1 to n-2 do begin
      c:=fsl;
      fsl:=fpr+fsl;
      fpr:=c;
  end;
  writeln(fsl);
  end;
(*Osn proga*)
begin
writeln('Usk sposob=1','   ','Ob sposob=2');
read(k);
writeln('Nomer 4isla');
read(n);
case k of
1: f1_usk;
2: f2;
end;
end.

-----------------------------------
уберите плз лишнее, оставив только рекурсивное решение

М

Тэги!!

Сообщение отредактировано: Lapp - 26.03.2010 6:26

[volvo]

удалите лишнее

Тут не удалять, а добавлять надо...

Знаешь, как называется вот этот метод - рекурсия

с использованием вспомогательного массива для хранения вычисленных значений

? Мемоизация (Memoization)... Выглядит как-то вот так:

const
  maxValue = 256;
var
  Results: array[1 .. maxValue] of longint;

function fib(n: integer): longint;
begin
  if Results[n] = -1 then
    if n <= 2 then Results[n] := 1
    else Results[n] := fib(n - 1) + fib(n - 2);

  fib := Results[n]
end;

var i: integer;
begin
  for i := 1 to maxValue do Results[i] := -1;

  writeln(fib(11));
end.

[BSS]

Тупо выводит результат 89...Но спасибо за мемоизацию

Сообщение отредактировано: BSS - 26.03.2010 3:20

[Lapp]

Тупо выводит результат 89...Но спасибо за мемоизацию

Гм. Почему это - тупо??
И почему "но"?..

Ты вообще о чем?.. Тебе дали в лучшем виде то, что ты просил - а у тебя какие-то придирки?.. Будь так добр, объясни.

[BSS]

Ну программа не работает в смысле.(тупо выводит-это о программе).Извините, пожалуйста, если что не так сказал

[Lapp]

Ну программа не работает в смысле.(тупо выводит-это о программе).Извините, пожалуйста, если что не так сказал

Постой, постой. Как это не работатет?..
Ты просил рекурсивную функцию для подсчета чисел Фибоначчи? Тебе и дали эту функцию.
То, что она выводит 11-й элемент последовательности правильно (89) - разве это не подтверждение того, что она работает??..

Почитай Крылова. "Мартышка и очки" называется. Это про тебя. Просишь что-то, а как применить - без понятия..

PS
разобраться он хочет.. ага, держи карман шире. Даже посмотреть, что именно выводится - мы уже не в состоянии..

[BSS]

Постой, постой. Как это не работатет?..
Ты просил рекурсивную функцию для подсчета чисел Фибоначчи? Тебе и дали эту функцию.
То, что она выводит 11-й элемент последовательности правильно (89) - разве это не подтверждение того, что она работает??..

Почитай Крылова. "Мартышка и очки" называется. Это про тебя. Просишь что-то, а как применить - без понятия..

PS
разобраться он хочет.. ага, держи карман шире. Даже посмотреть, что именно выводится - мы уже не в состоянии..

********************************
Спасибо Вам, Владимир и Андрей. Я виноват, что не заметил, что там выводится значение функции от 11... fib(11). Ночью дело было...
*************
*************
Программа значит:

const
  maxValue = 256;
var
  Results: array[1 .. maxValue] of longint;

function fib(n: integer): longint;
begin
  if Results[n] = -1 then
    if n <= 2 then Results[n] := 1
    else Results[n] := fib(n - 1) + fib(n - 2);

  fib := Results[n]
end;

var i,n: integer;
begin
  readln(n);
  for i:= 1 to maxValue do Results[i]:= -1;

  writeln(fib(n));
end.

Добавлено через 8 мин.
А что означает строка:

if Results[n] = -1


?

Сообщение отредактировано: Lapp - 26.03.2010 23:19

[Lapp]

А что означает строка:
if Results[n] = -1
?

Это значит, что нужный член последовательности еще не посчитан. Перед работой программа инициализирует массив значением -1. Это значение не встречается в последовательности, поэтому оно используется для индикации того, что этот член еще не считался, и программа начинает его вычислять. В противном случае она выдает то значение, которое сохранено в массиве.


Пожалуйста, при публикации программного кода используй тэги кода (Правила Форума, п.5 и правила раздела Задачи, п.2)