羅馬數字與阿拉伯數字的相互轉換
最近遇到一道非常有趣的題目，題目大意如下：有一個富翁在銀河系裡做生意，而銀河系使用的是羅馬數字，所以他需要一個精明能幹的助手，幫助他完成羅馬數字與阿拉伯數字的相互轉換，題目在這個背景下衍生出交易場景，我們需要幫助他計算出相關商品的價格。對於這道題目，如果剝離開這個題目本身的交易場景，這道題目本質上就是一個純粹的演算法問題。說來慚愧，博主當時並未能快速地解決這個問題，事後通過研讀別人的文章始能有所領悟。所以，今天想在這篇文章里，同大家一起來討論下這個問題。今天，全世界都在使用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，顯然這是不符合我們預期的。整理下我們的思路，這段代碼實現如下：
public static string ConvertToRoman(int number)
{
var output = new StringBuilder();
var digitMap = new Dictionary()
{
,,,,
,,,,
,,,,
};
var digits = digitMap.OrderByDescending(e => e.Key).ToList();
for (int i = 0; i 0; i++)
{
if (number
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位依次循環，判斷當前元素的正負然後累加，再加上最後一位元素的值即可。下面是代碼實現：
public static int ConvertToNumber(string romanNumber)
{
var number = 0;
var length = romanNumber.Length;
var digits = new Dictionary()
{
{"I",1},{"V",5},{"X",10},{"L",50},{"C",100},{"D",500},{"M",1000}
};
for (int i = 0; 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月再見！
TAG:5厘米的理想 |