Рекурсия

Gagarin614 · 09.03.2011, 15:35

Помогите написать программу в делфи:
Условие:
Описать рекурсивную функцию
function fib(n : integer) : integer;
для вычисления n-ого (n =< 40) числа Фибоначчи.
Указание.
Последовательность чисел Фибоначчи fk образуется так:
f0=1, f1=1, fk = fk-2 + fk-1.
Зарания спасибо

kreol · 09.03.2011, 16:44

Код:

function fib(n:integer): integer;
begin
  if (n = 0) or (n = 1) then
   fib := 1;
  else  
   fib := fib(n - 1) + fib(n - 2);
end;

вроде так.
п.с. счет идет с 0
т.е.
0 -1
1 -1
2 -2
3 -3
4 -5
5 -8 и т.д.
хотя в lisp -e это намного изящнее

Код:

(defun fibonacci(n)
    (if (or (= n 0) (= n 1))
     1
     (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

Gagarin614 · 09.03.2011, 18:36

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

kreol · 13.03.2011, 01:43

Цитата:

Сообщение от Gagarin614

встречаюсь с этой прроцедурой впервые

вы о чем??

Gagarin614 · 13.03.2011, 13:46

о том что тему рекурсия с трудом понимаю

kreol · 13.03.2011, 22:46

ааа ну рекурсия это вызов функции самой себя некоторое количество раз.
общий принцип построения:

ОБЯЗАТЕЛЬНО условие выход из рекурсии
Тело рекурсии
Вызов этой же функции опять.
если "разложить" код приведенный выше для функции fib(3) то получим

"переменной" - "функции" после первого прохода возвращается
fib(3-1)+ fib(3 - 2) т.е. fib(2)+fib(1) после второго прохода
fib(2) переходит в fib(1) - fib(0) a fib(1) просто в 1
дальше
fib(1) -> 1 fib(0)-> 1 ну и 1
в общем у нас получается 3
проверяем
№ 0 1 2 3
числа фиб. 1 1 2 3
как видим мы посчитали реально не для 3-го элемента а для 4-го т.к. номера элементов начинаются с 0

Gagarin614 · 14.03.2011, 19:39

Спасибо

09.03.2011, 15:35	#1 (permalink)
Gagarin614 Member Регистрация: 17.10.2010 Сообщений: 43 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Рекурсия Помогите написать программу в делфи: Условие: Описать рекурсивную функцию function fib(n : integer) : integer; для вычисления n-ого (n =< 40) числа Фибоначчи. Указание. Последовательность чисел Фибоначчи fk образуется так: f0=1, f1=1, fk = fk-2 + fk-1. Зарания спасибо

09.03.2011, 16:44	#2 (permalink)
kreol Member Регистрация: 27.02.2010 Сообщений: 659 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 1312	Код: function fib(n:integer): integer; begin if (n = 0) or (n = 1) then fib := 1; else fib := fib(n - 1) + fib(n - 2); end; вроде так. п.с. счет идет с 0 т.е. 0 -1 1 -1 2 -2 3 -3 4 -5 5 -8 и т.д. хотя в lisp -e это намного изящнее Код: (defun fibonacci(n) (if (or (= n 0) (= n 1)) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2))))) Последний раз редактировалось kreol; 09.03.2011 в 16:49

09.03.2011, 15:35
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Люди уже писали про это, полистайте Рекурсия Рекурсия Рекурсия в паскале Рекурсия. Рекурсия

09.03.2011, 18:36	#3 (permalink)
Gagarin614 Member Регистрация: 17.10.2010 Сообщений: 43 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	примного лагодарен, не могли бы пояснить что выполняет каждая строчка, встречаюсь с этой прроцедурой впервые

13.03.2011, 13:46	#5 (permalink)
Gagarin614 Member Регистрация: 17.10.2010 Сообщений: 43 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	о том что тему рекурсия с трудом понимаю

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070

13.03.2011, 22:46	#6 (permalink)
kreol Member Регистрация: 27.02.2010 Сообщений: 659 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 1312	ааа ну рекурсия это вызов функции самой себя некоторое количество раз. общий принцип построения: ОБЯЗАТЕЛЬНО условие выход из рекурсии Тело рекурсии Вызов этой же функции опять. если "разложить" код приведенный выше для функции fib(3) то получим "переменной" - "функции" после первого прохода возвращается fib(3-1)+ fib(3 - 2) т.е. fib(2)+fib(1) после второго прохода fib(2) переходит в fib(1) - fib(0) a fib(1) просто в 1 дальше fib(1) -> 1 fib(0)-> 1 ну и 1 в общем у нас получается 3 проверяем № 0 1 2 3 числа фиб. 1 1 2 3 как видим мы посчитали реально не для 3-го элемента а для 4-го т.к. номера элементов начинаются с 0

14.03.2011, 19:39	#7 (permalink)
Gagarin614 Member Регистрация: 17.10.2010 Сообщений: 43 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Спасибо