Последовательность Фибоначчи: Алгоритм и упрощенная реализация на языке Python

1.1 Последовательность Фибоначчи

Числа Фибоначчи, иногда известные как Fn, создают ряд, в котором каждое число является суммой
двух предыдущих чисел. Хотя некоторые авторы игнорируют начальные слова и начинают последовательность
с 1 и 1 или с 1 и 2, обычно последовательность начинается с 0 и 1.
После 0 и 1 в последовательности следуют следующие значения: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

1.2 Две предыдущие цифры объединяются, чтобы получить следующее число:

• 1 находится путем сложения двух предшествующих ей цифр (0+1),
• 2 — путем сложения двух предшествующих цифр (1+1),
• 3 — путем сложения двух предшествующих чисел (1+2),
• 5 — путем сложения двух предшествующих чисел (2+3) и так далее!

1.3 Математически Фибоначчи можно представить следующим образом:

F(1) = 1
F(2) = 1
F(n) = F(n — 1) + F(n — 2)

1.4 наглядное представление

2 Алгоритм Фибоначчи

2.1 Нерекурсивный итеративный алгоритм Фибоначчи
Процедуры или подпрограммы, написанные на языке программирования, которые не ссылаются на самих себя
называются нерекурсивными функциями.

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

Procedure Iterative_Fibonacci(n):
    int f0, f1, fib
    f0 = 0
    f1 = 1
    display f0, f1
    for int i:= 1 to n:
        fib := f0 + f1   
        f0 := f1
        f1 := fib
        display fib
    END for loop
END Iterative_Fibonacci

2.1.2 Реализация в Python

num_terms = int(input("Number of terms? "))

# first two terms
f1, f2 = 0, 1
count = 0

# checking for the validity of the number of terms
if num_terms <= 0:
   print("Enter a positive integer")
# if there is only one term, return f1
elif num_terms == 1:
   print("Fibonacci sequence to",num_terms,":")
   print(f1)
# generate fibonacci sequence
else:
   print("Fibonacci sequence:")
   while count < num_terms:
       print(f1)
       nths = f1 + f2
       # update values
       f1 = f2
       f2 = nths
       count += 1

2.2 Рекурсивная реализация последовательности Фибоначчи

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

2.2.1 Свойства рекурсии

1. Должен существовать достижимый базовый случай, когда функция перестает вызывать саму себя, иначе возникнет бесконечный цикл
2. Аргумент функции должен изменяться при каждом вызове.
3. Выполнение одинаковых операций несколько раз с разными входами.
4. Для каждого шага мы применяем меньшие входы, чтобы уменьшить сложность задачи.

2.2.2 Алгоритм рекурсивного Фибоначчи

START
Procedure Fibonacci(n)
   declare f0, f1, fib, loop 

   set f0 to 0
   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 + f1   
      f0 ← f1
      f1 ← fib

      display fib
   end for

END

2.2.3 Реализация на языке Python

def fibo(n):
   if n <= 1:
       return n
   else:
       return(fibo(n-1) + fibo(n-2))

nterms = int(input('enter an integer? '))

# check if the number of terms is valid
if nterms <= 0:
   print("Please enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(recur_fibo(i))

Спасибо за прочтение, следите за другими интересными материалами по теме Структура данных и алгоритмы