【本文链接】
http://www.cnblogs.com/hellogiser/p/roman-to-integer-and-integer-to-roman.html
【题目】
给出一个罗马数字，转换为阿拉伯数字。本题只考虑3999以内的数。
罗马数字有如下符号：
Ⅰ（1）Ⅴ（5）Ⅹ（10）L（50）C（100）D（500）M（1000）
计数规则：
(1).若干相同数字连写表示的数是这些罗马数字的和，如III=3；
(2).小数字在大数字前面表示的数是用大数字减去小数字，如IV＝4；
(3).小数字在大数字后面表示的数是用大数字加上小数字，如VI=6;
组合规则：
(1)基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
(2)不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
(3)V 和 X 左边的小数字只能用Ⅰ。
(4)L 和 C 左边的小数字只能用×。
(5)D 和 M 左 边的小数字只能用 C 。
【分析】
（1）罗马数字转阿拉伯数字：
从前往后遍历罗马数字，如果某个数比前一个数小，则把该数加入到结果中；反之，则在结果中两次减去前一个数并加上当前这个数；
比如XVIII=18，是如何得到的？其对应的阿拉伯数字表示为10_5_1_1_1，因此结果为10+5+1+1+1=18；
XIX=19是如何得到的？其对应的阿拉伯数字表示为10_1_10，因此结果为10+1+10-2*1=19。
（2）阿拉伯数字转罗马数字：
把所有小数字在前的组合也作为基本数字，做一个对应的数值映射表。
比如4=1-5=IV,9=1-10=IX,40=10-50=XL,90=10-100=XC,400=100-500=CD, 900=100-1000=CM。
那么可以得到对应的映射为：
unsigned int val[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
string r[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
对于阿拉伯数字n，遍历val数组，如果n>=val[i]，则结果保留r[i]，同时更新n=n-val[i]，直到n=0为止。
【测试】
给定一个数字n，利用integer2raman函数转换为罗马数字r，然后再利用roman2integer函数将r转换为m，那么如果n!=m，则说明函数有问题。如果相等，则函数正确。
【代码】
C++ Code
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
// Roman2Integer.cpp : Defines the entry point for the console application. // / version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/5/26 / #include"stdafx.h" #include // roman to integer unsignedintroman2integer(string str) { // 99 -->10,100,1,10 // 66 --->50,10,5,1 if(str =="") return0; map<char,int> m; m['I'] =1; m['V'] =5; m['X'] =10; m['L'] =50; m['C'] =100; m['D'] =500; m['M'] =1000; intsum = m[str[0]]; intlen = str.length(); for(inti =0; i < len -1; i++) { if(m[str[i]] >= m[str[i +1]]) { // m[i]>=m[i+1], then add m[i+1] to sum sum = sum + m[str[i +1]]; } else { // m[i]<m[i+1], then add m[i+1] to sum, and remove 2m[i] sum = sum + m[str[i +1]] -2 m[str[i]]; } } returnsum; } #defineMAX3999 // integer to roman string integer2roman(unsignedintn) { // we should consider 4,9,40,90,400,900 string result =""; if(n <1|| n > MAX) returnresult; unsignedintval[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1}; unsignedintlength =sizeof(val) /sizeof(int); string r[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; for(inti =0; i < length; i++) { while(n >= val[i]) { result += r[i]; n -= val[i]; } } returnresult; } // test case for two functions voidtest_case(intn) { for(inti =1; i <= n; i++) { string roman = integer2roman(i); intinteger = roman2integer(roman); assert(i == integer); } } voidtest_main() { //test_case(20); test_case(MAX); } int_tmain(intargc, _TCHAR *argv[]) { test_main(); return0; } |
上面给出了roman2integer和integer2roman的实现，并且对函数进行了测试。对于1到3999的数字n，求得其对应的罗马数字为r，再将r转换为阿拉伯数字m，那么n应该和m相等。因而test_case中的assert(i == integer);语句能够正常运行，而不抛出异常。
【参考】
http://www.cnblogs.com/dosxp/archive/2008/08/13/1266781.html
http://blog.csdn.net/wzy_1988/article/details/17057929
http://blog.csdn.net/fightforyourdream/article/details/12934139
【本文链接】
http://www.cnblogs.com/hellogiser/p/roman-to-integer-and-integer-to-roman.html
原文链接: https://www.cnblogs.com/hellogiser/p/roman-to-integer-and-integer-to-roman.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/132591
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
