logo

TechCodeview

Encontrando o número de dígitos no enésimo número de Fibonacci

Experimente no GfG Practice ' title= #practiceLinkDiv { display: nenhum! Importante; }

Dado um número n, encontre o número de dígitos no enésimo número de Fibonacci. Os primeiros números de Fibonacci são 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Exemplos:  
 

Input : n = 6  
Output : 1  
6'th Fibonacci number is 8 and it has   
1 digit.  
Input : n = 12  
Output : 3  
12'th Fibonacci number is 144 and it has   
3 digits.


 



Prática recomendada enésimo dígito de Fibonacci Experimente!


UM solução simples é encontrar enésimo número de Fibonacci e conte o número de dígitos nele. Esta solução pode levar a problemas de overflow para valores grandes de n.
UM maneira direta é contar o número de dígitos no enésimo número de Fibonacci usando a fórmula de Binet abaixo. 
 

fib(n) = (?n - ?-n) / ?5  
where  
? = (1 + ?5) / 2  
? = (1 - ?5) / 2  
The above formula can be simplified   
fib(n) = round(?n / ?5)   
Here round function indicates nearest integer.  
Count of digits in Fib(n) = Log10Fib(n)  
 = Log10(?n / ?5)  
 = n*Log10(?) - Log10?5  
 = n*Log10(?) - (Log105)/2


Como mencionado em esse G-Fact esta fórmula não parece funcionar e produzir números de Fibonacci corretos devido às limitações da aritmética de ponto flutuante. No entanto, parece viável usar esta fórmula para encontrar a contagem de dígitos no enésimo número de Fibonacci.
Abaixo está a implementação da ideia acima: 
 

C++ 
/* C++ program to find number of digits in nth  Fibonacci number */ #include   using namespace std; // This function returns the number of digits // in nth Fibonacci number after ceiling it // Formula used (n * log(phi) - (log 5) / 2) long long numberOfDigits(long long n) {  if (n == 1)  return 1;  // using phi = 1.6180339887498948  long double d = (n * log10(1.6180339887498948)) -  ((log10(5)) / 2);  return ceil(d); } // Driver program to test the above function int main() {  long long i;  for (i = 1; i <= 10; i++)  cout << 'Number of Digits in F('  << i <<') - '  << numberOfDigits(i) << 'n';  return 0; }
Java 
// Java program to find number of digits in nth // Fibonacci number class GFG  {  // This function returns the number of digits  // in nth Fibonacci number after ceiling it  // Formula used (n * log(phi) - (log 5) / 2)  static double numberOfDigits(double n)  {  if (n == 1)  return 1;    // using phi = 1.6180339887498948  double d = (n * Math.log10(1.6180339887498948)) -  ((Math.log10(5)) / 2);    return Math.ceil(d);  }  // Driver code  public static void main (String[] args)  {  double i;  for (i = 1; i <= 10; i++)  System.out.println('Number of Digits in F('+i+') - '   +numberOfDigits(i));  } } // This code is contributed by Anant Agarwal.
Python3 
# Python program to find  # number of digits in nth  # Fibonacci number import math # storing value of  # golden ratio aka phi phi = (1 + 5**.5) / 2 # function to find number  # of digits in F(n) This  # function returns the number  # of digitsin nth Fibonacci  # number after ceiling it # Formula used (n * log(phi) -  # (log 5) / 2) def numberOfDig (n) : if n == 1 : return 1 return math.ceil((n * math.log10(phi) - .5 * math.log10(5))) // Driver Code for i in range(1 11) : print('Number of Digits in F(' + str(i) + ') - ' + str(numberOfDig(i))) # This code is contributed by SujanDutta
C# 
// C# program to find number of  // digits in nth Fibonacci number using System; class GFG {    // This function returns the number of digits  // in nth Fibonacci number after ceiling it  // Formula used (n * log(phi) - (log 5) / 2)  static double numberOfDigits(double n)  {  if (n == 1)  return 1;    // using phi = 1.6180339887498948  double d = (n * Math.Log10(1.6180339887498948)) -  ((Math.Log10(5)) / 2);    return Math.Ceiling(d);  }  // Driver code  public static void Main ()  {  double i;  for (i = 1; i <= 10; i++)  Console.WriteLine('Number of Digits in F('+ i +') - '  + numberOfDigits(i));  } } // This code is contributed by Nitin Mittal.
JavaScript 
<script>// Javascript program to find number of // digits in nth Fibonacci number // This function returns the // number of digits in nth // Fibonacci number after // ceiling it Formula used // (n * log(phi) - (log 5) / 2) function numberOfDigits(n) {  if (n == 1)  return 1;  // using phi = 1.6180339887498948  let d = (n * Math.log10(1.6180339887498948)) -  ((Math.log10(5)) / 2);  return Math.ceil(d); }  // Driver Code  let i;  for (let i = 1; i <= 10; i++)  document.write(`Number of Digits in F(${i}) - ${numberOfDigits(i)}   
`); // This code is contributed by _saurabh_jaiswal </script>
PHP 
 // PHP program to find number of  // digits in nth Fibonacci number  // This function returns the // number of digits in nth // Fibonacci number after  // ceiling it Formula used  // (n * log(phi) - (log 5) / 2) function numberOfDigits($n) { if ($n == 1) return 1; // using phi = 1.6180339887498948 $d = ($n * log10(1.6180339887498948)) - ((log10(5)) / 2); return ceil($d); } // Driver Code $i; for ($i = 1; $i <= 10; $i++) echo 'Number of Digits in F($i) - '  numberOfDigits($i) 'n'; // This code is contributed by nitin mittal ?>

Saída 
Number of Digits in F(1) - 1 Number of Digits in F(2) - 1 Number of Digits in F(3) - 1 Number of Digits in F(4) - 1 Number of Digits in F(5) - 1 Number of Digits in F(6) - 1 Number of Digits in F(7) - 2 Number of Digits in F(8) - 2 Number of Digits in F(9) - 2 Number of Digits in F(10) - 2

Complexidade de tempo: O(1)
Espaço Auxiliar: O(1)



Outra abordagem (usando o fato de que os números de Fibonacci são periódicos):

A sequência de Fibonacci é módulo periódico qualquer número inteiro com período igual a 60 (conhecido como período de Pisano). Isso significa que podemos calcular o enésimo número de Fibonacci módulo 10 ^ k para algum k grande e então usar a periodicidade para calcular o número de dígitos. Por exemplo, podemos calcular F_n módulo 10^10 e contar o número de dígitos:

F_n_mod = F_n% 10**10
dígitos = piso(log10(F_n_mod)) + 1

Abaixo está a implementação da abordagem acima:



C++ 
#include   using namespace std; long long numberOfDigits(long long n){  int k = 10; // module 10^k  int phi = (1 + sqrt(5)) / 2; //golden ratio    // compute the n-th Fibonacci number modulo 10^k  int a = 0 b = 1;  for (int i = 2; i <= n; i++) {  int c = (a + b) % int(pow(10 k));  a = b;  b = c;  }  int F_n_mod = b;  // compute the number of digits in F_n_mod  int digits = 1;  while (F_n_mod >= 10) {  F_n_mod /= 10;  digits++;  }  return digits; } int main(){  long long i;  for (i = 1; i <= 10; i++)  cout << 'Number of Digits in F('  << i <<') - '  << numberOfDigits(i) << 'n';  return 0; } // This code is contributed by Yash Agarwal(yashagarwal2852002)
Java 
import java.util.*; public class GFG {  public static long numberOfDigits(long n) {  int k = 10; // module 10^k  double phi = (1 + Math.sqrt(5)) / 2; //golden ratio  // compute the n-th Fibonacci number modulo 10^k  int a = 0 b = 1;  for (int i = 2; i <= n; i++) {  int c = (a + b) % (int) Math.pow(10 k);  a = b;  b = c;  }  int F_n_mod = b;  // compute the number of digits in F_n_mod  int digits = 1;  while (F_n_mod >= 10) {  F_n_mod /= 10;  digits++;  }  return digits;  }  public static void main(String[] args) {  long i;  for (i = 1; i <= 10; i++)  System.out.println('Number of Digits in F(' + i + ') - ' + numberOfDigits(i));  } }
Python3 
import math def numberOfDigits(n): k = 10 # Golden ratio (approximately 1.618033988749895) phi = (1 + math.sqrt(5)) / 2 # Compute the n-th Fibonacci number modulo 10^k a b = 0 1 # Start the loop from 2 as we already have F(0) and F(1) for i in range(2 n + 1): c = (a + b) % pow(10 k) # Update the previous Fibonacci numbers for the next iteration a = b b = c F_n_mod = b # Compute the number of digits in F_n_mod # Initialize the digit counter to 1 (as any number has at least one digit) digits = 1 # Keep dividing F_n_mod by 10 until it becomes less than 10 while F_n_mod >= 10: F_n_mod = F_n_mod // 10 # Increment the digit counter digits += 1 # Return the number of digits in the n-th Fibonacci number modulo 10^k return digits # Driver code for i in range(1 11): # Calculate and print the number of digits in F(i) modulo 10^10 print('Number of Digits in F(' + str(i) + ') - ' + str(numberOfDigits(i))) # THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)
C# 
using System; class GFG {  static int NumberOfDigits(long n)  {  int k = 10; // modulo 10^k   // Compute the n-th Fibonacci number modulo 10^k  int a = 0 b = 1;  for (int i = 2; i <= n; i++)  {  int c = (a + b) % (int)Math.Pow(10 k);  a = b;  b = c;  }  int F_n_mod = b;  // Compute the number of digits in F_n_mod  int digits = 1;  while (F_n_mod >= 10)  {  F_n_mod /= 10;  digits++;  }  return digits;  }  static void Main(string[] args)  {  for (long i = 1; i <= 10; i++)  {  Console.WriteLine($'Number of Digits in F({i}) - {NumberOfDigits(i)}');  }  } }
JavaScript 
function numberOfDigits(n) {  let k = 10; // module 10^k  let phi = (1 + Math.sqrt(5)) / 2; // golden ratio  // compute the n-th Fibonacci number modulo 10^k  let a = 0  b = 1;  for (let i = 2; i <= n; i++) {  let c = (a + b) % Math.pow(10 k);  a = b;  b = c;  }  let F_n_mod = b;  // compute the number of digits in F_n_mod  let digits = 1;  while (F_n_mod >= 10) {  F_n_mod = Math.floor(F_n_mod / 10);  digits++;  }  return digits; } // main function let i; for (i = 1; i <= 10; i++)  console.log('Number of Digits in F(' + i + ') - ' + numberOfDigits(i)); // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)

Saída 
Number of Digits in F(1) - 1 Number of Digits in F(2) - 1 Number of Digits in F(3) - 1 Number of Digits in F(4) - 1 Number of Digits in F(5) - 1 Number of Digits in F(6) - 1 Number of Digits in F(7) - 2 Number of Digits in F(8) - 2 Number of Digits in F(9) - 2 Number of Digits in F(10) - 2

Complexidade de tempo: O (nk)

Espaço Auxiliar: O(1)


Referências:  
https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html#section2  
https://en.wikipedia.org/wiki/Fibonacci_number