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

Автор: maksimla 30.01.2009 21:36

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


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


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

Автор: volvo 30.01.2009 23:10

Смотри, что от тебя требуется: сначала пишем обычную рекурсивную функцию, результат работы которой показан в твоем посте:

function fib_1(n: integer): integer;
begin
  writeln('calculating fib_1(', n, ')');
  if n < 2 then fib_1 := n
  else fib_1 := fib_1(n - 1) + fib_1(n - 2);
end;

begin
  writeln('result = ', fib_1(7));
end.

Запускаем ее, и смотрим, что творится:
Видишь, сколько вызовов происходит впустую? А теперь - твоя задача: имея массив, написать такую рекурсивную функцию(с теми же самыми параметрами, функция, вычисляющая Фибоначчи, всегда принимает одно число, и возвращает результат), которая будет брать значение из массива, если оно уже вычислено, тем самым избавляясь от повторных вызовов функции. Вот что выдает моя функция:
Чувствуешь, насколько меньше вычислений производится, насколько разгружается стек?

А вот как она выглядит - я пока не покажу тебе... Попробуй подумать сам.

Автор: maksimla 31.01.2009 16:12

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

Автор: maksimla 31.01.2009 19:01

я чегото неразобрался даже как эта рекурсия работает чегото и чего выводит 13 в последней строчке

Автор: volvo 31.01.2009 20:10

Помнишь, я давал тебе схему, как работает возведение в степень? Сделай точно такое же для этой функции, скажем для fib_1(4), чтоб очень много не рисовать, разберешься...

А 13 в последней строке - это и есть результат: 7-ое (если считать с нулевого) число Фибоначчи - 13: 0, 1, 1, 2, 3, 5, 8, 13

Автор: maksimla 31.01.2009 20:34

разобрался почему она так выводит сперва левую сторону дерева счетает потом правую и когда 7 раскладывает то получается тринадцать единиц но непонел как эти тренадцать единиц записывает все и выводит

Автор: maksimla 31.01.2009 23:39

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

Автор: maksimla 2.02.2009 22:01

ну я чегото нечего нимогу придумать

Автор: volvo 2.02.2009 22:19

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

{ здесь будем хранить уже вычисленные результаты }
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.

Вот и все...

Автор: maksimla 2.02.2009 23:27

а мочему масив до 23 ? а почему масив в самой функции нележит? мне кажется надо было чтобы массив в функции былбы

ах очень сложно мне

Автор: maksimla 3.02.2009 0:29

у меня чегото выбевает ошибка это из за того что масив от 0 до 23 а цикл от 0 до 255

Автор: maksimla 3.02.2009 1:00

пожалста скажите как вы эти посчетали и как вывели на экран 13
то мне еще в одной рекурсии надо подсчитать и вывести сколько обращений будет к прочедуре в другом задании

Автор: volvo 3.02.2009 1:24

Потому что начиная с 24-го значения число Фибоначчи не помещается в Integer, слишком большим становится...

Ай-яй-яй... Нельзя этого делать, тогда весь смысл использования массива пропадает: на каждом уровне рекурсии будет создаваться своя копия массива... Либо описывать внутри функции, но как типизированную константу (это тоже имеет недостаток, если интересует - расскажу), либо глобально...

Да, я сначала делал массив от 0 до 255, потом поменял размер, а здесь изменить забыл... Поправлю.

Автор: maksimla 3.02.2009 1:29

раскажи какой недостаток?

Автор: volvo 3.02.2009 2:56

Недостаток - это то, что надо явно инициализировать все значения. Ну ладно тут, от 0 до 23-х, всего 24 элемента. А если поменять тип на LongInt, тогда уже 46 чисел будут помещаться в этот тип, и придется написать в 2 раза больше (-1)-ниц... Но с другой стороны - есть неоспоримое преимущество: все, что уже было вычислено, второй раз вычисляться ВООБЩЕ не будет - сразу будет подставлено уже готовое значение. Особенно это эффективно, если функция вызывается не один раз, а несколько. Смотри, что будет:

function fib(n: integer): integer;
var
  f: integer;
const
  { вот это и есть тот самый недостаток }
  arr: array[0 .. 23] of integer = (
    -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1
  );
begin
  writeln('calculating fib(', n, ')');

  if arr[n] > -1 then fib := arr[n]
  else begin
    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
  writeln('result = ', fib(20));
  writeln('fib(12) = ', fib(12));
end.

fib(20) вычисляется обычно... А вот потом, когда вызывается еще fib(12) - никаких вычислений нет вообще, просто сразу возвращается значение из массива, и все... Запусти и посмотри, что будет...

Автор: Гость 3.02.2009 2:57

Program pr40 (Input, Output);          	

Var          	

X             : Array [1..50] Of Integer;   	

N             : Integer;               	

i               : Integer;               	
Begin     	
Write ('PASCAL: Вычисление чисел Фибоначчи '); 	

WriteLn ('по рекуррентной формуле c запоминанием членов.');              	

Write ('Введите количество членов (3<=N<=50):  N = ');                	
ReadLn (N);          	
X [1] := 1;              	
X [2] := 1;              	
WriteLn ('Вычисленные члены:');  	
Write ('1 1 ');         	
For i := 3 To N Do               	
Begin     	
X [i] := X [i - 2] + X [i - 1];  	

Write (X [i]);         	

Write (' ');              	

End;       	
ReadLn; 	

End.

Теги

Автор: volvo 3.02.2009 3:02

Гость, "Рекуррентная" - не значит "рекурсивная". Автору нужен был "гибрид" - рекурсивно, но с хранением промежуточных значений в массиве. Вопросы еще будут?

На будущее - то, что ты, kick, постишь под "гостем" - еще не значит, что Правила Форума тебя не касаются... Теги надо использовать... И программу проверять, кстати, тоже нужно... Как вариант - попробуй запустить свою программу, и ввести 49, посмотришь, что будет...