Kapunk a Fibonacci szám . Az első néhány Fibonacci-szám 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
Meg kell találnunk az adott Fibonacci-szám indexét, azaz ahogy a 8-as Fibonacci-szám a 6-os indexen áll.
Példák:
Input : 13
Output : 7
Input : 34
Output : 9
1. módszer (egyszerű) : Egy egyszerű megközelítés, ha Fibonacci számokat keresünk a megadott Fibonacci számokig, és megszámoljuk az elvégzett iterációk számát.
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. ?> Kimenet
8
2. módszer (képlet alapú)
De itt létre kellett hoznunk az összes Fibonacci-számot egy megadott Fibonacci-számig. De van egy gyors megoldás erre a problémára. Lássuk hogyan! Vegye figyelembe, hogy egy szám naplójának kiszámítása a legtöbb platformon O(1) művelet.
A Fibonacci-számot a következőképpen írják le
F n = 1 / sqrt(5) (pow(an) - pow(bn)), ahol
a = 1/2 (1 + négyzet(5)) és b = 1/2 (1 - négyzet(5))
Ha figyelmen kívül hagyjuk a pow(b n) értéket, amely n nagy értéke miatt nagyon kicsi
n = kör {2,078087 * log(Fn) + 1,672276}
ahol kerek kereket jelent a legközelebbi egész számra.
Alább látható a fenti ötlet megvalósítása.
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. ?> Kimenet
10
Időbeli összetettség : O(1)
Segédtér : O(1)
Megközelítés:
ezt a problémát meg tudjuk oldani az n-edik Fibonacci-szám képletével, amely a következő:
F(n) = (pow((1+sqrt(5))/2 n) - pow((1-sqrt(5))/2 n)) / sqrt(5)
Ezzel a képlettel levezethetjük egy adott Fibonacci-szám indexét. Iterálhatjuk n értékeit, és kiszámolhatjuk a megfelelő Fibonacci-számot a fenti képlet segítségével, amíg nem találunk egy Fibonacci-számot, amely nagyobb vagy egyenlő az adott számmal. Ezen a ponton visszaadhatjuk annak a Fibonacci-számnak az indexét, amely megfelel az adott számnak.
Az alábbiakban bemutatjuk a fenti megközelítés megvalósítását:
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();
Kimenet
The index of 34 is 9
Időbeli összetettség: O(1), mivel csak néhány aritmetikai műveletet tartalmaz.
A tér összetettsége: O(1), mivel csak állandó mennyiségű memóriát használ a változók tárolására.
Ennek a cikknek a közreműködője Aditya Kumar .