Gitt et tall n , skrive ut n-te Fibonacci-nummer .
Fibonacci-tallene er tallene i følgende heltallssekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
Eksempler:
Anbefalt problemløsningsproblem [/Tex] med frøverdier ogInndata: n = 1
tilfeldig tall c-kodeUtgang: 1
Inndata: n = 9
Utgang: 3. 4
Inndata: n = 10
Utgang: 55
og 
. C++
// Fibonacci Series using Space Optimized Method> #include> using> namespace> std;> int> fib(>int> n)> {> >int> a = 0, b = 1, c, i;> >if> (n == 0)> >return> a;> >for> (i = 2; i <= n; i++) {> >c = a + b;> >a = b;> >b = c;> >}> >return> b;> }> // Driver code> int> main()> {> >int> n = 9;> >cout << fib(n);> >return> 0;> }> // This code is contributed by Code_Mech> |
>
>
C
// Fibonacci Series using Space Optimized Method> #include> int> fib(>int> n)> {> >int> a = 0, b = 1, c, i;> >if> (n == 0)> >return> a;> >for> (i = 2; i <= n; i++) {> >c = a + b;> >a = b;> >b = c;> >}> >return> b;> }> int> main()> {> >int> n = 9;> >printf>(>'%d'>, fib(n));> >getchar>();> >return> 0;> }> |
>
>
Java
// Java program for Fibonacci Series using Space> // Optimized Method> public> class> fibonacci {> >static> int> fib(>int> n)> >{> >int> a =>0>, b =>1>, c;> >if> (n ==>0>)> >return> a;> >for> (>int> i =>2>; i <= n; i++) {> >c = a + b;> >a = b;> >b = c;> >}> >return> b;> >}> >public> static> void> main(String args[])> >{> >int> n =>9>;> >System.out.println(fib(n));> >}> };> // This code is contributed by Mihir Joshi> |
>
>
Python3
# Function for nth fibonacci number - Space Optimisation> # Taking 1st two fibonacci numbers as 0 and 1> def> fibonacci(n):> >a>=> 0> >b>=> 1> >if> n <>0>:> >print>(>'Incorrect input'>)> >elif> n>=>=> 0>:> >return> a> >elif> n>=>=> 1>:> >return> b> >else>:> >for> i>in> range>(>2>, n>+>1>):> >c>=> a>+> b> >a>=> b> >b>=> c> >return> b> # Driver Program> print>(fibonacci(>9>))> # This code is contributed by Saket Modi> |
>
>
C#
// C# program for Fibonacci Series> // using Space Optimized Method> using> System;> namespace> Fib {> public> class> GFG {> >static> int> Fib(>int> n)> >{> >int> a = 0, b = 1, c = 0;> >// To return the first Fibonacci number> >if> (n == 0)> >return> a;> >for> (>int> i = 2; i <= n; i++) {> >c = a + b;> >a = b;> >b = c;> >}> >return> b;> >}> >// Driver function> >public> static> void> Main(>string>[] args)> >{> >int> n = 9;> >Console.Write(>'{0} '>, Fib(n));> >}> }> }> // This code is contributed by Sam007.> |
>
>
Javascript
> // Javascript program for Fibonacci Series using Space Optimized Method> function> fib(n)> {> >let a = 0, b = 1, c, i;> >if>( n == 0)> >return> a;> >for>(i = 2; i <= n; i++)> >{> >c = a + b;> >a = b;> >b = c;> >}> >return> b;> }> // Driver code> >let n = 9;> > >document.write(fib(n));> // This code is contributed by Mayank Tyagi> > |
>
>
PHP
// PHP program for Fibonacci Series // using Space Optimized Method function fib( $n) { $a = 0; $b = 1; $c; $i; if( $n == 0) return $a; for($i = 2; $i <= $n; $i++) { $c = $a + $b; $a = $b; $b = $c; } return $b; } // Driver Code $n = 9; echo fib($n); // This code is contributed by anuj_67. ?>> |
>
>
Produksjon
34>
Tidskompleksitet: På)
Hjelpeplass: O(1)
Rekursjonsmetode for å finne og skrive ut Nth Fibonacci-tall:
I matematiske termer er sekvensen Fn av Fibonacci-tall definert av gjentakelsesrelasjonen:
med frøverdier og
og
.
Det N-te Fibonacci-tallet kan bli funnet ved å bruke gjentakelsesrelasjonen vist ovenfor:
hrithik roshan
- hvis n = 0, returner deretter 0.
- Hvis n = 1, skal den returnere 1.
- For n> 1 skal den returnere Fn-1+ Fn-2
Nedenfor er implementeringen av tilnærmingen ovenfor:
C++
// Fibonacci Series using Recursion> #include> using> namespace> std;> int> fib(>int> n)> {> >if> (n <= 1)> >return> n;> >return> fib(n - 1) + fib(n - 2);> }> int> main()> {> >int> n = 9;> >cout << n <<>'th Fibonacci Number: '> << fib(n);> >return> 0;> }> // This code is contributed> // by Akanksha Rai> |
>
>
C
// Fibonacci Series using Recursion> #include> int> fib(>int> n)> {> >if> (n <= 1)> >return> n;> >return> fib(n - 1) + fib(n - 2);> }> int> main()> {> >int> n = 9;> >printf>(>'%dth Fibonacci Number: %d'>, n, fib(n));> >return> 0;> }> |
>
>
Java
// Fibonacci Series using Recursion> import> java.io.*;> class> fibonacci {> >static> int> fib(>int> n)> >{> >if> (n <=>1>)> >return> n;> >return> fib(n ->1>) + fib(n ->2>);> >}> >public> static> void> main(String args[])> >{> >int> n =>9>;> >System.out.println(> >n +>'th Fibonacci Number: '> + fib(n));> >}> }> /* This code is contributed by Rajat Mishra */> |
>
>
Python3
# Fibonacci series using recursion> def> fibonacci(n):> >if> n <>=> 1>:> >return> n> >return> fibonacci(n>->1>)>+> fibonacci(n>->2>)> if> __name__>=>=> '__main__'>:> >n>=> 9> >print>(n,>'th Fibonacci Number: '>)> >print>(fibonacci(n))> ># This code is contributed by Manan Tyagi.> |
>
>
C#
// C# program for Fibonacci Series> // using Recursion> using> System;> public> class> GFG {> >public> static> int> Fib(>int> n)> >{> >if> (n <= 1) {> >return> n;> >}> >else> {> >return> Fib(n - 1) + Fib(n - 2);> >}> >}> >// driver code> >public> static> void> Main(>string>[] args)> >{> >int> n = 9;> >Console.Write(n +>'th Fibonacci Number: '> + Fib(n));> >}> }> // This code is contributed by Sam007> |
>
>
Javascript
// Javascript program for Fibonacci Series> // using Recursion> function> Fib(n) {> >if> (n <= 1) {> >return> n;> >}>else> {> >return> Fib(n - 1) + Fib(n - 2);> >}> }> // driver code> let n = 9;> console.log(n +>'th Fibonacci Number: '> + Fib(n));> |
>
>
PHP
// PHP program for Fibonacci Series // using Recursion function Fib($n) { if ($n <= 1) { return $n; } else { return Fib($n - 1) + Fib($n - 2); } } // driver code $n = 9; echo $n . 'th Fibonacci Number: ' . Fib($n); // This code is contributed by Sam007 ?>> |
>
>
Produksjon
34>
Tidskompleksitet: Eksponentiell, som hver funksjon kaller to andre funksjoner.
Ekstra plass kompleksitet: O(n), ettersom maksimal dybde til rekursjonstreet er n.
Dynamisk programmeringsmetode for å finne og skrive ut Nth Fibonacci-tall:
Tenk på rekursjonstreet for det femte Fibonacci-tallet fra tilnærmingen ovenfor:
fib(5) / fib(4) fib(3) / / fib(3) fib(2) fib(2) fib(1) / / / fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / fib(1) fib(0)>
Hvis du ser, blir det samme metodekallet gjort flere ganger for samme verdi. Dette kan optimaliseres ved hjelp av dynamisk programmering. Vi kan unngå det gjentatte arbeidet som er gjort i rekursjonstilnærmingen ved å lagre Fibonacci-tallene som er beregnet så langt.
java tostring
Dynamisk programmeringsmetode for å finne og skrive ut Nth Fibonacci-tall:
Nedenfor er implementeringen av tilnærmingen ovenfor:
C++
// C++ program for Fibonacci Series> // using Dynamic Programming> #include> using> namespace> std;> class> GFG {> public>:> >int> fib(>int> n)> >{> >// Declare an array to store> >// Fibonacci numbers.> >// 1 extra to handle> >// case, n = 0> >int> f[n + 2];> >int> i;> >// 0th and 1st number of the> >// series are 0 and 1> >f[0] = 0;> >f[1] = 1;> >for> (i = 2; i <= n; i++) {> >// Add the previous 2 numbers> >// in the series and store it> >f[i] = f[i - 1] + f[i - 2];> >}> >return> f[n];> >}> };> // Driver code> int> main()> {> >GFG g;> >int> n = 9;> >cout << g.fib(n);> >return> 0;> }> // This code is contributed by SoumikMondal> |
>
>
C
// Fibonacci Series using Dynamic Programming> #include> int> fib(>int> n)> {> >/* Declare an array to store Fibonacci numbers. */> >int> f[n + 2];>// 1 extra to handle case, n = 0> >int> i;> >/* 0th and 1st number of the series are 0 and 1*/> >f[0] = 0;> >f[1] = 1;> >for> (i = 2; i <= n; i++) {> >/* Add the previous 2 numbers in the series> >and store it */> >f[i] = f[i - 1] + f[i - 2];> >}> >return> f[n];> }> int> main()> {> >int> n = 9;> >printf>(>'%d'>, fib(n));> >getchar>();> >return> 0;> }> |
>
>
Java
// Fibonacci Series using Dynamic Programming> public> class> fibonacci {> >static> int> fib(>int> n)> >{> >/* Declare an array to store Fibonacci numbers. */> >int> f[]> >=>new> int>[n> >+>2>];>// 1 extra to handle case, n = 0> >int> i;> >/* 0th and 1st number of the series are 0 and 1*/> >f[>0>] =>0>;> >f[>1>] =>1>;> >for> (i =>2>; i <= n; i++) {> >/* Add the previous 2 numbers in the series> >and store it */> >f[i] = f[i ->1>] + f[i ->2>];> >}> >return> f[n];> >}> >public> static> void> main(String args[])> >{> >int> n =>9>;> >System.out.println(fib(n));> >}> };> /* This code is contributed by Rajat Mishra */> |
>
>
Python3
# Fibonacci Series using Dynamic Programming> def> fibonacci(n):> ># Taking 1st two fibonacci numbers as 0 and 1> >f>=> [>0>,>1>]> >for> i>in> range>(>2>, n>+>1>):> >f.append(f[i>->1>]>+> f[i>->2>])> >return> f[n]> print>(fibonacci(>9>))> |
>
>
C#
// C# program for Fibonacci Series> // using Dynamic Programming> using> System;> class> fibonacci {> >static> int> fib(>int> n)> >{> >// Declare an array to> >// store Fibonacci numbers.> >// 1 extra to handle> >// case, n = 0> >int>[] f =>new> int>[n + 2];> >int> i;> >/* 0th and 1st number of the> >series are 0 and 1 */> >f[0] = 0;> >f[1] = 1;> >for> (i = 2; i <= n; i++) {> >/* Add the previous 2 numbers> >in the series and store it */> >f[i] = f[i - 1] + f[i - 2];> >}> >return> f[n];> >}> >// Driver Code> >public> static> void> Main()> >{> >int> n = 9;> >Console.WriteLine(fib(n));> >}> }> // This code is contributed by anuj_67.> |
>
>
Javascript
> // Fibonacci Series using Dynamic Programming> >function> fib(n)> >{> >/* Declare an array to store Fibonacci numbers. */> >let f =>new> Array(n+2);>// 1 extra to handle case, n = 0> >let i;> >/* 0th and 1st number of the series are 0 and 1*/> >f[0] = 0;> >f[1] = 1;> >for> (i = 2; i <= n; i++)> >{> >/* Add the previous 2 numbers in the series> >and store it */> >f[i] = f[i-1] + f[i-2];> >}> >return> f[n];> >}> >let n=9;> >document.write(fib(n));> > >// This code is contributed by avanitrachhadiya2155> > > |
>
>
PHP
//Fibonacci Series using Dynamic // Programming function fib( $n) { /* Declare an array to store Fibonacci numbers. */ // 1 extra to handle case, // n = 0 $f = array(); $i; /* 0th and 1st number of the series are 0 and 1*/ $f[0] = 0; $f[1] = 1; for ($i = 2; $i <= $n; $i++) { /* Add the previous 2 numbers in the series and store it */ $f[$i] = $f[$i-1] + $f[$i-2]; } return $f[$n]; } $n = 9; echo fib($n); // This code is contributed by // anuj_67. ?>> |
>
>
Produksjon
34>
Tidskompleksitet : O(n) for gitt n
Hjelpeplass : O(n)
Nth Power of Matrix-tilnærming til å finne og skrive ut Nth Fibonacci-tall
Denne tilnærmingen er avhengig av det faktum at hvis vi n ganger multipliserer matrisen M = {{1,1},{1,0}} til seg selv (med andre ord beregner potens(M, n)), så får vi (n) +1) Fibonacci-nummer som elementet ved rad og kolonne (0, 0) i den resulterende matrisen.
- Hvis n er jevn, så er k = n/2:
- Derfor N-te Fibonacci-tall = F(n) = [2*F(k-1) + F(k)]*F(k)
- Hvis n er oddetall, er k = (n + 1)/2:
- Derfor N-te Fibonacci-tall = F(n) = F(k)*F(k) + F(k-1)*F(k-1)
Hvordan fungerer denne formelen?
Formelen kan utledes fra matriseligningen.
freddie mercury
Ved å ta determinant på begge sider får vi (-1)n= Fn+1Fn-1– Fn2
Dessuten, siden AnENm= An+mfor enhver kvadratisk matrise A kan følgende identiteter utledes (de er hentet fra to forskjellige koeffisienter av matriseproduktet)
FmFn+ Fm-1Fn-1= Fm+n-1 ——————————(1)
Ved å sette n = n+1 i ligning(1),
FmFn+1+ Fm-1Fn= Fm+n —————————(2)
Setter m = n i ligning(1).
F2n-1= Fn2+ Fn-12
Setter m = n i ligning(2)
F2n= (Fn-1+ Fn+1)Fn= (2Fn-1+ Fn)Fn——–
likhet av strenger i java(Ved å sette Fn+1 = Fn + Fn-1)
For å få formelen til å bli bevist, trenger vi ganske enkelt å gjøre følgende
- Hvis n er partall, kan vi sette k = n/2
- Hvis n er oddetall, kan vi sette k = (n+1)/2
Nedenfor er implementeringen av tilnærmingen ovenfor
C++
// Fibonacci Series using Optimized Method> #include> using> namespace> std;> void> multiply(>int> F[2][2],>int> M[2][2]);> void> power(>int> F[2][2],>int> n);> // Function that returns nth Fibonacci number> int> fib(>int> n)> {> >int> F[2][2] = { { 1, 1 }, { 1, 0 } };> >if> (n == 0)> >return> 0;> >power(F, n - 1);> >return> F[0][0];> }> // Optimized version of power() in method 4> void> power(>int> F[2][2],>int> n)> {> >if> (n == 0 || n == 1)> >return>;> >int> M[2][2] = { { 1, 1 }, { 1, 0 } };> >power(F, n / 2);> >multiply(F, F);> >if> (n % 2 != 0)> >multiply(F, M);> }> void> multiply(>int> F[2][2],>int> M[2][2])> {> >int> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> >int> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> >int> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> >int> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> >F[0][0] = x;> >F[0][1] = y;> >F[1][0] = z;> >F[1][1] = w;> }> // Driver code> int> main()> {> >int> n = 9;> >cout << fib(9);> >getchar>();> >return> 0;> }> // This code is contributed by Nidhi_biet> |
>
>
C
#include> void> multiply(>int> F[2][2],>int> M[2][2]);> void> power(>int> F[2][2],>int> n);> /* function that returns nth Fibonacci number */> int> fib(>int> n)> {> >int> F[2][2] = { { 1, 1 }, { 1, 0 } };> >if> (n == 0)> >return> 0;> >power(F, n - 1);> >return> F[0][0];> }> /* Optimized version of power() in method 4 */> void> power(>int> F[2][2],>int> n)> {> >if> (n == 0 || n == 1)> >return>;> >int> M[2][2] = { { 1, 1 }, { 1, 0 } };> >power(F, n / 2);> >multiply(F, F);> >if> (n % 2 != 0)> >multiply(F, M);> }> void> multiply(>int> F[2][2],>int> M[2][2])> {> >int> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> >int> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> >int> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> >int> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> >F[0][0] = x;> >F[0][1] = y;> >F[1][0] = z;> >F[1][1] = w;> }> /* Driver program to test above function */> int> main()> {> >int> n = 9;> >printf>(>'%d'>, fib(9));> >getchar>();> >return> 0;> }> |
>
>
Java
// Fibonacci Series using Optimized Method> public> class> fibonacci {> >/* function that returns nth Fibonacci number */> >static> int> fib(>int> n)> >{> >int> F[][] =>new> int>[][] { {>1>,>1> }, {>1>,>0> } };> >if> (n ==>0>)> >return> 0>;> >power(F, n ->1>);> >return> F[>0>][>0>];> >}> >static> void> multiply(>int> F[][],>int> M[][])> >{> >int> x = F[>0>][>0>] * M[>0>][>0>] + F[>0>][>1>] * M[>1>][>0>];> >int> y = F[>0>][>0>] * M[>0>][>1>] + F[>0>][>1>] * M[>1>][>1>];> >int> z = F[>1>][>0>] * M[>0>][>0>] + F[>1>][>1>] * M[>1>][>0>];> >int> w = F[>1>][>0>] * M[>0>][>1>] + F[>1>][>1>] * M[>1>][>1>];> >F[>0>][>0>] = x;> >F[>0>][>1>] = y;> >F[>1>][>0>] = z;> >F[>1>][>1>] = w;> >}> >/* Optimized version of power() in method 4 */> >static> void> power(>int> F[][],>int> n)> >{> >if> (n ==>0> || n ==>1>)> >return>;> >int> M[][] =>new> int>[][] { {>1>,>1> }, {>1>,>0> } };> >power(F, n />2>);> >multiply(F, F);> >if> (n %>2> !=>0>)> >multiply(F, M);> >}> >/* Driver program to test above function */> >public> static> void> main(String args[])> >{> >int> n =>9>;> >System.out.println(fib(n));> >}> };> /* This code is contributed by Rajat Mishra */> |
>
>
Python3
# Fibonacci Series using> # Optimized Method> # function that returns nth> # Fibonacci number> def> fib(n):> >F>=> [[>1>,>1>],> >[>1>,>0>]]> >if> (n>=>=> 0>):> >return> 0> >power(F, n>-> 1>)> >return> F[>0>][>0>]> def> multiply(F, M):> >x>=> (F[>0>][>0>]>*> M[>0>][>0>]>+> >F[>0>][>1>]>*> M[>1>][>0>])> >y>=> (F[>0>][>0>]>*> M[>0>][>1>]>+> >F[>0>][>1>]>*> M[>1>][>1>])> >z>=> (F[>1>][>0>]>*> M[>0>][>0>]>+> >F[>1>][>1>]>*> M[>1>][>0>])> >w>=> (F[>1>][>0>]>*> M[>0>][>1>]>+> >F[>1>][>1>]>*> M[>1>][>1>])> >F[>0>][>0>]>=> x> >F[>0>][>1>]>=> y> >F[>1>][>0>]>=> z> >F[>1>][>1>]>=> w> # Optimized version of> # power() in method 4> def> power(F, n):> >if>(n>=>=> 0> or> n>=>=> 1>):> >return> >M>=> [[>1>,>1>],> >[>1>,>0>]]> >power(F, n>/>/> 2>)> >multiply(F, F)> >if> (n>%> 2> !>=> 0>):> >multiply(F, M)> # Driver Code> if> __name__>=>=> '__main__'>:> >n>=> 9> >print>(fib(n))> # This code is contributed> # by ChitraNayal> |
>
>
C#
// Fibonacci Series using> // Optimized Method> using> System;> class> GFG {> >/* function that returns> >nth Fibonacci number */> >static> int> fib(>int> n)> >{> >int>[, ] F =>new> int>[, ] { { 1, 1 }, { 1, 0 } };> >if> (n == 0)> >return> 0;> >power(F, n - 1);> >return> F[0, 0];> >}> >static> void> multiply(>int>[, ] F,>int>[, ] M)> >{> >int> x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0];> >int> y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1];> >int> z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0];> >int> w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1];> >F[0, 0] = x;> >F[0, 1] = y;> >F[1, 0] = z;> >F[1, 1] = w;> >}> >/* Optimized version of> >power() in method 4 */> >static> void> power(>int>[, ] F,>int> n)> >{> >if> (n == 0 || n == 1)> >return>;> >int>[, ] M =>new> int>[, ] { { 1, 1 }, { 1, 0 } };> >power(F, n / 2);> >multiply(F, F);> >if> (n % 2 != 0)> >multiply(F, M);> >}> >// Driver Code> >public> static> void> Main()> >{> >int> n = 9;> >Console.Write(fib(n));> >}> }> // This code is contributed> // by ChitraNayal> |
>
>
Javascript
> // Fibonacci Series using Optimized Method> // Function that returns nth Fibonacci number> function> fib(n)> {> >var> F = [ [ 1, 1 ], [ 1, 0 ] ];> >if> (n == 0)> >return> 0;> > >power(F, n - 1);> >return> F[0][0];> }> function> multiply(F, M)> {> >var> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> >var> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> >var> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> >var> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> >F[0][0] = x;> >F[0][1] = y;> >F[1][0] = z;> >F[1][1] = w;> }> // Optimized version of power() in method 4 */> function> power(F, n)> > >if> (n == 0> // Driver code> var> n = 9;> document.write(fib(n));> // This code is contributed by gauravrajput1> > |
>
>
Produksjon
34>
Tidskompleksitet: O(Logg n)
Hjelpeplass: O(Log n) hvis vi vurderer funksjonen kall stabelstørrelse, ellers O(1).
Relaterte artikler:
Store Fibonacci-tall i Java