Problem 344 Roman Digititis，羅馬數字

此題是輸入一個數字 n，要你算出以羅馬數字表示從 1 ~ n 內，共出現幾次 i、v、x、l、c。

首先還是設計一個結構(struct)，順便將這結構宣告 101 個的陣列：

struct RomanNum
{
   int i;
   int v;
   int x;
   int l;
   int c;       
};

struct RomanNum RN[101];

接著我們可以用函式來建立陣列在整個羅馬數字出現的次數，因為羅馬數字最大範圍只到100，但整數40、90排列比較特殊，所以要優先處理，寫成如以下程式碼：

void adder(int index, int n)
{
     if (n == 0) return;
     if (n >= 40 && n <= 49)
         RN[index].l ++, RN[index].x ++, n -= 40;     
     if (n >= 90 && n <= 99)
         RN[index].c ++, RN[index].x ++, n -= 90;
     if (n % 10 == 4)
         RN[index].v ++, RN[index].i ++, n -= 4;     
     if (n % 10 == 9)
         RN[index].x ++, RN[index].i ++, n -= 9;
     if (n / 100 > 0)
         RN[index].c += (n/100), n %= 100;
     if (n / 50 > 0)
         RN[index].l += (n/50), n %= 50;
     if (n / 10 > 0)
         RN[index].x += (n/10), n %= 10;
     if (n / 5 > 0)
         RN[index].v += (n/5), n %= 5;
     if (n / 1 > 0)
         RN[index].i += (n/1), n %= 1;                    
}

以上函式的 index 代表陣列索引值，而 n 則為欲分解的羅馬數字(以10進位傳入)。我們可以在主程式內寫一迴圈，將上一陣列索引羅馬數字的總和傳遞給下一陣列索引羅馬數字，再進行累加：

for (i = 0; i < 100; i ++)
{
    adder(i, i + 1);
    RN[i + 1].i = RN[i].i, RN[i + 1].v = RN[i].v, 
    RN[i + 1].x = RN[i].x;
    RN[i + 1].l = RN[i].l, RN[i + 1].c = RN[i].c;  
}

如此一來，只須對應所輸入的值，將陣列索引印出即可：

while (1)
{
    scanf("%d", &n);
    if (n == 0) break;
    n -= 1;
    printf("%d: %d i, %d v, %d x, %d l, %d c\n", n+1, 
            RN[n].i, RN[n].v, RN[n].x, RN[n].l, RN[n].c);  
}

By David.K

p344題目連結
回ACM題庫目錄
回首頁