N-ASIS FIBONAČIO NUMERIS – TECHCODEVIEW.COM

Duotas skaičius n , spausdinti n-asis Fibonačio skaičius .

Fibonačio skaičiai yra skaičiai šioje sveikųjų skaičių sekoje: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….

Pavyzdžiai:

Įvestis: n = 1

Išvestis: 1

Įvestis: n = 9

Išvestis: 3. 4

Įvestis: n = 10

Išvestis: 55

Rekomenduojama problemos sprendimo problema [/Tex]su sėklų vertėmis ir F_0 = 0

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>

Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)

lapė prieš vilką

N-ojo Fibonačio numerių radimo ir spausdinimo rekursinis metodas:

Matematine prasme Fibonačio skaičių seka Fn apibrėžiama pasikartojimo ryšiu: $F_{n} = F_{n-1} + F_{n-2}$ su sėklų vertėmis ir ir .

N-ąjį Fibonačio skaičių galima rasti naudojant aukščiau pateiktą pasikartojimo ryšį:

jeigu n = 0, tada grąžinkite 0.
Jei n = 1, tada jis turėtų grąžinti 1.
Jei n> 1, jis turėtų grąžinti F_n-1+ F_n-2

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

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>

Laiko sudėtingumas: eksponentinis, kaip kiekviena funkcija iškviečia dvi kitas funkcijas.
Pagalbinės erdvės sudėtingumas: O(n), nes didžiausias rekursijos medžio gylis yra n.

sveikasis skaičius į eilutę Java

Dinaminio programavimo metodas N-tiesiems Fibonačio skaičiams rasti ir spausdinti:

Apsvarstykite 5-ojo Fibonačio skaičiaus rekursijos medį pagal aukščiau pateiktą metodą:

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

Jei matote, tas pats metodas iškviečiamas kelis kartus tai pačiai vertei. Tai galima optimizuoti dinaminio programavimo pagalba. Mes galime išvengti pakartotinio darbo, atlikto taikant rekursijos metodą, išsaugodami iki šiol apskaičiuotus Fibonačio skaičius.

Dinaminio programavimo metodas N-tiesiems Fibonačio skaičiams rasti ir spausdinti:

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

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>

Laiko sudėtingumas : O(n) duotam n
Pagalbinė erdvė : O(n)

N-oji matricos metodo galia ieškant ir atspausdinant N-ąjį Fibonačio skaičių

Šis metodas remiasi tuo, kad jei matricą M = {{1,1},{1,0}} n kartų padauginsime iš jos pačios (kitaip tariant, apskaičiuosime galią(M, n)), tada gausime (n +1) Fibonačio skaičius kaip elementas gautos matricos eilutėje ir stulpelyje (0, 0).

Jei n lygus, tada k = n/2:
Todėl N-asis Fibonačio skaičius = F(n) = [2*F(k-1) + F(k)]*F(k)
Jei n nelyginis, tada k = (n + 1)/2:
Todėl N-asis Fibonačio skaičius = F(n) = F(k)*F(k) + F(k-1)*F(k-1)

Kaip ši formulė veikia?
Formulę galima išvesti iš matricos lygties.

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

Paėmę determinantą iš abiejų pusių, gauname (-1)ⁿ= F_n+1F_n-1– F_n²
c# jungiklis

Be to, kadangi AⁿA^m= A^n+mbet kuriai kvadratinei matricai A galima nustatyti tokias tapatybes (jie gaunami iš dviejų skirtingų matricos sandaugos koeficientų)

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

Į (1) lygtį įdėjus n = n+1,

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

Įdėjus m = n į lygtį (1).

F_2n-1= F_n²+ F_n-1²

m = n įtraukimas į (2) lygtį

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

(Įdėjus Fn+1 = Fn + Fn-1 )

Kad formulė būtų įrodyta, tiesiog reikia atlikti šiuos veiksmus

Jei n lygus, galime pateikti k = n/2
Jei n nelyginis, galime pateikti k = (n+1)/2

Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas

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

Išvestis

34>

Laiko sudėtingumas: O (Žurnalas n)
Pagalbinė erdvė: O(Log n), jei atsižvelgsime į funkcijos iškvietimo krūvos dydį, kitu atveju O(1).

Susiję straipsniai:
Dideli Fibonačio skaičiai Java