C++で有理数を10進数表記の文字列に変換する方法（循環小数対応）

問題概要

分子（numerator）と分母（denominator）の2つの整数で、有理数「分子 / 分母」を表すことを考えます。この値を10進数表記の文字列として求めます。小数部分に循環する数字（循環節）が含まれる場合は、その部分を括弧 ( ) で囲んで表現します。

たとえば、入力が numerator = 164、denominator = 3 の場合、164 ÷ 3 = 54.666… となるため、出力は「54.(6)」となります。

アルゴリズムの考え方

この問題は、筆算の割り算をコンピュータ上でシミュレートすることで解決できます。手順は以下の通りです。

• 分子が0の場合は、そのまま「0」を返します。
• 結果を格納するための配列 ans を用意します。
• 分子と分母の符号が異なる場合（片方が負でもう片方が正の場合）は、ans の末尾に '-' を追加します。
• divisor := |分子|、dividend := |分母| とします。
• remainder := divisor mod dividend として余りを求めます。
• x := (divisor ÷ dividend) を文字列に変換し、その各文字を ans に追加します（これが整数部分になります）。
• remainder が0の場合（割り切れた場合）は、ここで ans を文字列として返して終了です。
• 割り切れない場合は、ans の末尾に '.' を追加します。
• 余りの出現位置を記録するためのマップ m を定義します。
• remainder が0になるまで、次の処理を繰り返します。
  • remainder がすでに m に登録されている場合：同じ余りが再び現れたということは、そこから数字の並びが循環していることを意味します。したがって、m[remainder] に記録された位置に '(' を挿入し、ans の末尾に ')' を追加してループを抜けます。
  • まだ登録されていない場合：m[remainder] := 現在の ans のサイズを記録し、remainder := remainder × 10 として、(remainder ÷ dividend) の商の数字を ans の末尾に追加します。その後、remainder := remainder mod dividend と更新します。
• 最後に ans を文字列として返します。

なお、余りは必ず 0 以上 dividend 未満の範囲に収まるため、同じ余りが再び現れるか、余りが0になって終了するかのどちらかが必ず起こります。つまり、このアルゴリズムは必ず有限回のループで停止することが保証されています。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string solve(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());
   }
};
string solve(int numerator, int denominator) {
   return (new Solution())->solve(numerator, denominator);
}
int main() {
   cout << solve(164, 3);
}

実装のポイントとして、絶対値の計算に labs() を使用しています。これは int 型の最小値（INT_MIN）を扱う際にオーバーフローを避けるためで、long 型にキャストしてから絶対値を取ることで安全に処理できます。

入力

164, 3

出力

54.(6)