หาค่าต่ำสุดร่วม (LCM) ของพจน์ฟีโบนัชชี 2 พจน์ใน C++

ให้ N, M หา LCM ของพจน์ฟีโบนัชชีที่ N และ M

ตัวอย่าง: N=4, M=9 → F(4)=2, F(9)=21 → LCM = 42

วิธีแก้ปัญหา

1. คำนวณพจน์ฟีโบนัชชีที่ N และ M
2. หา LCM ของทั้งสองจำนวน (ใช้วิธีหาตัวคูณร่วมน้อย)

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

long int fibo(int N) {
    long int a = 0, b = 1, c;
    for (int i = 2; i < N; i++) {
        c = a + b; a = b; b = c;
    }
    return c;
}

int findLCM(int a, int b) {
    int max = (a > b) ? a : b;
    int step = max;
    while (true) {
        if (max % a == 0 && max % b == 0) return max;
        max += step;
    }
}

int CalcFiboLCM(int N, int M) {
    int fiboN = fibo(N);
    int fiboM = fibo(M);
    return findLCM(fiboN, fiboM);
}

int main() {
    int N = 5, M = 14;
    cout << "The LCM of two Fibonacci number is " << CalcFiboLCM(N, M);
    return 0;
}

Output

The LCM of two Fibonacci number is 699