私たちに与えられているのは、 フィボナッチ数 。最初のいくつかのフィボナッチ数は 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) 操作であることに注意してください。
フィボナッチ数は次のように記述されます。
F n = 1 / sqrt(5) (pow(an) - pow(bn)) ここで、
a = 1 / 2 ( 1 + sqrt(5) ) および b = 1 / 2 ( 1 - sqrt(5) )
n の値が大きいため非常に小さい pow(b n) を無視すると、次のようになります。
n = 丸め { 2.078087 * log(Fn) + 1.672276 }
どこ ラウンド 最も近い整数に丸めることを意味します。
以下は上記のアイデアを実装したものです。
CSS画像を整列させる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
時間計算量 :O(1)
補助スペース :O(1)
アプローチ：
この問題は、次の n 番目のフィボナッチ数の公式を使用して解決できます。
F(n) = (pow((1+sqrt(5))/2 n) - pow((1-sqrt(5))/2 n)) / 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) は、変数を格納するために一定量のメモリのみを使用するためです。
この記事は次の寄稿者です アディティア・クマール 。
Javaのランダム値ジェネレータークイズの作成