返回列表 發帖

Rank: 7Rank: 7Rank: 7
1# 跳轉到 » 倒序看帖
打印
tT
buy發表於 2010-11-13 12:23 | 只看該作者

下次題目-a013: 羅馬數字

http://zerojudge.tw/ShowProblem?problemid=a013

如果生活在數世紀之前的古羅馬，你應該用過 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。檔案最後會以符號 # 表示結束。
輸出說明 ：
每筆測試資料的答案必須輸出到檔案中，並且換行。如果答案為零，則須輸出字串 ZERO。
範例輸入 ：

I I MM II #
範例輸出 ：

ZERO MCMXCVIII
收藏 分享

Rank: 7Rank: 7Rank: 7
2#
buy發表於 2010-11-13 12:24 | 只看該作者
  1. #include <iostream>
  2. #include <string>
  3. #define N 7

  5. using namespace std;

  7. char roman[N] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
  8. int arabic[N] = {1000, 500, 100, 50, 10, 5, 1};

  10. int iabs(const int& t);
  11. int to_arabic(string t);
  12. int to_arabic(char c);
  13. string to_roman(int t);

  15. int main()
  16. {
  17.     for(;;)
  18.     {
  19.         string t1, t2;
  20.         cin >> t1;
  21.         
  22.         if(t1[0] == '#')
  23.             break;
  24.         else
  25.             cin >> t2;
  26.         
  27.         cout << to_roman(iabs(to_arabic(t1) - to_arabic(t2))) << endl;
  28.     }
  29.    
  30.     return 0;
  31. }

  33. inline int iabs(const int& t)
  34. {
  35.     return (t > 0)? t : -t;
  36. }
  37. inline int to_arabic(string t)
  38. {
  39.     int len = t.length(), array[len];
  40.    
  41.     for(int i = 0; i < len; i++)
  42.         array[i] = to_arabic(t[i]);
  43.    
  44.     len--;
  45.    
  46.     int tmp = array[len];
  47.    
  48.     for(int i = 0; i < len; i++)
  49.     {
  50.         if(array[i] < array[i+1])
  51.             tmp -= array[i];
  52.         else
  53.             tmp += array[i];
  54.     }
  55.    
  56.     return tmp;
  57. }
  58. inline int to_arabic(char c)
  59. {
  60.     for(int i = 0; i < N; i++)
  61.         if(c == roman[i])
  62.             return arabic[i];
  63. }
  64. inline string to_roman(int t)
  65. {
  66.     if(t == 0)
  67.         return "ZERO";
  68.    
  69.     string tmp;
  70.    
  71.     for(int j = 0; j < N; j += 2)
  72.     {
  73.         int k = t / arabic[j];
  74.         
  75.         if(k == 9)
  76.             tmp.push_back(roman[j]), tmp.push_back(roman[j-2]);
  77.         else if(k == 4)
  78.             tmp.push_back(roman[j]), tmp.push_back(roman[j-1]);
  79.         else
  80.         {
  81.             if(k > 4)
  82.                 tmp.push_back(roman[j-1]), k -= 5;
  83.             
  84.             for(int i = k; i > 0; i--)
  85.                 tmp.push_back(roman[j]);
  86.         }
  87.         
  88.         t %= arabic[j];
  89.     }
  90.    
  91.     return tmp;
  92. }
複製代碼

TOP

Rank: 7Rank: 7Rank: 7
3#
buy發表於 2010-11-18 17:17 | 只看該作者
不會大家都複製貼上吧
Mai  買大誠 [E-Mail : mainword@dlinfo.tw, mainword@gmail.com] 手機 : 0911-116194
Sun Certified Java Programmer

DL Info 鼎侖資訊 [886-7-969-0998] 高雄市苓雅區光華一路206號6樓之2

TOP

Rank: 7Rank: 7Rank: 7
4#
b790113g發表於 2010-12-18 11:08 | 只看該作者
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #define N 7

  6. using namespace std ;

  8. string roman[N] = {"M", "D", "C", "L", "X", "V", "I"};
  9. int arabic[N] = {1000, 500, 100, 50, 10, 5, 1};
  10.    
  11. int to_int(string s){
  12.     int tmp =0 ;
  13.     int m = 0 ;
  14.     for(int i=0;i<s.length();i++){
  15.         for(int j=0;j<N;j++){
  16.             string c = s.substr(i,1) ;
  17.             if( roman[j]== c){
  18.                 tmp += arabic[j];
  19.                 break;
  20.             }   
  21.         }
  22.     }
  23.     return tmp ;
  24. }
  25. string to_roman(int ab){
  26.     if(ab==0){
  27.         return "ZERO";         
  28.     }
  29.     string tmp ;
  30.     int t ;
  31.     for(int i=0;i<N;i+=2){
  32.         t = ab/arabic[i];
  33.         if(t==9||t==4){
  34.             int les = arabic[i-2] - t*arabic[i];
  35.             for(int j=0;j<N;j++){
  36.                 if(arabic[j]==les){
  37.                     tmp += roman[j];
  38.                     break;                  
  39.                 }  
  40.             }
  41.             tmp+=roman[i-2];
  42.         }else{
  43.               if(t>4){
  44.                    tmp += roman[i-1];
  45.                    t-=5 ;
  46.               }
  47.               for(int z=0;z<t;z++){
  48.                       tmp+=roman[i];
  49.               }
  50.         }
  51.         ab %= arabic[i];
  52.     }
  53.     return tmp ;
  54. }
  55. int main(){
  56.    
  57.     string s = "MM";
  58.     string s2 = "II" ;
  59.     int a ,b ;
  60.     a = to_int(s);
  61.     b = to_int(s2);
  62.     cout << to_roman(a-b) ;
  63.    
  64.     cout << endl ;
  65.     system("pause");
  66. }
複製代碼

TOP

返回列表