USACO 2.2.1 Preface Numbering 罗马数字转换 preface
相信许多人遇到这道题都晕了，罗马数字的规则的确太复杂了。想了解罗马数字的看这里： 罗马数字介绍
理解简单的（题目上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>=1000) //M
{
t['M']++;
getrome(n-1000);
}else
if (n>=900) //CM
{
t['C']++;
t['M']++;
getrome(n-900);
}
else
if (n>=500)
{
t['D']++;
getrome(n-500);
}
else
if (n>=400)
{
t['C']++;
t['D']++;
getrome(n-400);
}
else
if (n>=100)
{
t['C']++;
getrome(n-100);
}
else
if (n>=90)
{
t['X']++;
t['C']++;
getrome(n-90);
}
else
if (n>=50)
{
t['L']++;
getrome(n-50);
}
else
if (n>=40)
{
t['X']++;
t['L']++;
getrome(n-40);
}
else
if (n>=10)
{
t['X']++;
getrome(n-10);
}
else
if (n>=9)
{
t['I']++;
t['X']++;
getrome(n-9);
}
else
if (n>=5)
{
t['V']++;
getrome(n-5);
}
else
if (n>=4)
{
t['I']++;
t['V']++;
getrome(n-4);
}
else
if (n>=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",&n);
fclose(fi);
for (i=1;i<=n;i++)
getrome(i);
for (i=0;i<=6;i++)
if (t[ch[i]]>0)
fprintf(fo,"%c %ldn",ch[i],t[ch[i]]);
fclose(fo);
return 0;
}
上次修改时间 2017-05-17