最近遇到一道非常有趣的题目,题目大意如下:有一个富翁在银河系里做生意,而银河系使用的是罗马数字,所以他需要一个精明能干的助手,帮助他完成罗马数字与阿拉伯数字的相互转换,题目在这个背景下衍生出交易场景,我们需要帮助他计算出相关商品的价格。对于这道题目,如果剥离开这个题目本身的交易场景,这道题目本质上就是一个纯粹的算法问题。说来惭愧,博主当时并未能快速地解决这个问题,事后通过研读别人的文章始能有所领悟。所以,今天想在这篇文章里,同大家一起来讨论下这个问题。今天,全世界都在使用0到9这10个阿拉伯数字,比阿拉伯数字早2000年的罗马数字。为什么没有流传下来为后世所用呢?我觉得这是一个非常有意思的问题,数学同计算机学科间那种千丝万缕的联系、技术演进过程中若有若无的某种必然性……这些都是令我觉得非常有意思的地方。那么,一起来看看这个问题可好?

罗马数字起源

  罗马数字,顾名思义,就是古罗马人使用的数字系统。在罗马数字中,共有7个基本数字,即I、V、X、L、C、D、M,它们分别表示1、5、10、50、100、500、1000。可以注意到,在这套数字系统中,0不被视作是一个整数。据说,曾经有一位罗马学者不顾教皇的反对,执意将与0相关的知识以及0在运算中的作用向民众传播,因此被教皇囚禁并投入监狱,理由是0是一个邪物,破坏了神圣的数。同样罗马数字无法表示小数(注:罗马数字有分数的表示方法,可仅仅能表示1/12的整数倍),因此罗马数字常常用来表示纪年,在欧洲国家的古书籍、建筑和钟表中,我们都可以见到罗马数字的身影。我们熟悉的元素周期表,同样采用了罗马数字来表示元素所在的”族”。需要说明的是,罗马数字是一种计数规则,而非计算规则,这意味者罗马数字是没有进位和权重的概念的,所以一般罗马数字只用以计数而不用以演算。

  既然罗马数字是一种计数规则,那么我们就不得不说一说它的组合规则,因为4000以内的数字,都可以用这7个基本数字组合表示。具体来讲,罗马数字的基本规则有以下4条:

  • 重复次数:一个数字重复多少次,所表示的数字就是这个罗马数字的多少倍;一个罗马数字最多重复三次。这条规则该怎么理解呢?第一点,I、II、III分别表示1、2、3;第二点,4必须被表示为IV,而不是IIII。关于4的表示方法,在历史上一直存在争议,一种观点认为IIII这种写法占用书写空间,IV可以达到简化书写的作用;而一种观点则认为IV有亵渎神灵朱庇特、含不敬侮辱之意。
  • 左减原则:当一个较小的数字被放在一个较大数字的左边时,所表示的数字等于这个大数减去这个小数,且左边最多只能放一个较小的数字。联系第一条原则,IV表示的实际上是V-I,所以这个数值表示4;同理,9为了满足第一条原则,必须被表示成IX。
  • 右加原则:当一个较小的数字被放在一个较大数字的右边时,所表示的数字等于这个大数加上这个小数,且右边最多只能放一个较小的数字。这一条原则和第二条原则相对应,例如11会被表示成XI、21会被表示为XXI,以此类推。
  • 搭配原则:I只能被放在V和X的左边;X只能被放在L和C的左边;C只能被放在D和M的左边;V、L、D不能被放在左边。这一条可以看作对是第二条的总结,所以没有什么可说的。

  好了,通过这个这些规则我们就可以组合出不同的数字,我们可以注意到这些数字呈现出1、4、5、9的规律。什么是1、4、5、9的规律呢?我们可以注意到4和9是两个特殊的数字,4必须通过5左减来得到,9必须通过10左减来得到,这是因为罗马数字要满足最多重复三次的原则,而4和9相对1和5的偏移量恰好是4,所以它们的表示方法和其他数字不同。因为罗马数字没有进位和权重的概念,所以除了左减和右增这两种特殊情况以外,它的基本数字应该从左至右依次递减,即使在左减的情况下,左边的数字应该和右边的数字处在同一序列。这句话怎么理解呢?例如,90必须用100-10来表示;而99必须拆解为90和9,然后分别用100-10和10-1来表示,唯独不能通过100-1来表示,因为100和1分属两个不同的序列。

数字转换实现

  了解完罗马数字的历史渊源,我们就对罗马数字有了一定的了解。现在来考虑一个问题,即罗马数字和阿拉伯数字间的相互转换。罗马数字的确是古罗马人发明的,可阿拉伯数字实际上却是古印度人发明的。今天全世界人都在使用阿拉伯数字,因此这两者间需要一个转换器,这正是我们一开始所讨论的问题:假如银河系里的人们都使用罗马数字来计数,当一个地球上的富翁来到银河系以后,他要如何去和这里的人们进行交易。显然,这种转换应该是双向的,我们下面分别来看如何实现相应的转换。

阿拉伯转罗马

  首先来考虑阿拉伯数字转罗马数字,因为一个罗马数字必然是从左到右依次递减,所以我们只需要将这7个基本数字从大到小排列,找到第一个不小于指定数字的数位即可。例如1024显然超过了1000,而罗马数字中的1000对应M,因此1024的第一位应该是M。接下来24,显然超过10,因此1024的第二位数字应该是X。接下来14,显然超过10,因此1024的第三位数字同样是X。接下来4,这是一个特殊的数字,需要被表示为IV,这是1024的第四位数字。我们将整个过程串联起来,就可以得到1024的罗马数字形式MXXIV。我们注意的一点是,这里需要4和9这两个数字作为辅助数字,因为1到3、6到8的数字,我们总可以通过不断地重复1来得到,就像辗转相除法一样。如果没有这两个辅助数字会怎样呢?4会变成IIII,而9会变成VIIII,显然这是不符合我们预期的。整理下我们的思路,这段代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static string ConvertToRoman(int number)
{
var output = new StringBuilder();
var digitMap = new Dictionary<int,string>()
{
{1,"I"},{4,"IV"},{5,"V"},{9,"IX"},
{10,"X"},{40,"XL"},{50,"L"},{90,"XC"},
{100,"C"},{400,"CD"},{500,"D"},{900,"CM"},
{1000,"M"}
};
var digits = digitMap.OrderByDescending(e => e.Key).ToList();

for (int i = 0; i < digits.Count && number > 0; i++)
{
if (number < digits[i].Key) continue;
while (number >= digits[i].Key)
{
number -= digits[i].Key;
output.Append(digits[i].Value);
}
}

return output.ToString();
}

罗马转阿拉伯

  接下来考虑罗马数字如何转换为阿拉伯数字,我们可以明确的一点是,罗马数字基本上是从左到右依次递减排列的,每一个数字的左侧和右侧出现的数字一定处于当前数字的同一序列。比如,I只能被放在V和X的左边;X只能被放在L和C的左边;C只能被放在D和M的左边。因此,我们从左到右依次遍历整个字符串,将每个字符转化为对应的阿拉伯数字然后累加即可,需要注意的是,当当前元素小于下一元素时,表示当前元素为负数;当当前元素大于下一元素时,表示当前元素为正数。显然,这里最后一位应该是正数,因为它没有下一个元素可以比较。至此,我们梳理出整个思路:从第一位到第n-1位依次循环,判断当前元素的正负然后累加,再加上最后一位元素的值即可。下面是代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int ConvertToNumber(string romanNumber)
{
var number = 0;
var length = romanNumber.Length;
var digits = new Dictionary<string,int>()
{
{"I",1},{"V",5},{"X",10},{"L",50},{"C",100},{"D",500},{"M",1000}
};

for (int i = 0; i < length - 1; i++)
{
//前面 n-1 位数字通过左右比较决定正负 & 第 n 位数字必然为正
if ((digits[romanNumber[i].ToString()] >= digits[romanNumber[i + 1].ToString()]) || i + 1 >= length)
{
number += digits[romanNumber[i].ToString()];
}
else
{
number -= digits[romanNumber[i].ToString()];
}
}
return number;
}

为什么会溢出

  相信上面这两段代码,大家都已然把玩过了。可我们仔细想想,就会觉得这事儿不靠谱。前段时间网络上一直流传着,我们这些佛系青年正在被同龄人抛弃。这个题目里我们所面对的,可是一个来自地球的的富翁啊!富翁的钱不都是按亿来计数的吗?我们没有一个亿这样的小目标,我们的目标是月入5万啊,这是一个社会上流行的说法。好了,回到这个题目中来,如果我们输入50000这个阿拉伯数字,它会输出什么呢?答案是50个M,这很罗马数字啊,当然更神奇的事情是什么呢?当我们尝试把这由50个M组成的罗马数字转换为阿拉伯数字时,会发现它不能像我们期望地输出50000,而会变成是一个负数。为什么这里是负数呢?答案是溢出啦!

  过去,我们常常听到”溢出“这个词儿,最常见的是数据溢出。为什么会发生数据溢出呢?因为我们定义的数据超过了计算机所使用的数据的表示范围。这一点我们可能无法理解,一个相对粗浅的认识是,现代计算机的内存已经大到非常客观,甚至我们的硬盘都已经使用TB这样的容量单位,为什么还是会发生数据溢出呢?回到罗马数字这个问题,我们发现一个残酷的事实是,古罗马人并没有定义1000以上的数字表示,这或许和古罗马人发明数字的过程有关。古人最早都是使用手指、绳结、竹筹这样的工具来计数,在人们没有接触到相当大的数字以前,人们认为这些数的表示是足够的。同样的,我们的计算机经历了从8位、16位、32位到64位的发展。所以,这个世界上没有任何东西是一成不变的,一个技术方案势必要随着业务演化而扩展。

  我们前面曾提到,这7个基本数字可以表示4000以内的数字,为什么是4000以内呢?因为根据罗马数字最多重复三次的规则,我们应该用5000-1000来表示4000,可问题是这7个基本数字中并没有5000的定义,这和计算机中的数据溢出是非常相似的,因为我们都无法通过现有的构造去描述一个新的东西。这和数学上的那些”扩充“有着极其相似的地方,当我们意识到所有的数不都是整数的时候,我们引入了分数/小数;当我们意识到所有的数不都是有理数的时候,我们引入了无理数; 当我们意识到所有的数不都是实数的时候,我们引入了虚数。在数学上,这叫做数的扩充;在计算机里,这叫做数据溢出。数学作为一本学科,可以通过完善理论来自圆其说;而编程语言里数据结构,是在一开始就定义好的一套规范,它无法更不应该经常去修改,关于如何去解决程序中数据溢出的问题,这已然是一个新的问题了,不过我们可以看看古罗马人是怎么做的。

  聪明的罗马人自然想到了这个问题,他们提出的解决方案是这样的:在一个数字的上面加一条横线,表示这个数增值1000倍。所以,按照这个定义,4000应该由IV变化而来,9000应该由10000变化而来,而10000则可以看作是10的1000倍,即10000应该由X变化而来。我们在最初的规则中为什么没有说这一条呢?因为在数字上面增加一条横线,这更接近一个书写的行为,它增加了我们程序解析的难度,当一个数字的上面出现横线以后,我们就不能再按照原来的方式去转换。所以,考虑这个因素,实际上还是为了简化问题本身,这道题目中同样回避了这个问题。罗马人这个想法的确很好,可以解决眼下我们所面临的问题,可时间久了以后,罗马人发现这套计数规则书写了繁琐复杂,因而这套规则渐渐地就被人们放弃了。在2015年意大利官方宣布,国内街道编码、文件编码等全部废弃原有的罗马数字,改为使用阿拉伯数字。

选择阿拉伯数字

  历史最终选择了阿拉伯数字,而不是罗马数字,这并不是一个巧合,尽管罗马数字要比阿拉伯数字早2000年。罗马数字的缺陷不仅仅在于其书写的繁杂,一个更重要的原因是,它不能更好地推动数学学科的发展。罗马人发明罗马数字的目的是为了计数,可一旦产生了数,就势必会产生计算。可我们发现罗马数字并不适合计算,因为它对数字的构造并不是正交的。一个最为直观的例子是,数字可能会用一个字母、两个字母或者三个字母来表示,如果两个数字要进行加减法,我们会发现它的数字是无法”对齐“的,你必须非常小心地分清楚不同的数位,而罗马数字恰好是没有数位的概念的。同样,当数字加减时会产生进位或者借位,罗马数字的构造会导致牵一发而动全身,因为任何一个中间步骤,我们都必须将其记录下来,记录的代价是将整个结果重写。反观阿拉伯数字,0到9共10个数字可以表示一切,形式上的统一让计算更加便捷,书写更为简洁,这套定义可以扩展到无限大的数上面去,可以扩展到小数、分数甚至无理数、虚数。这是否意味着,一个统一化的定义或者构造,更适合去做相关的运算流程或者逻辑流程呢?

本文小结

  本文从一道有趣的题目作为引子,引出这篇文章的主题:罗马数字。我们首先为大家回顾了罗马数字的历史渊源。罗马数字是一种由古罗马人创造的数字系统,这套数字系统主要的用途是进行计数。罗马数字由I、V、X、L、C、D、M共7个基本数字组成,其基本规则是最多重复三次、左减右增。接下来,我们分析了罗马数字与阿拉伯数字相互转换的规律,并提供相关代码实现。在当前方案的基础上,我们引出了罗马数字中的”4000“问题,联系计算机中的数据溢出的相关概念,我们分析了为什么当罗马数字超过4000时会发生”溢出“,以及罗马人是如何解决这个问题的。虽然罗马数字比阿拉伯数字早2000年,可历史最终选择了阿拉伯数字,这里我们简要地分析了原因,因为罗马数字并不适合计算,而数字作为数学的基本要素,一个不能被运用到计算出的数字系统,最终免除不了被人们抛弃的命运。好了,这篇五一节前的文章 就是这样啦,4月再见!