[B02]阿拉伯数字转换为罗马数字 | JavaScript 算法实现

[hylerrix]

昨日，在 FCC 平台整整用了两三小时，才刷出一道 JS 算法题，回首而看，最终的代码也就那么多行，记录过程，写文以促进之后改进，也顺便整理一下自己在 FCC 上遇到问题后的解决思路。

阿拉伯数字转换为罗马数字 -- 做题传送门，来试试~

想看答案的可以直接拉至文章后方~~

---

数字转换规则

---

罗马数字我们都不陌生，I、II、V 、IX 等字符见文知意，可是当阿拉伯数字达到百千级别的时候，用什么字母表示？字母的排列顺序又应该是什么样子的呢？下面诺列了几个规则：

基本字符

I、V、X、L、C、D、M

分别代表

1、5、10、50、100、500、1000

计数规则：

• 若干相同数字连写表示的数是这些罗马数字的和，如III=3；
• 小数字在大数字前面表示的数是用大数字减去小数字，如IV＝4；
• 小数字在大数字后面表示的数是用大数字加上小数字，如VI=6;

组合规则：

• 基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
• 不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
• V 和 X 左边的小数字只能用 Ⅰ。
• L 和 C 左边的小数字只能用 X。
• D 和 M 左 边的小数字只能用 C 。

可见该字符只适用于 4000 以下的正整数阿拉伯数字。

---

思路历程

---

按照规则来说，看来也就是要满足类似如下输入和输出：

首先想到的是找不同字符：最终也就只有 I、V、X、L、C、D、M 这七个字符分别代表几个数字，进行一定的左右顺序排列后完成转换。那么在这里首先要生成一个装有七个元素的数组，这时输入 9 的话，去拼装 I 和 X，输入 97 的话，去拼装 L 或者 C 等等。

var Roman = {
  1: 'I',
  5: 'V',
  10: 'X',
  50: 'L',
  100: 'C',
  500: 'D',
  1000: 'M'
};

就像 97 ，选择从 L (50)向右拼装呢还是选择 C (100)向左拼装，看来要去找输入数字左右两侧有对应罗马字符的数字，例如 97 的左边有代表 'L' 的 50 ，右边有代表 'C' 的 100。

开始设计算法，处处断点跟踪。

function convert(num) {
    if (isNaN(num)) return num;
    var str = "";
    var left, right; // 找到输入数字的左值和右值
    var p;
    for (p in Roman) {
      if (num > p) {
        left = p; // 左边的值一直在跟踪
      } else {
        right = p; // 知道左边的值找到后，左边的值得下一个赋给右边的值
        break;
      }
    }
    console.log("(left: " + left + ")----" + num + "----(right: " + right + ")");
    return str;
}

断点跟踪情况来看。发现确实能找到输入数字左右两边的值。

---

变得更复杂了，及时收手，重新思考

---

哇塞，找到输入数字左右两个数字后呢？在之前的转换规则里有说过，最大的罗马数字(例如‘V’)，左侧的数字(例如‘I’)代表减少，右侧的数字代表(例如‘II’)增加。这时，罗马数字‘IV’、‘VII’即为阿拉伯数字 4 和 7 了。

当这时只用单个字符左右拼装 3999 的时候，一切都复杂了。

3999 --> MMMCMXCIX

要判断 9 应该转换为 VIIII 还是 IX ，必然会多出很多选择循环分支，变得更复杂了，及时收手，重新查找规律。

原来，像 97 这样的数字，不必纠结于是从 L(50) 开始拼装还是从 C(100) 开始拼装，90 转换成 XC ，7 转换成 VII 即可。看了看别的数字，都是这个规律呢，于是制定出如下对应表，直接查找到 个十百千 的任何一个。

var Roman = [["","I","II","III","IV","V","VI","VII","VIII","IX"],
             ["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"],
             ["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],
             ["","M","MM","MMM","  "," ","  ","   ","    ","  "]];

3999 就可以理解为：3000 -> MMM, 900 -> CM, 90 -> XC, 9 -> IX 了。

3999 --> MMMCMXCIX

---

最终算法实现

---

其实你只用从这里正式看就可以了，前面的情景铺设不利于直接解答你的困惑呢。最终实现功能的函数才只有短短的 8 行。

• ReverseArr 数组用来将输入数字转换成字符数组后倒序保存，这样 ReverseArr[0] 永远是输入数字的个位数，便于处理。
• CorrectArr 数组用来将每个 ReverseArr 数组的数字查表转换成对应的罗马数字。
• 最终返回 CorrectArr 数组经过 join 方法后连接起来的字符串。

var Roman = [["","I","II","III","IV","V","VI","VII","VIII","IX"],
             ["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"],
             ["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],
             ["","M","MM","MMM","  "," ","  ","   ","    ","  "]];

// 只能转换 4000 以下的正整数阿拉伯数字
function convert(num) {
    if(isNaN(num)) return num;
    var ReverseArr = num.toString().split("").reverse();
    var CorrectArr = [];
    for (var i = 0; i < ReverseArr.length; i++) {
      CorrectArr.unshift(Roman[i][ReverseArr[i]]);
    }
    return CorrectArr.join("");
}

俩小时后的这一瞬间，感动死我了思密达：

---

整理自己的思考过程

---

• 查看 MDN 文档(重要)，MDN 文档由网上所有人参与编辑维护，里面有几乎全部的 JS 对象及其方法的使用用例。
• 随时 Chrome 开发者工具测试 demo 和调试，处处 console.log “人肉”看状态。
• 搜索引擎 -- 百度 or 谷歌(辅助)，算法这块，到瓶颈之处真不好意思一直不查资料想下去。
• FCC 微信群，记得“提问的智慧”哦，人人都很忙呢。

• Hello，我是韩亦乐，现任本科软工男一枚。软件工程专业的一路学习中，我有很多感悟，也享受持续分享的过程。如果想了解更多或能及时收到我的最新文章，欢迎订阅我的个人微信号：韩亦乐。我的简书个人主页中，有我的订阅号二维码和 Github 主页地址；[我的知乎主页]中也会坚持产出，欢迎关注。
• 本文内部编号经由我的 Github 相关仓库统一管理；本文可能发布在多个平台但仅在上述仓库中长期维护；本文同时采用【知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议】进行许可。