Programa para números Fibonacci
Os números de Fibonacci são os números na seguinte seqüência inteira.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …… ..
Em termos matemáticos, a sequência Fn dos números de Fibonacci é definida pela relação de recorrência.
Fn = Fn-1 + Fn-2
com valores de semente
F0 = 0 and F1 = 1.
Dado um número n, imprima o n-ésimo número de Fibonacci.
Exemplos:
Input : n = 2 Output : 1 Input : n = 9 Output : 34
Escreva uma função int fib (int n) que retorna F n . Por exemplo, se n = 0, então fib() deve retornar 0. Se n = 1, então ele deve retornar 1. Para n> 1, ele deve retornar F n-1 + F n-2
For n = 9 Output:34
A seguir estão diferentes métodos para obter o enésimo número de Fibonacci.
Método 1 (Usar recursão)
Um método simples que é uma relação de recorrência matemática de implementação recursiva direta fornecida acima.
//Fibonacci Series using Recursion
#include<bits/stdc++.h>
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 << fib(n);
getchar();
return 0;
}
// This code is contributed
// by Akanksha Rai//Fibonacci Series using Recursion
#include<stdio.h>
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}//Fibonacci Series using Recursion
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(fib(n));
}
}
/* This code is contributed by Rajat Mishra */# Function for nth Fibonacci number
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==0:
return 0
# Second Fibonacci number is 1
elif n==1:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2)
# Driver Program
print(Fibonacci(9))
#This code is contributed by Saket Modi// 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(Fib(n));
}
}
// This code is contributed by Sam007<?php
// Fibonacci Series
// using Recursion
// function returns
// the Fibonacci number
function fib($n)
{
if ($n <= 1)
return $n;
return fib($n - 1) +
fib($n - 2);
}
// Driver Code
$n = 9;
echo fib($n);
// This code is contributed by aj_36
?><script>
//Fibonacci Series using Recursion
let n = 9;
// function returns the Fibonacci number
function fib(n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
//function call
document.write(fib(n));
//This code is contributed by Surbhi Tyagi
</script>Saída
34
Complexidade de tempo: T (n) = T (n-1) + T (n-2) que é exponencial.
Podemos observar que esta implementação faz muito trabalho repetido (veja a seguinte árvore de recursão). Portanto, esta é uma implementação ruim para o enésimo número de Fibonacci.
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)
Espaço extra: O (n) se considerarmos o tamanho da pilha de chamadas de função, caso contrário, O (1).
Método 2 (usar programação dinâmica)
Podemos evitar o trabalho repetido feito no método 1, armazenando os números de Fibonacci calculados até agora.
// C++ program for Fibonacci Series
// using Dynamic Programming
#include<bits/stdc++.h>
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//Fibonacci Series using Dynamic Programming
#include<stdio.h>
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;
}// Fibonacci Series using Dynamic Programming
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 */# 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# 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.<?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.
?><script>
// 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
</script>Saída
34
Método 3 (Método 2 com
otimização de espaço ) Podemos otimizar o espaço usado no método 2 armazenando os dois números anteriores apenas porque isso é tudo de que precisamos para obter o próximo número de Fibonacci em série.
// Fibonacci Series using Space Optimized Method
#include<bits/stdc++.h>
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// Fibonacci Series using Space Optimized Method
#include<stdio.h>
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 program for Fibonacci Series using Space
// Optimized Method
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# 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# 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.<?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.
?><script>
// 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
</script>Saída
34
Complexidade de tempo: O (n)
Espaço extra: O (1)
Método 4 (usando a potência da array {{1, 1}, {1, 0}})
Este outro O (n) que se baseia no fato de que se n vezes multiplicarmos a array M = {{1,1}, {1,0}} para si mesmo (em outras palavras, calcule a potência (M, n)), então obtemos o (n + 1) o número de Fibonacci como o elemento na linha e coluna (0, 0) na array resultante.
A representação da array fornece a seguinte expressão fechada para os números de Fibonacci:
#include<bits/stdc++.h>
using namespace std;
// Helper function that multiplies 2
// matrices F and M of size 2*2, and
// puts the multiplication result
// back to F[][]
void multiply(int F[2][2], int M[2][2]);
// Helper function that calculates F[][]
// raise to the power n and puts the
// result in F[][]
// Note that this function is designed
// only for fib() and won't work as
// general power function
void power(int F[2][2], int n);
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];
}
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;
}
void power(int F[2][2], int n)
{
int i;
int M[2][2] = { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the
// matrix to {{1,0},{0,1}}
for(i = 2; i <= n; i++)
multiply(F, M);
}
// Driver code
int main()
{
int n = 9;
cout << " " << fib(n);
return 0;
}
// This code is contributed by shivanisinghss2110#include <stdio.h>
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
void power(int F[2][2], int n);
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];
}
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;
}
void power(int F[2][2], int n)
{
int i;
int M[2][2] = {{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}class fibonacci
{
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];
}
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
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;
}
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][]{{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
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 */# Helper function that multiplies
# 2 matrices F and M of size 2*2,
# and puts the multiplication
# result back to F[][]
# Helper function that calculates
# F[][] raise to the power n and
# puts the result in F[][]
# Note that this function is
# designed only for fib() and
# won't work as general
# power function
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
def power(F, n):
M = [[1, 1],
[1, 0]]
# n - 1 times multiply the
# matrix to {{1,0},{0,1}}
for i in range(2, n + 1):
multiply(F, M)
# Driver Code
if __name__ == "__main__":
n = 9
print(fib(n))
# This code is contributed
# by ChitraNayalusing System;
class GFG {
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];
}
/* Helper function that multiplies 2
matrices F and M of size 2*2, and puts
the multiplication result back to F[][] */
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;
}
/* Helper function that calculates F[][]
raise to the power n and puts the result
in F[][] Note that this function is designed
only for fib() and won't work as general
power function */
static void power(int [,]F, int n)
{
int i;
int [,]M = new int[,]{{1, 1},
{1, 0} };
// n - 1 times multiply the matrix to
// {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
public static void Main ()
{
int n = 9;
Console.WriteLine(fib(n));
}
}
// This code is contributed by anuj_67.<?php
function fib($n)
{
$F = array(array(1, 1),
array(1, 0));
if ($n == 0)
return 0;
power($F, $n - 1);
return $F[0][0];
}
function 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;
}
function power(&$F, $n)
{
$M = array(array(1, 1),
array(1, 0));
// n - 1 times multiply the
// matrix to {{1,0},{0,1}}
for ($i = 2; $i <= $n; $i++)
multiply($F, $M);
}
// Driver Code
$n = 9;
echo fib($n);
// This code is contributed
// by ChitraNayal
?><script>
// Note that this function is designed
// only for fib() and won't work as
// general power function
function fib( n)
{
var F = [ [ 1, 1 ], [ 1, 0 ] ];
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
// Helper function that multiplies 2
// matrices F and M of size 2*2, and
// puts the multiplication result
// back to F[][]
function 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;
}
// Helper function that calculates F[][]
// raise to the power n and puts the
// result in F[][]
function power( F, n)
{
var i;
var M = [[ 1, 1 ], [ 1, 0 ]];
// n - 1 times multiply the
// matrix to {{1,0},{0,1}}
for(i = 2; i <= n; i++)
multiply(F, M);
}
// Driver code
var n = 9;
document.write (" " + fib(n));
//This code is contributed by sweetyty
</script>Saída
34
Complexidade de tempo: O (n)
Espaço extra: O (1)
Método 5 (Método 4 otimizado)
O método 4 pode ser otimizado para trabalhar em complexidade de tempo O (Logn). Podemos fazer multiplicação recursiva para obter potência (M, n) no método anterior (semelhante à otimização feita neste post)
// Fibonacci Series using Optimized Method
#include <bits/stdc++.h>
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#include <stdio.h>
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;
}//Fibonacci Series using Optimized Method
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 */# 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// 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<script>
// 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 || n == 1)
return;
var M = [ [ 1, 1 ], [ 1, 0 ] ];
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
// Driver code
var n = 9;
document.write(fib(n));
// This code is contributed by gauravrajput1
</script>Saída
34
Complexidade de tempo: O (Logn)
Espaço extra: O (Logn) se considerarmos o tamanho da pilha de chamadas de função, caso contrário, O (1).
Método 6 (Tempo O (Log n))
Abaixo está mais uma fórmula de recorrência interessante que pode ser usada para encontrar o enésimo número de Fibonacci no tempo O (Log n).
If n is even then k = n/2: F(n) = [2*F(k-1) + F(k)]*F(k) If n is odd then k = (n + 1)/2 F(n) = F(k)*F(k) + F(k-1)*F(k-1)
Como essa fórmula funciona?
A fórmula pode ser derivada da equação da array acima.
Taking determinant on both sides, we get (-1)n = Fn+1Fn-1 - Fn2 Moreover, since AnAm = An+m for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product) FmFn + Fm-1Fn-1 = Fm+n-1 ---------------------------(1) By putting n = n+1 in equation(1), FmFn+1 + Fm-1Fn = Fm+n --------------------------(2) Putting m = n in equation(1). F2n-1 = Fn2 + Fn-12 Putting m = n in equation(2) F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (Source: Wiki) -------- ( By putting Fn+1 = Fn + Fn-1 ) To get the formula to be proved, we simply need to do the following If n is even, we can put k = n/2 If n is odd, we can put k = (n+1)/2
Abaixo está a implementação da ideia acima.
// C++ Program to find n'th fibonacci Number in
// with O(Log n) arithmetic operations
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Create an array for memoization
int f[MAX] = {0};
// Returns n'th fibonacci number using table f[]
int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
// If fib(n) is already computed
if (f[n])
return f[n];
int k = (n & 1)? (n+1)/2 : n/2;
// Applying above formula [Note value n&1 is 1
// if n is odd, else 0.
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
: (2*fib(k-1) + fib(k))*fib(k);
return f[n];
}
/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d ", fib(n));
return 0;
}// Java Program to find n'th fibonacci
// Number with O(Log n) arithmetic operations
import java.util.*;
class GFG {
static int MAX = 1000;
static int f[];
// Returns n'th fibonacci number using
// table f[]
public static int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
// If fib(n) is already computed
if (f[n] != 0)
return f[n];
int k = (n & 1) == 1? (n + 1) / 2
: n / 2;
// Applying above formula [Note value
// n&1 is 1 if n is odd, else 0.
f[n] = (n & 1) == 1? (fib(k) * fib(k) +
fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k))
* fib(k);
return f[n];
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 9;
f= new int[MAX];
System.out.println(fib(n));
}
}
// This code is contributed by Arnav Kr. Mandal.# Python3 Program to find n'th fibonacci Number in
# with O(Log n) arithmetic operations
MAX = 1000
# Create an array for memoization
f = [0] * MAX
# Returns n'th fibonacci number using table f[]
def fib(n) :
# Base cases
if (n == 0) :
return 0
if (n == 1 or n == 2) :
f[n] = 1
return (f[n])
# If fib(n) is already computed
if (f[n]) :
return f[n]
if( n & 1) :
k = (n + 1) // 2
else :
k = n // 2
# Applying above formula [Note value n&1 is 1
# if n is odd, else 0.
if((n & 1) ) :
f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
else :
f[n] = (2*fib(k-1) + fib(k))*fib(k)
return f[n]
# Driver code
n = 9
print(fib(n))
# This code is contributed by Nikita Tiwari.// C# Program to find n'th
// fibonacci Number with
// O(Log n) arithmetic operations
using System;
class GFG
{
static int MAX = 1000;
static int[] f;
// Returns n'th fibonacci
// number using table f[]
public static int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
// If fib(n) is already
// computed
if (f[n] != 0)
return f[n];
int k = (n & 1) == 1 ? (n + 1) / 2
: n / 2;
// Applying above formula
// [Note value n&1 is 1 if
// n is odd, else 0.
f[n] = (n & 1) == 1 ? (fib(k) * fib(k) +
fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k)) *
fib(k);
return f[n];
}
// Driver Code
static void Main()
{
int n = 9;
f = new int[MAX];
Console.WriteLine(fib(n));
}
}
// This code is contributed by mits<?php
// PHP Program to find n'th
// fibonacci Number in with
// O(Log n) arithmetic operations
$MAX = 1000;
// Returns n'th fibonacci
// number using table f[]
function fib($n)
{
global $MAX;
// Create an array for memoization
$f = array_fill(0, $MAX, NULL);
// Base cases
if ($n == 0)
return 0;
if ($n == 1 || $n == 2)
return ($f[$n] = 1);
// If fib(n) is already computed
if ($f[$n])
return $f[$n];
$k = ($n & 1) ? ($n + 1) / 2 : $n / 2;
// Applying above formula
// [Note value n&1 is 1 if
// n is odd, else 0.
$f[$n] = ($n & 1) ? (fib($k) * fib($k) +
fib($k - 1) * fib($k - 1)) :
(2 * fib($k - 1) + fib($k)) * fib($k);
return $f[$n];
}
// Driver Code
$n = 9;
echo fib($n);
// This code is contributed
// by ChitraNayal
?><script>
// JavaScript Program to find n'th fibonacci Number in
// with O(Log n) arithmetic operations
const MAX = 1000;
// Create an array for memoization
var f = [...Array(MAX)];
f.fill(0);
// Returns n'th fibonacci number using table f[]
function fib(n) {
// Base cases
if (n == 0) return 0;
if (n == 1 || n == 2) return (f[n] = 1);
// If fib(n) is already computed
if (f[n]) return f[n];
var k = n & 1 ? (n + 1) / 2 : n / 2;
// Applying above formula [Note value n&1 is 1
// if n is odd, else 0.
f[n] =
n & 1
? fib(k) * fib(k) + fib(k - 1) * fib(k - 1)
: (2 * fib(k - 1) + fib(k)) * fib(k);
return f[n];
}
/* Driver program to test above function */
var n = 9;
document.write(fib(n));
// This code is contributed by rdtank.
</script>Saída
34
A complexidade de tempo dessa solução é O (Log n), pois dividimos o problema pela metade em cada chamada recursiva.
Método 7
Outra abordagem (usando a fórmula):
neste método, implementamos diretamente a fórmula para o enésimo termo na série de Fibonacci.
F n = {[(√5 + 1) / 2] ^ n} / √5
Referência: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
// C++ Program to find n'th fibonacci Number
#include<iostream>
#include<cmath>
int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}
// Driver Code
int main ()
{
int n = 9;
std::cout << fib(n) << std::endl;
return 0;
}
//This code is contributed by Lokesh Mohanty.// C Program to find n'th fibonacci Number
#include<stdio.h>
#include<math.h>
int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}
int main ()
{
int n = 9;
printf("%d", fib(n));
return 0;
}// Java Program to find n'th fibonacci Number
import java.util.*;
class GFG {
static int fib(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n)
/ Math.sqrt(5));
}
// Driver Code
public static void main(String[] args) {
int n = 9;
System.out.println(fib(n));
}
}
// This code is contributed by PrinciRaj1992# Python3 program to find n'th
# fibonacci Number
import math
def fibo(n):
phi = (1 + math.sqrt(5)) / 2
return round(pow(phi, n) / math.sqrt(5))
# Driver code
if __name__ == '__main__':
n = 9
print(fibo(n))
# This code is contributed by prasun_parate// C# Program to find n'th fibonacci Number
using System;
public class GFG
{
static int fib(int n)
{
double phi = (1 + Math.Sqrt(5)) / 2;
return (int) Math.Round(Math.Pow(phi, n)
/ Math.Sqrt(5));
}
// Driver code
public static void Main()
{
int n = 9;
Console.WriteLine(fib(n));
}
}
// This code is contributed by 29AjayKumar<?php
// PHP Program to find n'th
// fibonacci Number
function fib($n)
{
$phi = (1 + sqrt(5)) / 2;
return round(pow($phi, $n) / sqrt(5));
}
// Driver Code
$n = 9;
echo fib($n) ;
// This code is contributed by Ryuga
?><script>
// Javascript Program to find n'th fibonacci Number
function fib(n) {
let phi = (1 + Math.sqrt(5)) / 2;
return Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
let n = 9;
document.write(fib(n));
// This code is contributed by mukesh07.
</script>Saída
34
Complexidade de tempo: O (logn), isso ocorre porque o cálculo de phi ^ n leva tempo logn
Complexidade de espaço: O (1)
Método 8
DP usando memoização (abordagem de cima para baixo)
Podemos evitar o trabalho repetido realizado no método 1, armazenando os números de Fibonacci calculados até agora. Precisamos apenas armazenar todos os valores em um array.
#include <bits/stdc++.h>
using namespace std;
int dp[10];
int fib(int n)
{
if (n <= 1)
return n;
// temporary variables to store
// values of fib(n-1) & fib(n-2)
int first, second;
if (dp[n - 1] != -1)
first = dp[n - 1];
else
first = fib(n - 1);
if (dp[n - 2] != -1)
second = dp[n - 2];
else
second = fib(n - 2);
// memoization
return dp[n] = first + second;
}
// Driver Code
int main()
{
int n = 9;
memset(dp, -1, sizeof(dp));
cout << fib(n);
getchar();
return 0;
// This code is contributed by Bhavneet Singh
}import java.util.*;
class GFG{
// Initialize array of dp
static int[] dp = new int[10];
static int fib(int n)
{
if (n <= 1)
return n;
// Temporary variables to store
// values of fib(n-1) & fib(n-2)
int first, second;
if (dp[n - 1] != -1)
first = dp[n - 1];
else
first = fib(n - 1);
if (dp[n - 2] != -1)
second = dp[n - 2];
else
second = fib(n - 2);
// Memoization
return dp[n] = first + second;
}
// Driver Code
public static void main(String[] args)
{
int n = 9;
Arrays.fill(dp, -1);
System.out.print(fib(n));
}
}
// This code is contributed by sujitmeshram# Initialize array of dp
dp = [-1 for i in range(10)]
def fib(n):
if (n <= 1):
return n;
global dp;
# Temporary variables to store
# values of fib(n-1) & fib(n-2)
first = 0;
second = 0;
if (dp[n - 1] != -1):
first = dp[n - 1];
else:
first = fib(n - 1);
if (dp[n - 2] != -1):
second = dp[n - 2];
else:
second = fib(n - 2);
dp[n] = first + second;
# Memoization
return dp[n] ;
# Driver Code
if __name__ == '__main__':
n = 9;
print(fib(n));
# This code contributed by Rajput-Jiusing System;
class GFG {
// Initialize array of dp
static int[] dp = new int[10];
static int fib(int n)
{
if (n <= 1)
return n;
// Temporary variables to store
// values of fib(n-1) & fib(n-2)
int first, second;
if (dp[n - 1] != -1)
first = dp[n - 1];
else
first = fib(n - 1);
if (dp[n - 2] != -1)
second = dp[n - 2];
else
second = fib(n - 2);
// Memoization
return dp[n] = first + second;
}
// Driver code
static void Main()
{
int n = 9;
Array.Fill(dp, -1);
Console.Write(fib(n));
}
}
// This code is contributed by divyeshrabadiya07.<script>
// Initialize array of dp
dp = Array.from({length: 10}, (_, i) => -1);
function fib(n)
{
if (n <= 1)
return n;
// Temporary variables to store
// values of fib(n-1) & fib(n-2)
var first, second;
if (dp[n - 1] != -1)
first = dp[n - 1];
else
first = fib(n - 1);
if (dp[n - 2] != -1)
second = dp[n - 2];
else
second = fib(n - 2);
// Memoization
return dp[n] = first + second;
}
// Driver Code
var n = 9;
document.write(fib(n));
// This code is contributed by Amit Katiyar
</script>Saída
34
https://www.youtube.com/watch?v=LwZRsM7qhrI
Este método é contribuído por Chirag Agarwal.
Artigos relacionados:
Números de Fibonacci grandes em Java
Por favor, escreva comentários se você achar os códigos / algoritmos acima incorretos ou encontrar outras maneiras de resolver o mesmo problema.
Referências:
http://en.wikipedia.org/wiki/Fibonacci_number
http://www.ics.uci.edu/~eppstein/161/960109.html
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
