Q 03　罗马数字的转换规则

IQ　80
目标时间：20 分钟

手表的表盘上常用罗马数字。我们去国外旅行时可以发现，随处都能看到罗马数字，比如历史建筑物的表面等。如果我们不了解“转换规则”，就不知道那些数字表示的是多少。

这里，我们来研究一下罗马数字。罗马数字使用的是表 1.5 中的符号。

这个表里没有的罗马数字可通过加法的方式来表示，但这样一来，1 个数就会有多种表现形式。这时，要从这些表现形式中选取用字较少的一种，并按照大数在左的规则从左往右排列。例如，27 可以表示成，所以写作 XXVII。

不过，罗马数字的表现形式中还有一条规则：连续排列的相同字符，其数量要少于 4（不包含 4）个。举个例子，4 不能写成 IIII，9 不能写成 VIIII。这时，要通过减法运算把较小的数字写在较大的数字的左边，比如 4 要写成 IV，9 要写成 IX。

另外，罗马数字能够使用的符号只到 M（1000），所以它最大只能表示到 3999。

问题

12 个罗马数字的符号一共能表示多少个符合规则的罗马数字呢？

例如，1 个符号可以表示的罗马数字有 I、V、X、L、C、D、M 这 7 个，而 15 个符号可以表示的罗马数字只有 MMMDCCCLXXXVIII（3888）这 1 个。

思路

正如 Hint 部分提示的那样，如果能把每个阿拉伯数字都转换成罗马数字，那么只要数一数一共有多少个字符就可以了。因此，我们需要思考一下如何将阿拉伯数字转换成罗马数字。

在读数字的时候，我们会考虑数位。除了个、十、百、千这种划分方式，超过了万位的话，还可以将这些数位组合起来使用，例如将 13 000 000 读作“一千三百万”，而英语中是像 ten thousand 这样按千来划分的。

在把阿拉伯数字转换成罗马数字时，我们也可以试着按照数位来进行划分。首先，为了按 1、10、100、1000 来划分，我们要用除法求余数。当余数是 4、9、40、90、…时，可以直接将阿拉伯数字转换成罗马数字。

当余数是别的数时，就要再除以 5、50、500……，进一步求余数。我们按照表 1.6 这种方式整理之后会发现，颜色相同的地方，罗马数字的递增方式也一样，是有规律可循的。

我们来根据这张表进行编程。具体的实现方式如代码清单 03.01 和代码清单 03.02 所示。

代码清单 03.01（q03.rb）

N = 12

# 转换一位
def conv(n, i, v, x)
  result = ''
  if n == 9
    result += i + x
  elsif n == 4
    result += i + v
  else
    result += v * (n / 5)
    n = n % 5
    result += i * n
  end
  result
end

# 转换为罗马数字
def roman(n)
  m, n = n.divmod(1000)
  c, n = n.divmod(100)
  x, n = n.divmod(10)
  result = 'M' * m
  result += conv(c, 'C', 'D', 'M')
  result += conv(x, 'X', 'L', 'C')
  result += conv(n, 'I', 'V', 'X')
  result
end

cnt = Hash.new(0)
1.upto(3999){|n|
  cnt[roman(n).size] += 1
}
puts cnt[N]

代码清单 03.02（q03.js）

N = 12;

// 转换一位
function conv(n, i, v, x){
  var result = '';
  if (n == 9)
    result += i + x;
  else if (n == 4)
    result += i + v;
  else {
    for (j = 0; j < Math.floor(n / 5); j++)
      result += v;
    n = n % 5;
    for (j = 0; j < n; j++)
      result += i;
  }
  return result;
}

// 转换为罗马数字
function roman(n){
  var m = Math.floor(n / 1000);
  n %= 1000;
  var c = Math.floor(n / 100);
  n %= 100;
  var x = Math.floor(n / 10);
  n %= 10;
  var result = 'M'.repeat(m);
  result += conv(c, 'C', 'D', 'M');
  result += conv(x, 'X', 'L', 'C');
  result += conv(n, 'I', 'V', 'X');
  return result;
}

var cnt = {};
for (i = 1; i < 4000; i++){
  var len = roman(i).length;
  if (cnt[len]){
    cnt[len] += 1;
  } else {
    cnt[len] = 1;
  }
}
console.log(cnt[N]);

答案　93 个