10進数をローマ数字に変換するアルゴリズムとC++実装

ローマ数字とは

ローマ数字は位取り記数法を採らない記数法です。複数の記号を組み合わせることで1つの数値を表現します。たとえば 75 は「75 = 50 + 10 + 10 + 5」と分解できるため、ローマ数字では LXXV と表されます。

この記事では、10進形式で与えられた数値をローマ数字の文字列へ変換する方法を、記号の一覧表・アルゴリズムの手順・C++による実装例とともに解説します。

ローマ数字の記号とその値

ローマ数字で使用される主な記号と、それぞれに対応する値は以下の表の通りです。ここでは 4000 以上の数も扱えるよう、非標準の拡張記号（MMMM、V'）も含めています。

この表を使えば、任意の数値に対応するローマ数字を容易に求められます。ポイントは、4 や 9 のように減算を伴う数（IV、IX など）もあらかじめ独立した記号として登録しておくことです。

入力と出力

Input:
Decimal number: 3569
Output:
The Roman equivalent of 3569 is: MMMDLXIX

アルゴリズム

変換には貪欲法（グリーディ法）を用います。「対象の数を超えない最大の記号の値を選び、その値を引いて残りに対して同じ操作を繰り返す」というシンプルな手順です。

decToRoman(nuList, num)

入力： 記号とその値のリスト nuList、ローマ数字へ変換する数値 num。
出力： 与えられた数値に対応するローマ数字。

Begin
   if num ≠ 0, then
      max := num を超えない最大の記号の値を取得
      display the nuList[max].symbol
      num := num − nuList[max].value
      decToRoman(nuList, num)
End

num が 0 になるまで再帰的に処理を続けることで、数値全体がローマ数字の文字列として出力されます。

C++による実装例

#include<iostream>
using namespace std;

// ローマ数字の記号とその値を保持する構造体
struct numeral {
   string sym;
   int val;
};

// num を超えない最大の値を持つ記号のインデックスを返す
int maxNume(numeral nu[], int num) {
   int index;
   for(int i = 0; i<15; i++)  // 配列には15個の記号が格納されている
      if(nu[i].val <= num)
         index = i;
   return index;  // num 以下で最大の値を持つ記号のインデックス
}

// 再帰的にローマ数字を出力する関数
void decToRoman(numeral nu[], int num) {
   int max;
   if(num != 0) {
      max = maxNume(nu, num);
      cout << nu[max].sym;  // 記号を出力
      num -= nu[max].val;  // 選んだ記号の値を引いて残りを求める
      decToRoman(nu, num);  // 再帰的に処理を続ける
   }
}

int main() {
   int number;
   numeral nume[15] = {{"I",1},{"IV",4},{"V",5},{"IX",9},
      {"X",10},{"XL",40},{"L",50},{"XC",90},
      {"C",100},{"CD",400},{"D",500},{"CM",900},
      {"M",1000},{"MMMM",4000},{"V'",5000}
   };
   cout << "Enter a decimal number: "; cin >> number;

   if(number >0 && number <= 5000) {  // 入力値の範囲チェック（1〜5000）
      cout<<"The Roman equivalent of " << number<<" is: ";
      decToRoman(nume, number);
   }else {
      cout << "Invalid Input";
   }
}

実行結果

Enter a decimal number: 3569
The Roman equivalent of 3569 is: MMMDLXIX

このように、3569 は「3000（MMM）+ 500（D）+ 60（LX）+ 9（IX）」として分解され、正しく MMMDLXIX と変換されています。プログラムは 1〜5000 の範囲外の入力に対して「Invalid Input」と表示し、不正な値を弾く仕組みにもなっています。