C++で配列から最大の有理数（分数）を求める方法

この記事では、有理数が1行に1つずつ格納された2次元配列から、最大の有理数（分数）を求めるC++プログラムの作成方法について解説します。

問題の説明

与えられる2次元配列は [n][2] の形式です。各行には2つの整数値が含まれており、これらは有理数 a/b を表す分子 a と分母 b に対応します。私たちのタスクは、配列内のすべての有理数の中から最も大きい値を見つけることです。

具体例を使って問題を理解しましょう。

入力例

rat[][] = {
    {3, 2},
    {5, 7},
    {1, 9},
    {11, 4}
}

出力例

11 4

解説

3/2、5/7、1/9、11/4 の中で最大の値は 11/4 です。

解決アプローチ

この問題を解くには、各有理数の実際の値を計算して比較する方法が考えられます。しかし、この方法には落とし穴があります。浮動小数点型（float や double）を使用すると、精度の差がわずかな有理数を正確に区別できません。たとえば、34.12313431123 と 34.12313431124 のような値は、float 型では同じ値として扱われてしまう可能性があります。

そこで、別の比較方法を採用します。それはすべての分母の最小公倍数（LCM）を求め、それに合わせて各分子を変換するという手法です。共通の分母に揃えた後は、分子同士を比較するだけで最大の有理数を特定できます。この方法なら整数演算のみで処理できるため、精度誤差の心配がありません。

実装プログラム

上記の解決策を実装したC++プログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
const int n = 4;
int findMaxRatNum(int ratNum[n][2]){
    int numArray[n];
    int LCM = 1;
    int mavVal = 0, index = 0;
    for (int i = 0; i < n; i++)
        LCM = (LCM * ratNum[i][1]) / __gcd(LCM, ratNum[i][1]);
    for (int i = 0; i < n; i++) {
        numArray[i] = (ratNum[i][0]) * (LCM / ratNum[i][1]);
        if (mavVal < numArray[i]) {
            mavVal = numArray[i];
            index = i;
        }
    }
    return index;
}
int main(){
    int ratNum[n][2] = {{3, 2},{5, 7},{1, 9},{11, 4}};
    int i = findMaxRatNum(ratNum);
    cout<<"The maximum rational number from an array is "<<ratNum[i][0]<<"/"<<ratNum[i][1];
}

実行結果

The maximum rational number from an array is 11/4

まとめ

このプログラムでは、まず __gcd 関数を使ってすべての分母の最小公倍数を計算し、次に各分数を通分して分子だけを比較することで最大の有理数を求めています。浮動小数点数を使用しないため、どれほど桁数が多くても正確な比較が可能です。有理数の大小比較が必要な場面で、ぜひ活用してみてください。