C++で2つの有理数のうち大きい方（最大値）を求める方法

問題概要

この問題では、2つの有理数が与えられ、そのうち大きい方（最大値）を見つけることが課題となります。

ここで扱う有理数は、p/q の形式（分数形式）で表されるものとします。

具体例で問題を理解しよう

入力：rat1 = 5/4、rat2 = 3/2

出力：3/2

説明：

5/4 = 1.25
3/2 = 1.5

小数に変換して比較すると、1.5 の方が大きいため、答えは 3/2 となります。

解法のアプローチ

この問題は、学校の数学で習った方法と同じ考え方で解くことができます。

手順は以下の通りです。

1. まず、2つの分母の最小公倍数（L.C.M.）を求めます。
2. 次に、各分数の分子を、分母を最小公倍数に揃えるために必要な倍率で掛け合わせます。
3. 共通の分母に揃えた後は、分子が大きい方の有理数が最大値となります。

解法の動作を示すプログラム

コード例

#include <bits/stdc++.h>
using namespace std;

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

void maxRational(int ratOneNum, int ratOneDen, int ratTwoNum, int ratTwoDen) {
    int k = findLCM(ratOneDen, ratTwoDen);

    int oneNum = ratOneNum * k / (ratOneDen);
    int twoNum = ratTwoNum * k / (ratTwoDen);

    if(oneNum > twoNum)
        cout<<ratOneNum<<"/"<<ratOneDen;
    else
        cout<<ratTwoNum<<"/"<<ratTwoDen;
}

int main() {
    int ratOneNum = 5;
    int ratOneDen = 4;
    int ratTwoNum = 3;
    int ratTwoDen = 2;
    cout<<"The maximum of the two rational Numbers is ";
    maxRational(ratOneNum, ratOneDen, ratTwoNum, ratTwoDen);
    return 0;
}

出力結果

The maximum of the two rational Numbers is 3/2

まとめ

このように、分母の最小公倍数を使って両方の有理数を通分し、分子同士を比較するだけで、浮動小数点数への変換による誤差を気にせずに正確な比較を行うことができます。計算量も最小公倍数の計算のみで済むため、非常に効率的な手法です。