#practiceLinkDiv { 표시: 없음 !중요; }숫자 n이 주어지면 n번째 피보나치 수열의 자릿수를 찾습니다. 처음 몇 개의 피보나치 수는 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
예:
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.
에이 간단한 해결책 찾는 것이다 n번째 피보나치 수 그런 다음 그 안에 있는 자릿수를 셉니다. 이 솔루션은 큰 n 값에 대해 오버플로 문제를 일으킬 수 있습니다.
에이 직접적인 방법 아래의 비네 공식을 이용하여 n번째 피보나치 수의 자릿수를 세는 것입니다.
자바 이런 개념
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
에서 언급했듯이 이것 G-사실 이 공식은 부동 소수점 산술의 한계로 인해 작동하지 않고 올바른 피보나치 수를 생성하지 않는 것 같습니다. 그러나 이 공식을 사용하여 n번째 피보나치 수의 자릿수를 찾는 것이 가능해 보입니다.
다음은 위의 아이디어를 구현한 것입니다.
자바 클래스 다이어그램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 ?> 산출
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
시간 복잡도: O(1)
보조 공간: O(1)
또 다른 접근법(피보나치 수가 주기적이라는 사실을 사용):
피보나치 수열은 주기가 60인 임의의 정수 모듈로 주기적인 수열입니다(피사노 주기라고도 함). 이는 일부 큰 k에 대해 n번째 피보나치 수 모듈로 10^k를 계산한 다음 주기성을 사용하여 자릿수를 계산할 수 있음을 의미합니다. 예를 들어 F_n 모듈로 10^10을 계산하고 자릿수를 계산할 수 있습니다.
F_n_mod = F_n % 10**10
숫자 = 바닥(log10(F_n_mod)) + 1
다음은 위의 접근 방식을 구현한 것입니다.
세계 최고의 자동차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)
산출
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
시간 복잡도: O(nk)
보조 공간: O(1)
참고자료:
https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number