#practiceLinkDiv { display: ingen !viktigt; }Givet ett nummer n hitta antalet siffror i n'te Fibonacci-tal. De första Fibonacci-talen är 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Exempel:
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.
Rekommenderad praxis n:e siffran i Fibonacci Prova!
A enkel lösning är att hitta n'te Fibonacci-numret och räkna sedan antalet siffror i den. Denna lösning kan leda till spillproblem för stora värden på n.
A direkt väg är att räkna antalet siffror i det n:e Fibonacci-talet med hjälp av nedanstående Binets formel.
java standardparametrar
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
Som nämnts i detta G-Fakta denna formel verkar inte fungera och producerar korrekta Fibonacci-tal på grund av begränsningar av flyttalsaritmetik. Det verkar dock lönsamt att använda denna formel för att hitta antalet siffror i n'te Fibonacci-nummer.
Nedan är implementeringen av ovanstående idé:
objekt i java-programmeringC++
/* C++ program to find number of digits in nth Fibonacci number */ #include
// 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.
# 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# 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.
<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 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 ?> Produktion
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
Tidskomplexitet: O(1)
Hjälputrymme: O(1)
Ett annat tillvägagångssätt (använder faktum att Fibonacci-tal är periodiska):
Fibonacci-sekvensen är periodisk modulo vilket heltal som helst med period lika med 60 (känd som Pisanos period). Det betyder att vi kan beräkna det n:te Fibonaccitalet modulo 10^k för några stora k och sedan använda periodiciteten för att beräkna antalet siffror. Till exempel kan vi beräkna F_n modulo 10^10 och räkna antalet siffror:
F_n_mod = F_n % 10**10
siffror = floor(log10(F_n_mod)) + 1
Nedan är implementeringen av ovanstående tillvägagångssätt:
C++
#include
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)); } }
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)
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)}'); } } }
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)
Produktion
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
Tidskomplexitet: O(nk)
sträng till jsonobject
Hjälputrymme: O(1)
Referenser:
https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number