13.Roman to Integerテーマと答えの詳細

6894 ワード

1テーマの簡単な説明
  Given aroman numeral, convert it to an integer.
  Input isguaranteed to be within the range from 1 to 3999.
ローマ数字を指定し、整数に変換します.
入力保証は1~3999の範囲です.
2答えの詳細
(1)ルール解析
まず、ローマ数字は7つあります.I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)です.次にローマの数のいくつかの規則を知って、まずこのような例を見てみましょう:アラビアの数字の1~11はローマの数字で表します:
I、II、III、IV、V、VI、VII、VIII、IX、X、XI
この例では、4つの一般的なルールについて説明します.
1)残りの数字のプレフィックスとしてI,X,Cのみが使用可能であり、例えばVM,LCは不正である.
2)I,X,C(1の先頭の数字、Mを除く)にとって、1回の使用量は最大4個までとすることはできない.これはIIIが不法であり、IVが正しく合法であり、またXXXXが不法であり、XLが正しく合法であるからである.
3)V,L,D(5の先頭の数字)については,1回の使用量が最大で1個となっているが,これはVVが10を表すことができず,Xが10を表すためである.
4)また、XIIXは、前の3つのルールに合致し、XIとIX、すなわち11と9に分けて20を加算するが、XXは20を表すため、XIIXは違法である.同様に、DCCCDも不正です.ps:アラビア数字はローマ数字の表現しかありません.
注意:ローマ数字表示法には、数字に横線を付けて1000倍の数を表すルールもありますが、今回の問題では、上記の4つのルールは十分に解決されています.
(2)解決策
このルールによれば、C++を用いてプログラムを記述し、C++のC言語特性において重要な点はオブジェクト向けプログラミング(OOP)であるため、今回の設計は、格納されたデータ型がvectorのコンテナであることを示すクラスの方法で実現される.設計は全体的に2つのステップに分けて行われます.
1)入力されたローマ数字が合法かどうかを初歩的に判断する.まず、入力したアルファベットにローマ数字以外の数字が7つ含まれている場合は不法です.そして、前の3つのルールに違反した場合は、不法です.合法的な数字を順番に容器に入れます.初歩的な判断が正しい場合、第4のルールに違反することは避けられない.第4の規則の合法性に合致するかどうかについては、初歩的な合法的な数字をアラビア数字に変換する際の判断に残す.
2)容器を最初から巡回し,高位から低位まで各項目を結果に順次加える.接頭辞のある項については、接頭辞の数字(例えばIV、IX)が1つしかないので、I、X、Cがそれより大きい数字に遭遇した場合、その組み合わせが表すアラビア数字の値(例えばIVを4、IXを9と求める)を求める.接尾辞のある項目については、VIIIが5+1+1の値であるため、組み合わせる必要はありません.4番目のルールの処理では、結果に加えられたアイテムが上位から下位に加算されていることがわかるので、加算の過程で、前に加えられたアイテムが後に加えられたアイテムより小さい場合は、不正(例えばXIIX:9+1+10、1対10が小さいため、この数字は不正)であり、これは上位から下位に加えられたアイテムがますます小さくなる可能性があるためである.最後に,保証ローマ数字の値が1~3999の範囲であることについては,最後の結果から判断する.
(3)設計手順
設計したプログラムはクラステンプレートを採用し,今回のテンプレート設計はその延長性とコード再利用性を体現していないが,この目的で身につけた習慣である.手順は次のとおりです.
#include 
#include 
#include 

using std::cin;
using std::cerr;
using std::cout;
using std::endl;
using std::vector;

void display(char& c)
{
    cout << c;
}

template
class RomanToInteger
{
private:
    vector romans_;
public:
    RomanToInteger(const vector& romans = vector(0)):romans_(romans) {}
    int result();
private:
    void judge();
    void exit_() {
        cerr << "Wrong Input" << endl;
        exit(EXIT_FAILURE);
    }
    void out_range() const {
        cerr << "Out of Range" << endl;
        exit(EXIT_FAILURE);
    }
};

template
void RomanToInteger::judge()
{
    typename vector::iterator it;
    int count;
    int left;
    for(it = romans_.begin(); it != romans_.end(); it++) {
        left = distance(it,romans_.end());
        if(left == 0) {
            exit_();
        } else if(*it == 'C' or *it == 'X' or *it == 'I') {
            if(left > 3 and *it == *(it + 1) and *it == *(it + 2) and *it == *(it + 3)) {
                exit_();
            } else if(left > 1 and *it == 'I' and (*(it + 1) == 'L' or *(it + 1) == 'C'
                                                   or *(it + 1) == 'D' or *(it + 1) == 'M')) {
                exit_();
            } else if(left > 1 and *it == 'X' and (*(it + 1) == 'D' or *(it + 1) == 'M')) {
                exit_();
            }
        } else if(*it == 'D' or *it == 'L' or *it == 'V') {
            if(left > 1 and *it == *(it + 1)) {
                exit_();
            } else if(left > 1 and *it == 'V' and (*(it + 1) == 'X' or *(it + 1) == 'L'
                                                   or *(it + 1) == 'C' or *(it + 1) == 'D' or *(it + 1) == 'M')) {
                exit_();
            } else if(left > 1 and *it == 'L' and (*(it + 1) == 'C' or *(it + 1) == 'D'
                                                   or *(it + 1) == 'M')) {
                exit_();
            } else if(left > 1 and *it == 'D'and *(it + 1) == 'M') {
                exit_();
            }
        }
    }
    cout << "The Number is:";
    for_each(romans_.begin(),romans_.end(),display);
    cout << endl;
    return;
}

template
int RomanToInteger::result()
{
    judge();
    int res(0);
    int add(0);
    int add_before(0);
    typename vector::iterator it;
    for(it = romans_.begin(); it != romans_.end(); it++) {
        if(*it == 'I') {
            if(*(it + 1) ==  'X') {
                add = 9;
                it++;
            } else if(*(it + 1) == 'V') {
                add = 4;
                it++;
            } else {
                add = 1;
            }
        } else if(*it == 'V') {
            add = 5;
        } else if(*it == 'X') {
            if(*(it + 1) == 'C') {
                add = 90;
                it++;
            } else if(*(it + 1) == 'L') {
                add = 40;
                it++;
            } else {
                add = 10;
            }
        } else if(*it == 'L') {
            add = 50;
        } else if(*it == 'C') {
            if(*(it + 1) == 'M') {
                add = 900;
                it++;
            } else if(*(it + 1) == 'M') {
                add = 400;
                it++;
            } else {
                add = 100;
            }
        } else if(*it == 'D') {
            add = 500;
        } else if(*it == 'M') {
            add = 1000;
        }
        if(!add_before) {
            add_before = add;
        } else if(add_before < add) {
            exit_();
        } else {
            add_before = add;
        }
        res += add;
        if(res > 3999) {
            out_range();
        }
    }
    if(res == 0) {
        out_range();
    }
    return res;
}

int main()
{
    vector vec;
    char ch;
    int res;
    cout << "Please Iuput Number of Roman:";
    while((ch = cin.get()) != '
') { if(ch != 'M'and ch != 'D'and ch != 'C'and ch != 'L'and ch != 'X'and ch != 'V' and ch != 'I') { cerr << "Wrong Input" << endl; exit(EXIT_FAILURE); } else { vec.push_back(ch); } } RomanToInteger rti(vec); res = rti.result(); cout << "Integer Number:" << res << endl; }

今回は4種類の異なる入力状況の運転結果をテストし、
実行結果:
Please Iuput Number of Roman:ASDCFWrong Input
Please Iuput Number of Roman:VX       Wrong Input
Please Iuput Number of Roman:XIIXThe Number is:XIIXWrong Input
Please Iuput Number of Roman:MDCLXVI The Number is:MDCLXVIInteger Number:1666