[Swust OJ 666]--初来乍到(题号都这么溜~~，递归，找规律)

题目链接：http://acm.swust.edu.cn/problem/0666/

Time limit(ms): 1000　　　　　　Memory limit(kb): 65535

Description

小李去埃及旅游，但是初来乍到的他不认识罗马数，所以请你将阿拉伯数n ( 0 < n <= 1000)改写为罗马数.

Input

N行数据，每行一个满足0 < n <= 1000的数；
结束以EOF判断

Output

每行一个,见输出示例

Sample Input

400

Sample Output

1=I

10=X

35=XXXV

99=XCIX

400=CD

基本数字:
I:一 V:五 X:十 L:五十 C:一百 D:五百 M:一千
记数方法
　　(1)相同的数字连写，所表示的数等于这些数字相加得到的数，如： Ⅲ = 3；
　　(2)小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：Ⅷ = 8；Ⅻ = 12；
　　(3)小的数字，(限于Ⅰ、X 和 C)在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ = 4；Ⅸ = 9；
　　(4)在一个数的上面画一条横线，表示这个数增值 1 000 倍，如：Ⅻ = 12 000 。
编辑本段
组数规则
　　(1)基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
　　(2)不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
　　(3)V 和 X 左边的小数字只能用Ⅰ。
　　(4)L 和 C 左边的小数字只能用×。
　　(5)D 和 M 左边的小数字只能用 C 。

Hint

解题思路：这里讲两种方法，像这类题纯粹找规律，做这道题时，我分析了多个数的组成方式。例如1=I,2=II,3=III,4=IV,5=V,6=VI,7=VII,8=VIII,9=IX,10=X······

　　　　　其实后面的数都和1~9的形式一样，只需要分析每位的数值就行；下面是一些关键数值39=XXXIX,40=XL,49=XLIX,50=L,89=LXXXIX,90=XC······

　　　　　因此想399，499，899这几种数就是分界点；最后只需从首位递归下去就可以了~~~

代码如下：

 #include<iostream>

 using namespace std;

 char key[], X[] = " IXCMVLD";//数的五倍用i+4表示

 int cnt;

 void Rserve(int x){

     int i, cur = , k = , lp = ;

     while (x > cur){

         cur =  * cur + ;

         k++;

     }

     for (i = ; i < k; i++, lp *= );

     if (x <=  * lp - ){

         for (i = ; i < x / lp; i++)

             key[cnt++] = X[k];

     }

     else if (x <=  * lp - ){

         key[cnt++] = X[k];

         key[cnt++] = X[k + ];

     }

     else if (x <=  * lp - ){

         key[cnt++] = X[k + ];

         for (i = ; i < x / lp - ; i++)

             key[cnt++] = X[k];

     }

     else{

         key[cnt++] = X[k];

         key[cnt++] = X[k + ];

     }

     if (x%lp) Rserve(x%lp);

 }

 int main(){

     int i, x;

     while (cin >> x){

         cnt = ;

         Rserve(x);

         cout << x << '=';

         for (i = ; i < cnt; i++)

             cout << key[i];

         cout << endl;

     }

     return ;

 }

当然了这道题这么溜，直接分析数字的组成方式1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1，与这些数字相关联会发生比如3和4,8和9,之间数字构成有一个本质的变化，具体的看题目的规则吧，然后每一个数字对应一个罗马数字组合递归找就是了具体见下表

1000

900

500

400

100

很溜的代码如下：

 #include <iostream>

 #include <string>

 using namespace std;

 int x[] = { , , , , , , , , , , , ,  };

 string L[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

 string exchange(int n){

     string s;

     int i = ;

     while (n){

         if (n >= x[i]){

             n -= x[i];

             s += L[i];

         }

         else

             i++;

     }

     return s;

 }

 int main(){

     int n;

     while (cin >> n){

         cout << n << '=';

         cout << exchange(n) << endl;

     }

     return ;

 }

这个代码ce,不过拿来改造用来玩还是不错的，至少答案全正确

 #include <stdio.h>

 void main(){

     static char *a[][] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"

         "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XCC", "", "C", "CC", "CCC",

         "CD", "D", "DC", "DCC", "DCCC", "CM" };

     int n, t, i, m;

     printf("Please enter number:");

     scanf("%d", &n);

     printf("%d=", n);

     for (m = , i = ; m < ; m++, i /= ){

         t = (n%i) / (i / );

         printf("%s", a[ - m][t]);

     }

     printf("\n");

 }

秒客网

[Swust OJ 666]--初来乍到(题号都这么溜~~，递归，找规律)

相关文章