Vi får en Fibonacci nummer . De første par Fibonacci-tal er 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
Vi skal finde indekset for det givne Fibonacci-tal, dvs. ligesom Fibonacci-nummer 8 er på indeks 6.
Eksempler:
Input : 13
Output : 7
Input : 34
Output : 9
Metode 1 (simpel) : En simpel tilgang er at finde Fibonacci-tal op til de givne Fibonacci-tal og tælle antallet af udførte iterationer.
java mainC++
// 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. ?> Produktion
8
Metode 2 (formelbaseret)
Men her skulle vi generere alle Fibonacci-tallene op til et givet Fibonacci-tal. Men der er en hurtig løsning på dette problem. Lad os se hvordan! Bemærk, at beregning af loggen for et tal er en O(1)-operation på de fleste platforme.
Fibonacci-tallet beskrives som
F n = 1 / sqrt(5) (pow(an) - pow(bn)) hvor
a = 1/2 ( 1 + sqrt(5) ) og b = 1/2 ( 1 - sqrt(5) )
Ved at negligere pow(b n), som er meget lille på grund af den store værdi af n, vi får
n = rund { 2,078087 * log(Fn) + 1,672276 }
hvor rund betyder rund til nærmeste heltal.
Nedenfor er implementeringen af ovenstående idé.
hardcover vs paperbackC++
// 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. ?> Produktion
10
Tidskompleksitet : O(1)
Hjælpeplads : O(1)
Nærme sig:
vi kan løse dette problem ved at bruge formlen for det n'te Fibonacci-tal, som er:
F(n) = (pow((1+sqrt(5))/2 n) - pow((1-sqrt(5))/2 n)) / sqrt(5)
knap i center css
Vi kan udlede indekset for et givet Fibonacci-tal ved hjælp af denne formel. Vi kan iterere over værdierne af n og beregne det tilsvarende Fibonacci-tal ved hjælp af ovenstående formel, indtil vi finder et Fibonacci-tal, der er større end eller lig med det givne tal. På dette tidspunkt kan vi returnere indekset for Fibonacci-tallet, der matcher det givne tal.
Nedenfor er implementeringen af ovenstående tilgang:
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();
Produktion
The index of 34 is 9
Tidskompleksitet: O(1), da det kun involverer nogle få aritmetiske operationer.
Rumkompleksitet: O(1), da den kun bruger en konstant mængde hukommelse til at gemme variablerne.
Denne artikel er bidraget af Aditya Kumar .