GCD IN FIBONACCIJEVA ŠTEVILA

Preizkusite na GfG Practice ' title=

#practiceLinkDiv { display: none !important; }

Dobili ste dve pozitivni števili M in N. Naloga je izpisati največji skupni delitelj od M'th in N'th Fibonaccijeva števila .
Prvih nekaj Fibonaccijevih števil je 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Upoštevajte, da se 0 šteje za 0'to Fibonaccijevo število.
Primeri:

Input : M = 3 N = 6 Output : 2 Fib(3) = 2 Fib(6) = 8 GCD of above two numbers is 2 Input : M = 8 N = 12 Output : 3 Fib(8) = 21 Fib(12) = 144 GCD of above two numbers is 3

Priporočena praksa GCD in Fibonaccijeva števila Poskusite!

A Preprosta rešitev sledite spodnjim korakom.
1) Poiščite M'th Fibonaccijevo število.
2) Poiščite N-to Fibonaccijevo število.
3) Vrni GCD dveh števil.
A Boljša rešitev temelji na spodnji identiteti

  GCD(Fib(M) Fib(N)) = Fib(GCD(M N))   The above property holds because Fibonacci Numbers follow Divisibility Sequence i.e. if M divides N then Fib(M) also divides N. For example Fib(3) = 2 and every third third Fibonacci Number is even. Source :   Wiki

Koraki so:
1) Poiščite GCD za M in N. Naj bo GCD g.
2) Vrnite Fib(g).
Spodaj so izvedbe zgornje ideje.

C++

// C++ Program to find GCD of Fib(M) and Fib(N) #include    using namespace std; const int MAX = 1000; // Create an array for memoization int f[MAX] = { 0 }; // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ int fib(int n) {  // Base cases  if (n == 0)  return 0;  if (n == 1 || n == 2)  return (f[n] = 1);  // If fib(n) is already computed  if (f[n])  return f[n];  int k = (n & 1) ? (n + 1) / 2 : n / 2;  // Applying recursive formula [Note value n&1 is 1  // if n is odd else 0.  f[n] = (n & 1)  ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1))  : (2 * fib(k - 1) + fib(k)) * fib(k);  return f[n]; } // Function to return gcd of a and b int gcd(int M int N) {  if (M == 0)  return N;  return gcd(N % M M); } // Returns GCD of Fib(M) and Fib(N) int findGCDofFibMFibN(int M int N) {  return fib(gcd(M N)); } // Driver code int main() {  int M = 3 N = 12;  cout << findGCDofFibMFibN(M N);  return 0; }

// C Program to find GCD of Fib(M) and Fib(N) #include  const int MAX = 1000; // Returns n'th Fibonacci number using table arr[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ int fib(int n) {  // Create an array for memoization  int arr[MAX];  for (int i = 0; i < MAX; i++)  arr[i] = 0;  // Base cases  if (n == 0)  return 0;  if (n == 1 || n == 2)  return (arr[n] = 1);  // If fib(n) is already computed  if (arr[n])  return arr[n];  int k = (n & 1) ? (n + 1) / 2 : n / 2;  // Applying recursive formula [Note value n&1 is 1  // if n is odd else 0.  arr[n]  = (n & 1)  ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1))  : (2 * fib(k - 1) + fib(k)) * fib(k);  return arr[n]; } // Function to return gcd of a and b int gcd(int M int N) {  if (M == 0)  return N;  return gcd(N % M M); } // Returns GCD of Fib(M) and Fib(N) int findGCDofFibMFibN(int M int N) {  return fib(gcd(M N)); } // Driver code int main() {  int M = 3 N = 12;  printf('%d' findGCDofFibMFibN(M N));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java Program to find GCD of Fib(M) and Fib(N) class gcdOfFibonacci {  static final int MAX = 1000;  static int[] f;  gcdOfFibonacci() // Constructor  {  // Create an array for memoization  f = new int[MAX];  }  // Returns n'th Fibonacci number using table f[].  // Refer method 6 of below post for details.  // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/  private static int fib(int n)  {  // Base cases  if (n == 0)  return 0;  if (n == 1 || n == 2)  return (f[n] = 1);  // If fib(n) is already computed  if (f[n]!=0)  return f[n];  int k = ((n & 1)==1)? (n+1)/2 : n/2;  // Applying recursive formula [Note value n&1 is 1  // if n is odd else 0.  f[n] = ((n & 1)==1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))  : (2*fib(k-1) + fib(k))*fib(k);  return f[n];  }  // Function to return gcd of a and b  private static int gcd(int M int N)  {  if (M == 0)  return N;  return gcd(N%M M);  }  // This method returns GCD of Fib(M) and Fib(N)  static int findGCDofFibMFibN(int M int N)  {  return fib(gcd(M N));  }  // Driver method  public static void main(String[] args)  {  // Returns GCD of Fib(M) and Fib(N)  gcdOfFibonacci obj = new gcdOfFibonacci();  int M = 3 N = 12;  System.out.println(findGCDofFibMFibN(M N));  } } // This code is contributed by Pankaj Kumar

Python3

# Python Program to find # GCD of Fib(M) and Fib(N) MAX = 1000 # Create an array for memoization f=[0 for i in range(MAX)] # Returns n'th Fibonacci # number using table f[].  # Refer method 6 of below # post for details. # https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ def fib(n): # Base cases if (n == 0): return 0 if (n == 1 or n == 2): f[n] = 1 # If fib(n) is already computed if (f[n]): return f[n] k = (n+1)//2 if(n & 1) else n//2 # Applying recursive # formula [Note value n&1 is 1 # if n is odd else 0. f[n] = (fib(k)*fib(k) + fib(k-1)*fib(k-1)) if(n & 1) else ((2* fib(k-1) + fib(k))*fib(k)) return f[n] # Function to return # gcd of a and b def gcd(M N): if (M == 0): return N return gcd(N % M M) # Returns GCD of # Fib(M) and Fib(N) def findGCDofFibMFibN(M N): return fib(gcd(M N)) # Driver code M = 3 N = 12 print(findGCDofFibMFibN(M N)) # This code is contributed # by Anant Agarwal.

// C# Program to find GCD of  // Fib(M) and Fib(N) using System; class gcdOfFibonacci {    static int MAX = 1000;  static int []f;  // Constructor  gcdOfFibonacci()   {  // Create an array  // for memoization  f = new int[MAX];  }  // Returns n'th Fibonacci number  // using table f[]. Refer method   // 6 of below post for details.  // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/  private static int fib(int n)  {  // Base cases  if (n == 0)  return 0;  if (n == 1 || n == 2)  return (f[n] = 1);  // If fib(n) is   // already computed  if (f[n]!=0)  return f[n];  int k = ((n & 1)==1)? (n+1)/2 : n/2;  // Applying recursive formula   // [Note value n&1 is 1  // if n is odd else 0.  f[n] = ((n & 1) == 1) ? (fib(k) * fib(k) +  fib(k - 1) * fib(k - 1)) :   (2 * fib(k - 1) + fib(k)) * fib(k);  return f[n];  }  // Function to return gcd of a and b  private static int gcd(int M int N)  {  if (M == 0)  return N;  return gcd(N%M M);  }  // This method returns GCD of  // Fib(M) and Fib(N)  static int findGCDofFibMFibN(int M int N)  {  return fib(gcd(M N));  }  // Driver method  public static void Main()  {  // Returns GCD of Fib(M) and Fib(N)  new gcdOfFibonacci();  int M = 3 N = 12;  Console.Write(findGCDofFibMFibN(M N));  } } // This code is contributed by nitin mittal.

PHP

 // PHP Program to find // GCD of Fib(M) and Fib(N) $MAX = 1000; // Create an array for memoization $f = array_fill(0 $MAX 0); // Returns n'th Fibonacci number  // using table f[]. Refer method  // 6 of below post for details. function fib($n) { global $f; // Base cases if ($n == 0) return 0; if ($n == 1 or $n == 2) $f[$n] = 1; // If fib(n) is already computed if ($f[$n]) return $f[$n]; $k = ($n & 1) ? ($n + 1) / 2 : $n / 2; // Applying recursive formula [Note  // value n&1 is 1 if n is odd else 0. $f[$n] = ($n & 1) ? (fib($k) * fib($k) + fib($k - 1) * fib($k - 1)) : ((2 * fib($k - 1) + fib($k)) * fib($k)); return $f[$n]; } // Function to return gcd of a and b function gcd($M $N) { if ($M == 0) return $N; return gcd($N % $M $M); } // Returns GCD of Fib(M) and Fib(N) function findGCDofFibMFibN($M $N) { return fib(gcd($M $N)); } // Driver code $M = 3; $N = 12; print(findGCDofFibMFibN($M $N)) // This code is contributed // by mits ?>

JavaScript

<script>  // JavaScript Program to find GCD of Fib(M) and Fib(N)  const MAX = 1000;  // Create an array for memoization  var f = [...Array(MAX)];  f.fill(0);  // Returns n'th Fibonacci number using table f[].  // Refer method 6 of below post for details.  // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/  function fib(n) {  // Base cases  if (n == 0) return 0;  if (n == 1 || n == 2) return (f[n] = 1);  // If fib(n) is already computed  if (f[n]) return f[n];  var k = n & 1 ? (n + 1) / 2 : n / 2;  // Applying recursive formula [Note value n&1 is 1  // if n is odd else 0.  f[n] =  n & 1  ? fib(k) * fib(k) + fib(k - 1) * fib(k - 1)  : (2 * fib(k - 1) + fib(k)) * fib(k);  return f[n];  }  // Function to return gcd of a and b  function gcd(M N) {  if (M == 0) return N;  return gcd(N % M M);  }  // Returns GCD of Fib(M) and Fib(N)  function findGCDofFibMFibN(M N) {  return fib(gcd(M N));  }  // Driver code  var M = 3  N = 12;  document.write(findGCDofFibMFibN(M N));    // This code is contributed by rdtank.  </script>

Izhod: