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

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

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

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

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

F 8 = 0 1 1 2 3 5 8 13

или это -

F 8 = 1 1 2 3 5 8 13 21

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

Анимация Фибоначчи

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

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

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, нажмите здесь .