a013: 羅馬數字

2019-08-02

內容

如果生活在數世紀之前的古羅馬，你應該用過 V 來表示五。V 和 5 這兩個符號都可以用來表示數目五。用來表示數目的符號稱作數字。而羅馬人用來表示數目的符號就是羅馬數字。

以下是七個基本的羅馬數字︰

羅馬數字	數目
I	1
V	5
X	10
L	50
C	100
D	500
M	1,000

所有其他的數目都是由這些數字組合而成。數目都是由左寫到右，通常值是等於組成的羅馬數字加起來。

例如十七可以表示為

X+V+I+I=XVII
10+5+1+1=17

表示羅馬數字可以使用減法來取代加法的規則。例如四可以不用四個一相加來表示 IIII，而採用五減一來表示 IV。利用這類規則，羅馬人能夠減化許多數目的表示方式，例如 IX 取代 VIIII 表示 9，及 CD 取代 CCCC 表示 400。

今日我們並不確定羅馬符號的起源為何。例如符號 V 的起源主要有兩個理論。有些學者認為五最早是用握拳、拇指在外的手勢來表示。最後以象形文字書寫而簡化為 V。

另一個理論認為 X 源自在 10 條線加上交叉線。因此五可以表示為 X 的一半，或是 V。

羅馬數字可以很容易地用來相加或相減，但算起乘除法就相當不順手。這就是為什麼現在羅馬數字並不常用的原因了。

問題
然而，羅馬數字還是經常用於書本章節及頁碼的編號。在這一題工作是讀入兩個正整數，然後輸出兩個數字差的絕對值。所有的數字都必須以羅馬數字來表示。而連續四個相同符號出現時，必須用減法規則來化簡之。

輸入

每個輸入檔中會有一個或以上的測試資料。每一行由兩個數字組成一筆測試資料，且所有數字將會小於 4,000。檔案最後會以符號 ## 表示結束。

I I
MM II
#

輸出

每筆測試資料的答案必須輸出到檔案中，並且換行。如果答案為零，則須輸出字串 ZERO。

ZERO
MCMXCVIII

解題思路

先將輸入的羅馬數字逐個轉成 int，並處理當前字元大於前一字元的例外情況，得到兩個整數相減後取絕對值即為答案，最後將答案用建好的表配合迴圈重新轉回羅馬數字輸出

完整程式碼

AC (1ms, 76KB)

#include<stdio.h>

typedef struct node
{
    char Str[3];
    int Val;
}Node;

int n, m, gap;
Node table[13] = { {"M" , 1000} , {"CM" , 900} ,{"D" , 500} ,{"CD" , 400}
                  ,{"C" , 100} ,{"XC" , 90} ,{"L" , 50} ,{"XL" , 40}
                  ,{"X" , 10} ,{"IX" , 9} ,{"V" , 5} ,{"IV" , 4} ,{"I" , 1} };

char strN[10], strM[10], strGap[10], * ptGap;

int toNum(char* src)
{
    char* pt = src - 1;
    int res = 0, prev, curr = 0;
    while (*(++pt))
    {
        prev = curr;
        if (*pt == 'I') curr = 1;
        else if (*pt == 'V') curr = 5;
        else if (*pt == 'X') curr = 10;
        else if (*pt == 'L') curr = 50;
        else if (*pt == 'C') curr = 100;
        else if (*pt == 'D') curr = 500;
        else if (*pt == 'M') curr = 1000;
        //
        if (prev < curr)
            res += curr - (prev << 1);
        else
            res += curr;
    }
    return res;
}

int main()
{
    while (scanf(" %s %s", strN, strM) == 2 && strN[0] != '#')
    {
        n = toNum(strN), m = toNum(strM);
        gap = n > m ? n - m : m - n;
        if (gap)
        {
            ptGap = strGap;
            for (int i = 0; i < 13; i++)
            {
                while (gap >= table[i].Val)
                {
                    char* tmp = table[i].Str - 1;
                    while (*(++tmp))
                        * ptGap++ = *tmp;
                    gap -= table[i].Val;
                }
            }
            *ptGap = '\0';
            puts(strGap);
        }
        else
        {
            puts("ZERO");
        }
    }
    return 0;
}