Mums tiek dota a Fibonači skaitlis . Pirmie Fibonači skaitļi ir 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
Mums ir jāatrod dotā Fibonači skaitļa indekss, t.i., tāpat kā Fibonači skaitlis 8 atrodas pie indeksa 6.
Piemēri:
Input : 13
Output : 7
Input : 34
Output : 9
1. metode (vienkārša) : Vienkārša pieeja ir atrast Fibonači skaitļus līdz dotajiem Fibonači skaitļiem un saskaitīt veikto iterāciju skaitu.
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. ?> Izvade
8
2. metode (pamatojoties uz formulu)
Bet šeit mums bija jāģenerē visi Fibonači skaitļi līdz norādītajam Fibonači skaitlim. Bet šai problēmai ir ātrs risinājums. Paskatīsimies, kā! Ņemiet vērā, ka lielākajā daļā platformu skaitļa žurnāla aprēķināšana ir O(1) darbība.
Fibonači skaitlis ir aprakstīts kā
F n = 1/sqrt(5) (pow(an) - pow(bn)), kur
a = 1/2 (1 + kvadrāts(5)) un b = 1/2 (1 - kvadrāts(5))
Neņemot vērā pow(b n), kas ir ļoti mazs n lielās vērtības dēļ, mēs iegūstam
n = apaļš {2,078087 * log(Fn) + 1,672276}
kur apaļa nozīmē noapaļot līdz tuvākajam veselam skaitlim.
burbulis kārtot java
Zemāk ir iepriekš minētās idejas īstenošana.
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. ?> Izvade
10
Laika sarežģītība : O(1)
Palīgtelpa : O(1)
Pieeja:
mēs varam atrisināt šo problēmu, izmantojot n-tā Fibonači skaitļa formulu, kas ir:
F(n) = (pow((1+sqrt(5))/2 n) - pow((1-sqrt(5))/2 n)) / sqrt(5)
Izmantojot šo formulu, mēs varam iegūt noteikta Fibonači skaitļa indeksu. Mēs varam atkārtot n vērtības un aprēķināt atbilstošo Fibonači skaitli, izmantojot iepriekš minēto formulu, līdz atrodam Fibonači skaitli, kas ir lielāks vai vienāds ar doto skaitli. Šajā brīdī mēs varam atgriezt Fibonači skaitļa indeksu, kas atbilst dotajam skaitlim.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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();
Izvade
The index of 34 is 9
Laika sarežģītība: O(1), jo tas ietver tikai dažas aritmētiskas darbības.
Kosmosa sarežģītība: O(1), jo tas izmanto tikai nemainīgu atmiņas apjomu, lai saglabātu mainīgos lielumus.
Šī raksta autors ir Aditja Kumara .