a013 - 羅馬數字
題目描述
題目要求讀入兩個以羅馬數字表示的正整數，計算它們的差的絕對值，並將結果以羅馬數字形式輸出。如果差為零，則輸出 "ZERO"。
解題思路
程式首先將輸入的兩個羅馬數字轉換為整數。轉換的過程中，需要考慮羅馬數字的減法規則（例如 IV 表示 4，IX 表示 9）。然後計算兩個整數的差的絕對值。最後，將結果的整數轉換回羅馬數字，並輸出。轉換回羅馬數字的過程，使用貪心演算法，從最大的羅馬數字符號開始，盡可能多地減去，直到差為零。
複雜度分析
- 時間複雜度: O(N)，其中 N 是羅馬數字字串的長度。轉換羅馬數字為整數和整數轉羅馬數字都需要遍歷字串。
- 空間複雜度: O(1)，程式使用的額外空間是常數級別。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main (){
string a;
string b;
int c=0;
int d=0;
int x=0;
while(1){
cin >> a >> b;
if(a=="#"){
break;
}
if(a==b){
cout << "ZERO" << endl;
}
for(int i=0;i<b.length();i++){//I IV V IX X XL L XC C CD D CM M
if(b[i]=='I'){d++;
if(b[i+1]=='V'){d+=3;i++;
}
else if(b[i+1]=='X'){d+=8;i++;
}
}
else if(b[i]=='V'){d+=5;
}
else if(b[i]=='X'){d+=10;
if(b[i+1]=='L'){d+=30;i++;
}
else if(b[i+1]=='C'){d+=80;i++;
}
}
else if(b[i]=='L'){d+=50;
}
else if(b[i]=='C'){d+=100;
if(b[i+1]=='D'){d+=300;i++;
}
else if(b[i+1]=='M'){d+=800;i++;
}
}
else if(b[i]=='D'){d+=500;
}
else if(b[i]=='M'){d+=1000;
}
}
for(int i=0;i<a.length();i++){
if(a[i]=='I'){c++;
if(a[i+1]=='V'){c+=3;i++;
}
else if(a[i+1]=='X'){c+=8;i++;
}
}
else if(a[i]=='V'){c+=5;
}
else if(a[i]=='X'){c+=10;
if(a[i+1]=='L'){c+=30;i++;
}
else if(a[i+1]=='C'){c+=80;i++;
}
}
else if(a[i]=='L'){c+=50;
}
else if(a[i]=='C'){c+=100;
if(a[i+1]=='D'){c+=300;i++;
}
else if(a[i+1]=='M'){c+=800;i++;
}
}
else if(a[i]=='D'){c+=500;
}
else if(a[i]=='M'){c+=1000;
}
}
x=c-d;
if(x<0){
x=-x;
}
while(x>=1000){
cout << "M";
x-=1000;}
while(x>=900){
cout << "CM";
x-=900;}
while(x>=500){
cout << "D";
x-=500;}
while(x>=400){
cout << "CD";
x-=400;}
while(x>=100){
cout << "C";
x-=100;}
while(x>=90){
cout << "XC";
x-=90;}
while(x>=50){
cout << "L";
x-=50;}
while(x>=40){
cout << "XL";
x-=40;}
while(x>=10){
cout << "X";
x-=10;}
while(x>=9){
cout << "IX";
x-=9;}
while(x>=5){
cout << "V";
x-=5;}
while(x>=4){
cout << "IV";
x-=4;}
while(x>=1){
cout << "I";
x--;}
cout << endl;
c=0;
d=0;
}
return 0;
}