Програма Python для друку послідовності Фібоначчі
Числа Фібоначчі - це числа в наступній послідовності цілих чисел. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. З математичної точки зору, послідовність Fn чисел Фібоначчі визначається рекурентним співвідношенням.
Ф п = F n-1 + Ф n-2
із початковими значеннями: Ф 0 = 0 і Ф 1 = 1.
Числа Фібоначчі з використанням рідного підходу
Ряд Фібоначчі з використанням a Цикл while на Python реалізується.
Python3
n> => 10> num1> => 0> num2> => 1> next_number> => num2> count> => 1> while> count <> => n:> > print> (next_number, end> => ' '> )> > count> +> => 1> > num1, num2> => num2, next_number> > next_number> => num1> +> num2> print> ()> |
Вихід
1 2 3 5 8 13 21 34 55 89
Програма Python для чисел Фібоначчі за допомогою рекурсії
Python Функція для знаходження n-го числа Фібоначчі за допомогою Рекурсія Python .
Python3
def> Fibonacci(n):> > # Check if input is 0 then it will> > # print incorrect input> > if> n <> 0> :> > print> (> 'Incorrect input'> )> > # Check if n is 0> > # then it will return 0> > elif> n> => => 0> :> > return> 0> > # Check if n is 1,2> > # it will return 1> > elif> n> => => 1> or> n> => => 2> :> > return> 1> > else> :> > return> Fibonacci(n> -> 1> )> +> Fibonacci(n> -> 2> )> # Driver Program> print> (Fibonacci(> 9> ))> |
Вихід
34
Часова складність: O(2 ^ n) Експоненціальний
Допоміжний простір: O(n)
Послідовність Фібоначчі з використанням DP (динамічне програмування)
Динамічне програмування Python приймає перші два числа Фібоначчі як 0 і 1.
Python3
# Function for nth fibonacci> # number> FibArray> => [> 0> ,> 1> ]> def> fibonacci(n):> > > # Check is n is less> > # than 0> > if> n <> 0> :> > print> (> 'Incorrect input'> )> > > # Check is n is less> > # than len(FibArray)> > elif> n <> len> (FibArray):> > return> FibArray[n]> > else> :> > FibArray.append(fibonacci(n> -> 1> )> +> fibonacci(n> -> 2> ))> > return> FibArray[n]> # Driver Program> print> (fibonacci(> 9> ))> |
Вихід
34
Часова складність: O(n)
Допоміжний простір: O(n)
Оптимізація послідовності Фібоначчі
Тут також оптимізація простору, взявши перші два числа Фібоначчі за 0 і 1.
Python3
# Function for nth fibonacci number> def> fibonacci(n):> > a> => 0> > b> => 1> > > # Check is n is less> > # than 0> > if> n <> 0> :> > print> (> 'Incorrect input'> )> > > # Check is n is equal> > # to 0> > elif> n> => => 0> :> > return> 0> > > # Check if n is equal to 1> > elif> n> => => 1> :> > return> b> > else> :> > for> i> in> range> (> 1> , n):> > c> => a> +> b> > a> => b> > b> => c> > return> b> # Driver Program> print> (fibonacci(> 9> ))> |
Вихід
34
Часова складність: O(n)
Допоміжний простір: О(1)
Послідовність Фібоначчі з використанням кешу
lru_cache збереже результат, щоб нам не довелося знову знаходити Фібоначчі для того самого числа.
Python3
from> functools> import> lru_cache> # Function for nth Fibonacci number> @lru_cache> (> None> )> def> fibonacci(num:> int> )> -> >> int> :> > # check if num is less than 0> > # it will return none> > if> num <> 0> :> > print> (> 'Incorrect input'> )> > return> > # check if num between 1, 0> > # it will return num> > elif> num <> 2> :> > return> num> > # return the fibonacci of num - 1 & num - 2> > return> fibonacci(num> -> 1> )> +> fibonacci(num> -> 2> )> # Driver Program> print> (fibonacci(> 9> ))> |
Вихід
34
Часова складність: O(n)
Допоміжний простір: O(n)
Послідовність Фібоначчі з використанням зворотного відстеження
Використання функції для n-го числа Фібоначчі Python3
def> fibonacci(n, memo> => {}):> > if> n <> => 0> :> > return> 0> > elif> n> => => 1> :> > return> 1> > elif> n> in> memo:> > return> memo[n]> > else> :> > memo[n]> => fibonacci(n> -> 1> )> +> fibonacci(n> -> 2> )> > return> memo[n]> # Driver Program> print> (fibonacci(> 9> ))> |
Вихід
34
Часова складність: O(n)
Допоміжний простір: O(n)
Перегляньте повну статтю на Програму для чисел фібоначчі для більш детальної інформації!
