logo

TechCodeview

N. Fibonacci nummer

Givet et nummer n , Print n-te Fibonacci nummer .

Fibonacci-tallene er tallene i følgende heltalssekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..



Eksempler:

Input: n = 1



strukturer ved hjælp af arrays i c

Output: 1

Input: n = 9

Output: 3. 4



Input: n = 10

Output: 55

Anbefalet problemløsningsproblem [/Tex] med frøværdier og F_0 = 0og F_1 = 1.

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. ?>>
>
>

Produktion 
34>

Tidskompleksitet: På)
Hjælpeplads: O(1)

Rekursionsmetode til at finde og udskrive N. Fibonacci-numre:

I matematiske termer er sekvensen Fn af Fibonacci-tal defineret af gentagelsesrelationen: F_{n} = F_{n-1} + F_{n-2} med frøværdier og F_0 = 0og F_1 = 1.

Det Nth Fibonacci-nummer kan findes ved hjælp af gentagelsesrelationen vist ovenfor:

computer opfundet år
  • hvis n = 0, returner derefter 0.
  • Hvis n = 1, skal det returnere 1.
  • For n> 1 skal den returnere Fn-1+ Fn-2

Nedenfor er implementeringen af ​​ovenstående tilgang:

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 ?>>
>
>

Produktion 
34>

Tidskompleksitet: Eksponentiel, da hver funktion kalder to andre funktioner.
Hjælperums kompleksitet: O(n), da den maksimale dybde af rekursionstræet er n.

Dynamisk programmeringstilgang til at finde og udskrive N. Fibonacci-numre:

Overvej rekursionstræet for det 5. Fibonacci-nummer fra ovenstående tilgang:

 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, udføres det samme metodekald flere gange for den samme værdi. Dette kan optimeres ved hjælp af dynamisk programmering. Vi kan undgå det gentagne arbejde udført i rekursionstilgangen ved at gemme de hidtil beregnede Fibonacci-tal.

java tostring
Dynamisk programmeringstilgang til at finde og udskrive N. Fibonacci-numre:

Dynamisk programmeringstilgang til at finde og udskrive N. Fibonacci-numre:

Nedenfor er implementeringen af ​​ovenstående tilgang:

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. ?>>
>
>

Produktion 
34>

Tidskompleksitet : O(n) for givet n
Hjælpeplads : På)

Nth Power of Matrix-tilgang til at finde og udskrive Nth Fibonacci-numre

Denne tilgang bygger på det faktum, at hvis vi n gange multiplicerer matricen M = {{1,1},{1,0}} til sig selv (med andre ord beregner potens(M, n)), så får vi (n) +1) Fibonacci-tal som elementet ved række og kolonne (0, 0) i den resulterende matrix.

  • Hvis n er lige, så er k = n/2:
    • Derfor N. Fibonacci-tal = F(n) = [2*F(k-1) + F(k)]*F(k)
  • Hvis n er ulige, er k = (n + 1)/2:
    • Derfor N. Fibonacci-tal = F(n) = F(k)*F(k) + F(k-1)*F(k-1)

Hvordan virker denne formel?
Formlen kan udledes af matrixligningen.

egin{bmatrix}1 & 1 1 & 0 end{bmatrix}^n = egin{bmatrix}F_{n+1} & F_n F_n & F_{n-1} end{bmatrix}

freddie mercury

Tager vi determinant på begge sider, får vi (-1)n= Fn+1Fn-1– Fn2

Desuden, siden AnENm= An+mfor enhver kvadratisk matrix A kan følgende identiteter udledes (de opnås fra to forskellige koefficienter for matrixproduktet)

FmFn+ Fm-1Fn-1= Fm+n-1 ——————————(1)

Ved at sætte n = n+1 i ligning(1),

FmFn+1+ Fm-1Fn= Fm+n —————————(2)

Sætter m = n i ligning(1).

F2n-1= Fn2+ Fn-12

Sætter m = n i ligning(2)

F2n= (Fn-1+ Fn+1)Fn= (2Fn-1+ Fn)Fn——-

.tif-fil

(Ved at sætte Fn+1 = Fn + Fn-1)

For at få formlen til at blive bevist, skal vi blot gøre følgende

  • Hvis n er lige, kan vi sætte k = n/2
  • Hvis n er ulige, kan vi sætte k = (n+1)/2

Nedenfor er implementeringen af ​​ovenstående tilgang

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> > 
>
>

Produktion 
34>

Tidskompleksitet: O(Log n)
Hjælpeplads: O(Log n), hvis vi betragter funktionskaldsstabelstørrelsen, ellers O(1).


Relaterede artikler:
Store Fibonacci-numre i Java