Board logo

標題: 下次題目-a013: 羅馬數字 [打印本頁]

作者: 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
作者: buy    時間: 2010-11-13 12:24

  1. #include <iostream>
  2. #include <string>
  3. #define N 7

  4. using namespace std;

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

  7. int iabs(const int& t);
  8. int to_arabic(string t);
  9. int to_arabic(char c);
  10. string to_roman(int t);

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

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

作者: buy    時間: 2010-11-18 17:17

不會大家都複製貼上吧
作者: b790113g    時間: 2010-12-18 11:08

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #define N 7

  5. using namespace std ;

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





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2