หาค่า LCM ของจำนวนตรรกยะ (Rational Numbers) ใน C++

บทนำ

บทความนี้จะแสดงวิธีการหา LCM (Least Common Multiple - ตัวคูณร่วมน้อยที่สุด) ของจำนวนตรรกยะ สมมติมีรายการจำนวนตรรกยะ เช่น {2/7, 3/14, 5/3} ค่า LCM จะได้เป็น 30/1

สูตรการคำนวณ

เพื่อแก้ปัญหานี้ เราต้องคำนวณ:

1. LCM ของตัวเศษทั้งหมด (Numerators)
2. GCD ของตัวส่วนทั้งหมด (Denominators)
3. LCM ของจำนวนตรรกยะ = LCM ของตัวเศษ / GCD ของตัวส่วน

สูตรคณิตศาสตร์:

$$LCM = \frac{LCM\text{ ของตัวเศษทั้งหมด}}{GCD\text{ ของตัวส่วนทั้งหมด}}$$

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int LCM(int a, int b) {
    return (a * b) / (__gcd(a, b));
}

int numeratorLCM(vector<pair<int, int> > vect) {
    int result = vect[0].first;
    for (int i = 1; i < vect.size(); i++)
        result = LCM(vect[i].first, result);
    return result;
}

int denominatorGCD(vector<pair<int, int> > vect) {
    int res = vect[0].second;
    for (int i = 1; i < vect.size(); i++)
        res = __gcd(vect[i].second, res);
    return res;
}

void rationalLCM(vector<pair<int, int> > vect) {
    cout << numeratorLCM(vect) << "/" << denominatorGCD(vect);
}

int main() {
    vector<pair<int, int> > vect;
    vect.push_back(make_pair(2, 7));
    vect.push_back(make_pair(3, 14));
    vect.push_back(make_pair(5, 3));
    cout << "LCM of rational numbers: ";
    rationalLCM(vect);
    return 0;
}

ผลลัพธ์

LCM of rational numbers: 30/1