【本文鏈接】
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 <string>
#include <iostream>
#include <map>
#include <assert.h>
using namespace std;
// roman to integer
unsigned int roman2integer(string str)
{
// 99 -->10,100,1,10
// 66 --->50,10,5,1
if (str == "")
return 0;
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;
int sum = m[str[0]];
int len = str.length();
for (int i = 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 2*m[i]
sum = sum + m[str[i + 1]] - 2 * m[str[i]];
}
}
return sum;
}
#define MAX 3999
// integer to roman
string integer2roman(unsigned int n)
{
// we should consider 4,9,40,90,400,900
string result = "";
if (n < 1 || n > MAX)
return result;
unsigned int val[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
unsigned int length = sizeof(val) / sizeof(int);
string r[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < length; i++)
{
while(n >= val[i])
{
result += r[i];
n -= val[i];
}
}
return result;
}
// test case for two functions
void test_case(int n)
{
for (int i = 1; i <= n; i++)
{
string roman = integer2roman(i);
int integer = roman2integer(roman);
assert(i == integer);
}
}
void test_main()
{
//test_case(20);
test_case(MAX);
}
int _tmain(int argc, _TCHAR *argv[])
{
test_main();
return 0;
}
上面給出了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
