De Fibonacci-getallen zijn de getallen in de volgende gehele reeks. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In wiskundige termen wordt de reeks Fn van Fibonacci-getallen gedefinieerd door de herhalingsrelatie.
F N = Fn-1+ Fn-2
met zaadwaarden: F 0 = 0 en F 1 = 1.
Fibonacci-getallen met behulp van een native aanpak
Fibonacci-reeks met behulp van a Python while-lus is geïmplementeerd.
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>()> |
c structuur in structuur
>
>
Uitvoer
1 2 3 5 8 13 21 34 55 89>
Python-programma voor Fibonacci-getallen met behulp van recursie
Python Functie om het n-de Fibonacci-getal te vinden met behulp van Python-recursie .
Python3
javascript base64-decodering
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>))> |
>
>Uitvoer
34>
Tijdcomplexiteit: O(2 ^ n) Exponentieel
Hulpruimte: Op)
Fibonacci-reeks met behulp van DP (dynamisch programmeren)
Python dynamisch programmeren neemt de eerste twee Fibonacci-getallen als 0 en 1.
Python3
ffilms
# 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>))> |
>
>Uitvoer
34>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
Optimalisatie van de Fibonacci-reeks
Hier ook ruimte-optimalisatie, waarbij de eerste twee Fibonacci-getallen als 0 en 1 worden genomen.
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>))> |
numpige sommatie
>
>Uitvoer
34>
Tijdcomplexiteit: Op)
Hulpruimte: O(1)
Fibonacci-reeks met behulp van cache
lru_cache slaat het resultaat op, zodat we Fibonacci niet opnieuw voor hetzelfde getal hoeven te vinden.
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>))> |
>
>
Java-constanteUitvoer
34>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
Fibonacci-reeks met behulp van Backtracking
Functie voor het n-de Fibonacci-getal met behulp vanPython3
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>))> |
>
>Uitvoer
34>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
Zie het volledige artikel over de Programma voor Fibonacci-getallen voor meer details!