程序在C ++中查找两个Fibonnaci数的LCM

在本教程中,我们将讨论一个程序来查找两个斐波那契数的LCM。

为此,我们将提供两个数字。我们的任务是找到这两个位置的斐波那契数,然后找到并打印这两个值的最小公倍数。

示例

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
//creating an array
int f[MAX] = { 0 };
//returning n'th fibonacci number
int fib(int n){
   //base cases
   if (n == 0)
      return 0;
   if (n == 1 || n == 2)
      return (f[n] = 1);
   if (f[n])
      return f[n];
   int k = (n & 1) ? (n + 1) / 2 : n / 2;
   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];
}
//finding GCD of those two values
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int findLCMFibonacci(int a, int b){
   return (fib(a) * fib(b)) / fib(gcd(a, b));
}
int main(){
   int a = 3, b = 12;
   cout << findLCMFibonacci(a, b);
   return 0;
}

输出结果

144