#practiceLinkDiv { görüntü: yok !önemli; }Verilen bir n sayısı, n'inci Fibonacci Sayılarının basamak sayısını bulun. İlk birkaç Fibonacci sayısı 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Örnekler:
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 basit çözüm bulmaktır n'inci Fibonacci Sayısı ve ardından içindeki basamak sayısını sayın. Bu çözüm, büyük n değerleri için taşma sorunlarına yol açabilir.
A doğrudan yol Aşağıdaki Binet Formülünü kullanarak n'inci Fibonacci sayısının basamak sayısını saymaktır.
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
Bahsedildiği gibi Bu G-Fact, kayan nokta aritmetiğinin sınırlamaları nedeniyle bu formülün işe yaramadığını ve doğru Fibonacci sayılarını üretmediğini gösteriyor. Ancak n'inci Fibonacci sayısının rakam sayısını bulmak için bu formülü kullanmak uygun görünüyor.
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır:
'100 üzerinden 10 kaç'C++
/* 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 ?> Çıkış
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
Zaman Karmaşıklığı: O(1)
Yardımcı Alan: O(1)
Başka Bir Yaklaşım (Fibonacci sayılarının periyodik olduğu gerçeğini kullanarak):
Fibonacci dizisi, periyodu 60'a eşit olan herhangi bir tam sayının periyodik modülüdür (Pisano periyodu olarak bilinir). Bu, bazı büyük k'lar için n'inci Fibonacci sayısını modulo 10^k hesaplayabileceğimiz ve daha sonra basamak sayısını hesaplamak için periyodikliği kullanabileceğimiz anlamına gelir. Örneğin F_n modulo 10^10'u hesaplayabilir ve basamak sayısını sayabiliriz:
F_n_mod = F_n %10**10
rakamlar = kat(log10(F_n_mod)) + 1
Aşağıda yukarıdaki yaklaşımın uygulanması yer almaktadır:
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)
Çıkış
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
Zaman Karmaşıklığı: O(nk)
Yardımcı Alan: O(1)
Referanslar:
https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number