#practiceLinkDiv { display: none !important; }Zadan je broj n. Pronađite broj znamenki u n-tom Fibonaccijevom broju. Prvih nekoliko Fibonaccijevih brojeva je 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Primjeri:
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.
A jednostavno rješenje je pronaći n-ti Fibonaccijev broj a zatim izbrojite broj znamenki u njemu. Ovo rješenje može dovesti do problema s preljevom za velike vrijednosti n.
A izravan način je prebrojati broj znamenki u n-tom Fibonaccijevom broju koristeći donju Binetovu formulu.
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
Kao što je spomenuto u ovaj G-Činjenica, čini se da ova formula ne radi i ne daje točne Fibonaccijeve brojeve zbog ograničenja aritmetike s pomičnim zarezom. Međutim, izgleda održivo koristiti ovu formulu za pronalaženje broja znamenki u n-tom Fibonaccijevom broju.
Ispod je implementacija gornje ideje:
/* 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 ?> Izlaz
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
Vremenska složenost: O(1)
Pomoćni prostor: O(1)
Drugi pristup (koristeći činjenicu da su Fibonaccijevi brojevi periodični):
Fibonaccijev niz je periodičan po modulu bilo kojeg cijelog broja s periodom jednakom 60 (poznato kao Pisanovo razdoblje). To znači da možemo izračunati n-ti Fibonaccijev broj modulo 10^k za neko veliko k i zatim koristiti periodičnost za izračunavanje broja znamenki. Na primjer, možemo izračunati F_n modulo 10^10 i prebrojati broj znamenki:
F_n_mod = F_n % 10**10
znamenke = kat(log10(F_n_mod)) + 1
U nastavku je implementacija gornjeg pristupa:
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)
Izlaz
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
Vremenska složenost: O(nk)
Pomoćni prostor: O(1)
Reference:
https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number