NÁJDITE INDEX DANÉHO FIBONACCIHO ČÍSLA V KONŠTANTNOM ČASE

Je nám dané a Fibonacciho číslo . Prvých pár Fibonacciho čísel je 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
Musíme nájsť index daného Fibonacciho čísla, t.j. ako Fibonacciho číslo 8 je na indexe 6.

pytón alebo

Príklady:

Input : 13  
Output : 7  
Input : 34  
Output : 9

Metóda 1 (jednoduchá) : Jednoduchý prístup je nájsť Fibonacciho čísla až po dané Fibonacciho čísla a spočítať počet vykonaných iterácií.

C++

// A simple C++ program to find index of given // Fibonacci number. #include   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 int main() {  int result = findIndex(21);  printf('%dn' result); } // This code is contributed by Saket Kumar

Java

// 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.

Python3

# 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.

JavaScript

<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>

PHP

 // 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. ?>

Výstup

Metóda 2 (založená na vzorci)
Tu sme však potrebovali vygenerovať všetky Fibonacciho čísla až po poskytnuté Fibonacciho číslo. Na tento problém však existuje rýchle riešenie. Pozrime sa ako! Všimnite si, že výpočet logu čísla je operácia O(1) na väčšine platforiem.

Fibonacciho číslo je opísané ako
F n = 1 / sqrt(5) (pow(an) - pow(bn)) kde
a = 1 / 2 ( 1 + sqrt(5) ) a b = 1 / 2 ( 1 - sqrt(5) )

Pri zanedbaní pow(b n), ktoré je veľmi malé kvôli veľkej hodnote n, dostaneme
n = okrúhle { 2,078087 * log(Fn) + 1,672276 }
kde okrúhle znamená zaokrúhliť na najbližšie celé číslo.

Nižšie je uvedená implementácia vyššie uvedenej myšlienky.

C++

// C++ program to find index of given Fibonacci // number #include   int findIndex(int n) {  float fibo = 2.078087 * log(n) + 1.672276;  // returning rounded off value of index  return round(fibo); } // Driver program to test above function int main() {  int n = 55;  printf('%dn' findIndex(n)); }

Java

// 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);  } }

Python3

# 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

JavaScript

<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

 // 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. ?>

Výstup

Časová zložitosť : O(1)
Pomocný priestor : O(1)

Prístup:

tento problém môžeme vyriešiť pomocou vzorca pre n-té Fibonacciho číslo, ktorý je:

F(n) = (pow((1+sqrt(5))/2 n) - pow((1-sqrt(5))/2 n)) / sqrt(5)

Pomocou tohto vzorca môžeme odvodiť index daného Fibonacciho čísla. Môžeme iterovať cez hodnoty n a vypočítať zodpovedajúce Fibonacciho číslo pomocou vyššie uvedeného vzorca, kým nenájdeme Fibonacciho číslo, ktoré je väčšie alebo rovné danému číslu. V tomto bode môžeme vrátiť index Fibonacciho čísla, ktorý sa zhoduje s daným číslom.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

#include    #include  using namespace std; int findIndex(int n) {  double phi = (1 + sqrt(5)) / 2;  int index = round(log(n * sqrt(5) + 0.5) / log(phi));  int fib = round((pow(phi index) - pow(1 - phi index)) / sqrt(5));  if (fib == n)  return index;  else  return -1; // n is not a Fibonacci number } int main() {  int n = 34;  int index = findIndex(n);  cout << 'The index of ' << n << ' is ' << index << endl;  return 0; }

Java

//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);  } }

Python3

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);  } }

JavaScript

// 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();

Výstup

The index of 34 is 9

Časová zložitosť: O(1), pretože zahŕňa len niekoľko aritmetických operácií.
Priestorová zložitosť: O(1), pretože používa iba konštantné množstvo pamäte na ukladanie premenných.

1 až 100 rímskych č

Do tohto článku prispeli Aditya Kumar .

Vytvoriť kvíz

TechCodeview

Nájdite index daného Fibonacciho čísla v konštantnom čase