Dado un número n, encuentre el número de dígitos en los n-ésimos números de Fibonacci. Los primeros números de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Ejemplos:
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.
Una solución simple es encontrar el n- ésimo número de Fibonacci y luego contar el número de dígitos que contiene. Esta solución puede conducir a problemas de desbordamiento para valores grandes de n.
Una forma directa es contar el número de dígitos en el n-ésimo número de Fibonacci usando la siguiente fórmula de Binet.
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 se menciona en este G-Fact, esta fórmula no parece funcionar y producir números de Fibonacci correctos debido a las limitaciones de la aritmética de punto flotante. Sin embargo, parece viable usar esta fórmula para encontrar el número de dígitos en el número n de Fibonacci.
A continuación se muestra la implementación de la idea anterior:
C++
/* C++ program to find number of digits in nth
Fibonacci number */
#include<bits/stdc++.h>
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.
PHP
<?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
?>
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)} <br>`);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
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
Referencias:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number
Este artículo es una contribución de Ayush Khanduri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA