우리는 피보나치 수 . 처음 몇 개의 피보나치 수는 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
우리는 주어진 피보나치 수의 인덱스를 찾아야 합니다. 즉, 피보나치 수 8이 인덱스 6에 있는 것과 같습니다.
예:
Input : 13
Output : 7
Input : 34
Output : 9
방법 1(간단) : 간단한 접근 방식은 주어진 피보나치 수까지 피보나치 수를 찾고 수행된 반복 횟수를 계산하는 것입니다.
C++
// A simple C++ program to find index of given // Fibonacci number. #include
// A simple Java program to find index of // given Fibonacci number. import java.io.*; class GFG { static int findIndex(int n) { // if Fibonacci number is less // than 2 its index will be // same as number if (n <= 1) return n; int a = 0 b = 1 c = 1; int res = 1; // iterate until generated fibonacci // number is less than given // fibonacci number while (c < n) { c = a + b; // res keeps track of number of // generated fibonacci number res++; a = b; b = c; } return res; } // Driver program to test above function public static void main (String[] args) { int result = findIndex(21); System.out.println( result); } } // This code is contributed by anuj_67.
# A simple Python 3 program to find # index of given Fibonacci number. def findIndex(n) : # if Fibonacci number is less than 2 # its index will be same as number if (n <= 1) : return n a = 0 b = 1 c = 1 res = 1 # iterate until generated fibonacci number # is less than given fibonacci number while (c < n) : c = a + b # res keeps track of number of # generated fibonacci number res = res + 1 a = b b = c return res # Driver program to test above function result = findIndex(21) print(result) # this code is contributed by Nikita Tiwari
// A simple C# program to // find index of given // Fibonacci number. using System; class GFG { static int findIndex(int n) { // if Fibonacci number // is less than 2 its // index will be same // as number if (n <= 1) return n; int a = 0 b = 1 c = 1; int res = 1; // iterate until generated // fibonacci number is less // than given fibonacci number while (c < n) { c = a + b; // res keeps track of // number of generated // fibonacci number res++; a = b; b = c; } return res; } // Driver Code public static void Main () { int result = findIndex(21); Console.WriteLine(result); } } // This code is contributed // by anuj_67.
<script> // A simple Javascript program to // find index of given // Fibonacci number. function findIndex(n) { // If Fibonacci number // is less than 2 its // index will be same // as number if (n <= 1) return n; let a = 0 b = 1 c = 1; let res = 1; // Iterate until generated // fibonacci number is less // than given fibonacci number while (c < n) { c = a + b; // res keeps track of // number of generated // fibonacci number res++; a = b; b = c; } return res; } // Driver code let result = findIndex(21); document.write(result); // This code is contributed by decode2207 </script>
// A simple PHP program to // find index of given // Fibonacci number. function findIndex($n) { // if Fibonacci number // is less than 2 // its index will be // same as number if ($n <= 1) return $n; $a = 0; $b = 1; $c = 1; $res = 1; // iterate until generated // fibonacci number // is less than given // fibonacci number while ($c < $n) { $c = $a + $b; // res keeps track of // number of generated // fibonacci number $res++; $a = $b; $b = $c; } return $res; } // Driver Code $result = findIndex(21); echo($result); // This code is contributed by Ajit. ?> 산출
8
방법 2(수식 기반)
하지만 여기서는 제공된 피보나치 수까지 모든 피보나치 수를 생성해야 했습니다. 하지만 이 문제에 대한 빠른 해결책이 있습니다. 방법을 보자! 숫자의 로그를 계산하는 것은 대부분의 플랫폼에서 O(1) 작업입니다.
피보나치 수는 다음과 같이 설명됩니다.
에프 n = 1 / sqrt(5) (pow(an) - pow(bn)) 여기서
a = 1/2( 1 + sqrt(5) ) 및 b = 1/2( 1 - sqrt(5) )
n의 값이 크기 때문에 매우 작은 pow(bn)을 무시하면 다음과 같은 결과를 얻을 수 있습니다.
n = 라운드 { 2.078087 * log(Fn) + 1.672276 }
어디 둥근 가장 가까운 정수로 반올림하는 것을 의미합니다.
아래는 위의 아이디어를 구현한 것입니다.
C++// C++ program to find index of given Fibonacci // number #include
// A simple Java program to find index of given // Fibonacci number public class Fibonacci { static int findIndex(int n) { float fibo = 2.078087F * (float) Math.log(n) + 1.672276F; // returning rounded off value of index return Math.round(fibo); } public static void main(String[] args) { int result = findIndex(55); System.out.println(result); } }
# Python 3 program to find index of given Fibonacci # number import math def findIndex(n) : fibo = 2.078087 * math.log(n) + 1.672276 # returning rounded off value of index return round(fibo) # Driver program to test above function n = 21 print(findIndex(n)) # This code is contributed by Nikita Tiwari.
// A simple C# program to find // index of given Fibonacci number using System; class Fibonacci { static int findIndex(int n) { float fibo = 2.078087F * (float) Math.Log(n) + 1.672276F; // returning rounded off value of index return (int)(Math.Round(fibo)); } // Driver code public static void Main() { int result = findIndex(55); Console.Write(result); } } // This code is contributed by nitin mittal
<script> // A simple Javascript program to find // index of given Fibonacci number function findIndex(n) { var fibo = 2.078087 * parseFloat(Math.log(n)) + 1.672276; // Returning rounded off value of index return Math.round(fibo); } // Driver code var result = findIndex(55); document.write(result); // This code is contributed by Ankita saini </script>
// PHP program to find index // of given Fibonacci Number function findIndex($n) { $fibo = 2.078087 * log($n) + 1.672276; // returning rounded off // value of index return round($fibo); } // Driver code $n = 55; echo(findIndex($n)); // This code is contributed by Ajit. ?> 산출
10
시간 복잡도 : ㅇ(1)
보조 공간 : ㅇ(1)
접근하다:
n번째 피보나치 수에 대한 공식을 사용하여 이 문제를 해결할 수 있습니다.
F(n) = (pow((1+sqrt(5))/2n) - pow((1-sqrt(5))/2n)) / sqrt(5)
이 공식을 사용하여 주어진 피보나치 수의 지수를 유도할 수 있습니다. 주어진 숫자보다 크거나 같은 피보나치 수를 찾을 때까지 n 값을 반복하고 위 공식을 사용하여 해당 피보나치 수를 계산할 수 있습니다. 이 시점에서 우리는 주어진 숫자와 일치하는 피보나치 수의 인덱스를 반환할 수 있습니다.
다음은 위의 접근 방식을 구현한 것입니다.
C++#include
//Java code for the above approach import java.util.*; public class FibonacciIndex { public static int findIndex(int n) { double phi = (1 + Math.sqrt(5)) / 2; int index = (int) Math.round(Math.log(n * Math.sqrt(5) + 0.5) / Math.log(phi)); int fib = (int) Math.round((Math.pow(phi index) - Math.pow(1 - phi index)) / Math.sqrt(5)); if (fib == n) return index; else return -1; // n is not a Fibonacci number } public static void main(String[] args) { int n = 34; int index = findIndex(n); System.out.println('The index of ' + n + ' is ' + index); } }
import math def find_index(n): phi = (1 + math.sqrt(5)) / 2 index = round(math.log(n * math.sqrt(5) + 0.5) / math.log(phi)) fib = round((math.pow(phi index) - math.pow(1 - phi index)) / math.sqrt(5)) if fib == n: return index else: return -1 # n is not a Fibonacci number def main(): n = 34 index = find_index(n) print(f'The index of {n} is {index}') if __name__ == '__main__': main()
using System; class Program { // Function to find the index of a number in the Fibonacci sequence static int FindIndex(int n) { double phi = (1 + Math.Sqrt(5)) / 2; // Golden ratio // Calculate the index using the formula for Fibonacci numbers int index = (int)Math.Round(Math.Log(n * Math.Sqrt(5) + 0.5) / Math.Log(phi)); // Calculate the Fibonacci number at the found index int fib = (int)Math.Round((Math.Pow(phi index) - Math.Pow(1 - phi index)) / Math.Sqrt(5)); // Check if the calculated Fibonacci number is equal to n if (fib == n) return index; else return -1; // n is not a Fibonacci number } static void Main() { int n = 34; int index = FindIndex(n); Console.WriteLine('The index of ' + n + ' is ' + index); } }
// Function to find the index of a number in the Fibonacci sequence function findIndex(n) { const phi = (1 + Math.sqrt(5)) / 2; const index = Math.round(Math.log(n * Math.sqrt(5) + 0.5) / Math.log(phi)); const fib = Math.round((Math.pow(phi index) - Math.pow(1 - phi index)) / Math.sqrt(5)); if (fib === n) { return index; } else { return -1; // n is not a Fibonacci number } } // Main function to test the findIndex function function main() { const n = 34; const index = findIndex(n); console.log('The index of ' + n + ' is ' + index); } main();
산출
The index of 34 is 9
시간 복잡도: O(1) 몇 가지 산술 연산만 필요하기 때문입니다.
공간 복잡도: O(1) 변수를 저장하는 데 일정한 양의 메모리만 사용하기 때문입니다.
이 기사는 기고자: 아디트야 쿠마르 .