AL-LEA NUMĂR FIBONACCI - TECHCODEVIEW.COM

Dat un număr n , imprimare al n-lea număr Fibonacci .

Numerele Fibonacci sunt numerele din următoarea secvență de numere întregi: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

Exemple:

Intrare : n = 1
numele orașului din SUA

Ieșire: 1

Intrare : n = 9

Ieșire: 3. 4

Intrare : n = 10

Ieșire: 55

Rezolvarea problemelor recomandate [/Tex]cu valori de seminţe şi F_0 = 0

și

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

>    34>

Complexitatea timpului: Pe)
Spațiu auxiliar: O(1)

Abordarea recursiunii pentru a găsi și tipări numerele al-al-lea Fibonacci:

În termeni matematici, succesiunea Fn de numere Fibonacci este definită de relația de recurență: $F_{n} = F_{n-1} + F_{n-2}$ cu valori de seminţe şi și .

Al N-lea număr Fibonacci poate fi găsit folosind relația de recurență prezentată mai sus:

dacă n = 0, apoi returnează 0.
Dacă n = 1, atunci ar trebui să returneze 1.
Pentru n> 1, ar trebui să returneze F_n-1+ F_n-2

Mai jos este implementarea abordării de mai sus:

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

>    34>

Complexitatea timpului: exponențial, deoarece fiecare funcție numește alte două funcții.
Complexitatea spațiului auxiliar: O(n), deoarece adâncimea maximă a arborelui recursiv este n.

Abordare de programare dinamică pentru a găsi și a tipări numerele al-aletele Fibonacci:

Luați în considerare arborele recursiv pentru al 5-lea număr Fibonacci din abordarea de mai sus:

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

Dacă vedeți, același apel de metodă este efectuat de mai multe ori pentru aceeași valoare. Acest lucru poate fi optimizat cu ajutorul programării dinamice. Putem evita munca repetă făcută în abordarea recursiunii prin stocarea numerelor Fibonacci calculate până acum.

Abordare de programare dinamică pentru a găsi și a tipări numerele al-aletele Fibonacci:

Mai jos este implementarea abordării de mai sus:

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

>    34>

Complexitatea timpului : O(n) pentru n dat
Spațiu auxiliar : Pe)

Puterea a N-a a abordării matricei pentru a găsi și tipări a N-a numere Fibonacci

Această abordare se bazează pe faptul că, dacă înmulțim de n ori matricea M = {{1,1},{1,0}} la ea însăși (cu alte cuvinte calculăm puterea(M, n)), atunci obținem (n +1)-al-lea număr Fibonacci ca element de pe rândul și coloana (0, 0) din matricea rezultată.

Dacă n este par, atunci k = n/2:
Prin urmare, al N-lea număr Fibonacci = F(n) = [2*F(k-1) + F(k)]*F(k)
Dacă n este impar, atunci k = (n + 1)/2:
Prin urmare, al N-lea număr Fibonacci = F(n) = F(k)*F(k) + F(k-1)*F(k-1)

Cum funcționează această formulă?
Formula poate fi derivată din ecuația matriceală.

$egin{bmatrix}1 și 1 1 și 0 end{bmatrix}^n = egin{bmatrix}F_{n+1} și F_n F_n și F_{n-1} end{bmatrix}$

matrice dinamică java

Luând determinant de ambele părți, obținem (-1)ⁿ= F_n+1F_n-1– F_n²

Mai mult, din moment ce AⁿA^m= A^n+mpentru orice matrice pătrată A, pot fi derivate următoarele identități (sunt obținute din doi coeficienți diferiți ai produsului matricei)

F_mF_n+ F_m-1F_n-1= F_{m+n-1 —————————(1)}

Punând n = n+1 în ecuația (1),

F_mF_n+1+ F_m-1F_n= F_{m+n ————————–(2)}

Punând m = n în ecuația (1).

F_2n-1= F_n²+ F_n-1²

Punând m = n în ecuația (2)

F_2n= (F_n-1+ F_n+1)F_n= (2F_n-1+ F_n)F_n——–

(Punând Fn+1 = Fn + Fn-1)

Pentru ca formula să fie demonstrată, trebuie pur și simplu să facem următoarele

Dacă n este par, putem pune k = n/2
Dacă n este impar, putem pune k = (n+1)/2

Mai jos este implementarea abordării de mai sus

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

Ieșire

34>

Complexitatea timpului: O(Log n)
Spațiu auxiliar: O(Log n) dacă luăm în considerare dimensiunea stivei de apeluri de funcție, în caz contrar O(1).

Articole similare:
Numere Fibonacci mari în Java