Beyond the Void
BYVoid
USACO 2.2.1 Preface Numbering 羅馬數字轉換 preface
本文正體字版由OpenCC轉換

相信許多人遇到這道題都暈了,羅馬數字的規則的確太複雜了。想了解羅馬數字的看這裏: 羅馬數字介紹

理解簡單的(題目上3500以內)羅馬數字轉化規則後再看這道題會發現它並不難,就是將1..n的每個十進制阿拉伯數字轉化成相應的羅馬數字串,然後統計每個字母出現的次數就可以了。

關鍵在於轉化阿拉伯數字(其實較大的羅馬數字轉化很複雜,而題中3500以內的羅馬數字轉化還是比較簡單的,所以只討論如何轉化3500以內的羅馬數字)。

轉化有以下規則: 1、數較大部分在前,較小部分在後 2、表示10整倍數的字母(I X C M)最多可以累加三次 3、要累加4次的數應該將比該數的字母稍大的表示5整倍數或是10的整倍數的字母在後,累加的字母在前(例如IV XL CD CM)

瞭解以上規則後發現並不需要實際“轉化”出羅馬數字,而只用統計每個字母出現的次數。可以用遞歸解決問題了。

/*
ID: cmykrgb1
PROG: preface
LANG: C++
*/
#include <stdio.h>
#include <string.h>

FILE *fi,*fo;

static char ch[7]={'I','V','X','L','C','D','M'};
long int t[100];

void getrome(int n)
{
    if (n&gt;=1000) //M
    {
        t['M']++;
        getrome(n-1000);
    }else
	if (n&gt;=900) //CM
	{
	    t['C']++;
	    t['M']++;
	    getrome(n-900);
	}
	else
    if (n&gt;=500)
    {
        t['D']++;
        getrome(n-500);
    }
    else
        if (n&gt;=400)
        {
            t['C']++;
            t['D']++;
            getrome(n-400);
        }
        else
        if (n&gt;=100)
        {
            t['C']++;
            getrome(n-100);
        }
        else
        if (n&gt;=90)
        {
            t['X']++;
            t['C']++;
            getrome(n-90);
        }
        else
        if (n&gt;=50)
        {
            t['L']++;
            getrome(n-50);
        }
        else
        if (n&gt;=40)
        {
            t['X']++;
            t['L']++;
            getrome(n-40);
        }
        else
        if (n&gt;=10)
        {
            t['X']++;
            getrome(n-10);
        }
        else
        if (n&gt;=9)
        {
            t['I']++;
            t['X']++;
            getrome(n-9);
        }
        else
        if (n&gt;=5)
        {
            t['V']++;
            getrome(n-5);
        }
        else
        if (n&gt;=4)
        {
            t['I']++;
            t['V']++;
            getrome(n-4);
        }
        else
        if (n&gt;=1)
        {
            t['I']++;
            getrome(n-1);
        }
}

int main(void)
{
    int n,i;char c;
    fi=fopen("preface.in","r");
    fo=fopen("preface.out","w");
    fscanf(fi,"%d",&amp;n);
    fclose(fi);
    for (i=1;i&lt;=n;i++)
        getrome(i);
    for (i=0;i&lt;=6;i++)
        if (t[ch[i]]&gt;0)
            fprintf(fo,"%c %ldn",ch[i],t[ch[i]]);
    fclose(fo);
    return 0;
}

上次修改時間 2017-05-17

相關日誌