C++で分数を小数文字列に変換する方法（循環小数への対応）

2つの整数（分数の分子と分母）が与えられたとき、その分数を文字列形式の小数に変換することを考えます。小数部分に循環する桁（循環節）がある場合は、その繰り返し部分を括弧 () で囲んで表現します。例えば、分子が 2、分母が 3 の場合、出力は "0.(6)" となります。

この問題は、筆算による割り算の処理をシミュレートしながら、余りの出現履歴を記録することで解くことができます。以下の手順に従って実装していきましょう。

アルゴリズム

• 分子が 0 の場合は、そのまま "0" を返します。
• 結果を格納するための配列 ans を定義します。
• 符号の判定を行います。分子が負かつ分母が正、または分子が正かつ分母が負の場合は、マイナス記号 '-' を ans に追加します。
• divisor := |分子|、dividend := |分母| とし、remainder := divisor mod dividend を計算します。
• x := 整数部（divisor / dividend）を文字列化したものとします。
• x の各文字を ans に追加します。
• 余りが 0 であれば、ここで ans を文字列として返します（割り切れたケース）。
• 小数点 '.' を ans に追加します。
• 余りの出現位置を記録するためのマップ m を定義します。
• 余りが 0 になるまで以下を繰り返します。
  • もし同じ余りがマップ m にすでに存在する場合：
    • m[remainder] の示すインデックス位置に開き括弧 '(' を挿入します。
    • ans の末尾に閉じ括弧 ')' を追加します。
    • ループを抜けます。
  • 存在しない場合：
    • m[remainder] := 現在の ans のサイズ（出現位置を記録）
    • remainder := remainder × 10
    • (remainder / dividend) の商に '0' を加えた文字を ans に追加します。
    • remainder := remainder mod dividend
• 最終的に ans を文字列として返します。

このアルゴリズムのポイントは、同じ余りが2回現れた時点で小数が循環していると判断できることです。マップで各余りが最初に出現した位置を記録しておけば、循環の始まりに正確に括弧を挿入できます。

実装例

それでは、実際のC++コードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0)return "0";
        vector <char> ans;
        if(numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0)ans.push_back('-');
        long divisor = labs(numerator);
        long dividend = labs(denominator);
        long remainder = divisor % dividend;
        string x = to_string(divisor/dividend);
        for(int i = 0; i < x.size(); i++){
            ans.push_back(x[i]);
        }
        if(remainder == 0){
            return string(ans.begin(), ans.end());
        }
        ans.push_back('.');
        map <int, int> m;
        while(remainder != 0){
            if(m.find(remainder)!=m.end()){
                ans.insert(ans.begin() + m[remainder], '(');
                ans.push_back(')');
                break;
            }else{
                m[remainder] = ans.size();
                remainder *= 10;
                ans.push_back((remainder / dividend) + '0');
                remainder %= dividend;
            }
        }
        return string(ans.begin(), ans.end());
    }
};
main(){
    Solution ob;
    cout << ((ob.fractionToDecimal(100,6)));
}

入力

100
6

出力

16.(6)

補足：実装上の注意点

この実装では、分子・分母の絶対値を long 型で扱っている点に注目してください。INT_MIN（-2147483648）のような極端な値を int のまま絶対値変換するとオーバーフローが発生するため、labs() を使って long 型に拡張してから計算しています。また、循環の検出には map を使用しているため、時間計算量は O(log n)、空間計算量も O(log n) 程度に収まります（n は分母の値）。筆算の仕組みをそのままコードに落とし込んだシンプルかつ堅牢なアプローチです。