在本教程中,我们将讨论一个程序来查找两个斐波那契数的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