Структура данных и алгоритмы Фибоначчи

Ряд Фибоначчи генерирует последующее число, добавляя два предыдущих числа. Ряд Фибоначчи начинается с двух чисел — F ₀ и F ₁ . Начальные значения F ₀ и F ₁ могут быть приняты 0, 1 или 1, 1 соответственно.

Ряд Фибоначчи удовлетворяет следующим условиям —

F n = F n-1 + F n-2

Следовательно, ряд Фибоначчи может выглядеть так —

F ₈ = 0 1 1 2 3 5 8 13

или это —

F ₈ = 1 1 2 3 5 8 13 21

В целях иллюстрации Фибоначчи F ₈ отображается как —

Итерационный алгоритм Фибоначчи

Сначала мы попытаемся составить итерационный алгоритм для ряда Фибоначчи.

Procedure Fibonacci(n)
   declare f 0 , f 1 , fib, loop 
   
   set f 0 to 0
   set f 1 to 1
   
   display f 0 , f 1
   
   for loop ← 1 to n
   
      fib ← f 0 + f 1   
      f 0 ← f 1
      f 1 ← fib

      display fib
   end for
	
end procedure

Чтобы узнать о реализации вышеупомянутого алгоритма на языке программирования C, нажмите здесь .

Рекурсивный алгоритм Фибоначчи

Давайте узнаем, как создать рекурсивный алгоритм ряда Фибоначчи. Базовые критерии рекурсии.

START
Procedure Fibonacci(n)
   declare f 0 , f 1 , fib, loop 
   
   set f 0 to 0
   set f 1 to 1
   
   display f 0 , f 1
   
   for loop ← 1 to n
   
      fib ← f 0 + f 1   
      f 0 ← f 1
      f 1 ← fib

      display fib
   end for

END

Чтобы увидеть реализацию вышеуказанного алгоритма на языке программирования C, нажмите здесь .