FINN INDEKS FOR GITT FIBONACCI-TALL I KONSTANT TID

Vi får en Fibonacci nummer . De første Fibonacci-tallene er 0 1 1 2 3 5 8 13 21 34 55 89 144 .....
Vi må finne indeksen til det gitte Fibonacci-tallet, det vil si at Fibonacci-tallet 8 er på indeks 6.

Eksempler:

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

Metode 1 (enkel) : En enkel tilnærming er å finne Fibonacci-tall opp til de gitte Fibonacci-tallene og telle antall iterasjoner utført.

java main

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

Produksjon

Metode 2 (formelbasert)
Men her trengte vi å generere alle Fibonacci-tallene opp til et gitt Fibonacci-nummer. Men det er en rask løsning på dette problemet. La oss se hvordan! Merk at å beregne loggen for et tall er en O(1)-operasjon på de fleste plattformer.

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 å neglisjere pow(b n) som er veldig liten på grunn av den store verdien av n vi får
n = rund { 2,078087 * log(Fn) + 1,672276 }
hvor rund betyr avrunding til nærmeste heltall.

Nedenfor er implementeringen av ideen ovenfor.

binært tre i java

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

Produksjon

Tidskompleksitet : O(1)
Hjelpeplass : O(1)

Nærme:

vi kan løse dette problemet ved å bruke formelen for det n-te Fibonacci-tallet som er:

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

Vi kan utlede indeksen til et gitt Fibonacci-tall ved å bruke denne formelen. Vi kan iterere over verdiene til n og beregne det tilsvarende Fibonacci-tallet ved å bruke formelen ovenfor til vi finner et Fibonacci-tall som er større enn eller lik det gitte tallet. På dette tidspunktet kan vi returnere indeksen til Fibonacci-tallet som samsvarer med det gitte tallet.

Nedenfor er implementeringen av tilnærmingen ovenfor:

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

Produksjon

The index of 34 is 9

Tidskompleksitet: O(1) da det bare involverer noen få aritmetiske operasjoner.
Plass kompleksitet: O(1) da den bare bruker en konstant mengde minne til å lagre variablene.

Denne artikkelen er bidratt av Aditya Kumar .

Lag quiz

TechCodeview

Finn indeks for gitt fibonacci-tall i konstant tid