C++で解く「簡約分数」問題：0と1の間のすべての既約分数を求める方法

整数 n が与えられたとき、0より大きく1より小さい範囲に存在するすべての簡約済み（既約）分数を、分母が n 以下という条件で求めてリストとして返すことを考えます。分数の出力順序は問われません。

例えば、入力が n = 4 の場合、出力は ["1/2", "1/3", "1/4", "2/3", "3/4"] となります。"2/4" は "1/2" に約分できるため、簡約分数としては含まれません。

解法のアプローチ

この問題は以下の手順で解くことができます。

• 結果を格納する配列 ret を定義します。

• i を分母として、i = 2 から n まで繰り返します。

  • j を分子として、j = 1 から i - 1 まで繰り返します。

    • c := i と j の最大公約数（GCD）を求めます。

    • a := j / c（約分後の分子）

    • b := i / c（約分後の分母）

    • 文字列に変換した a と b を "/" で連結し、ret の末尾に追加します。

• ret 内の一意な要素のみからなる配列を返します。

最大公約数を使って各分数を約分することで、重複する分数（例えば "2/4" と "1/2"）が同じ文字列になり、最後に set で一意化することで簡約分数だけが残る仕組みです。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ret;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int c = __gcd(i, j);
                int a = j / c;
                int b = i / c;
                ret.push_back(to_string(a) + "/" + to_string(b));
            }
        }
        set<string> s(ret.begin(), ret.end());
        return vector<string>(s.begin(), s.end());
    }
};
main(){
    Solution ob;
    print_vector(ob.simplifiedFractions(4));
}

入力

4

出力

[1/2, 1/3, 1/4, 2/3, 3/4]

計算量について

このアルゴリズムは二重ループを使用するため、時間計算量は O(n² × log n) となります（log n はGCD計算のコスト）。空間計算量は生成される分数の数に依存し、最大 O(n²) です。なお、set を使った一意化の代わりに「gcd(i, j) == 1」の場合のみ結果に追加する方法を採れば、約分処理と一意化処理を省略でき、より効率的な実装になります。