算法编程JsfreeCodeCamp

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

2017-01-18  本文已影响575人  hylerrix

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

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

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

数字转换规则

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

基本字符

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

分别代表

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

计数规则：

组合规则：

可见该字符只适用于 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 行。

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("");
}

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

�整理自己的思考过程

上一篇下一篇

猜你喜欢

热点阅读