[C++] Zadanie SPOJ JSUMRZYM - Dodawanie rzymskie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

[C++] Zadanie SPOJ JSUMRZYM - Dodawanie rzymskie

AutorWiadomość
Temat założony przez niniejszego użytkownika
[C++] Zadanie SPOJ JSUMRZYM - Dodawanie rzymskie
» 2020-02-06 11:07:01
Witam,
mam problem z wykonaniem zadania podanego w temacie. Link do zadania: https://pl.spoj.com/problems​/JSUMRZYM/.

Oto jego treść:

Dnia 01.01.2200 był sądnym dniem dla Eurolandu. Nowy przywódca zażądał, by zmienił się układ klawiatury komputera, zamiast cyfr arabskich miały pojawić się cyfry rzymskie. Natomiast same komputery miały wynik podawać w zapisie rzymskim. Cóż pozostało programistom komputerów... zabrali się do pracy. Na początku chcą zająć się operacją dodawania dwóch liczb rzymskich...
Input

Na wejściu w pojedyńczych wierszach podawane są dwie liczby rzymskie oddzielone spacją. Liczby rzymskie są z przedziału I..M (w zapisie arabskim 1..1000).
Output

Na wyjściu w osobnych wierszach podany jest wynik dodawania odpowiednich dwóch liczb podanych na wejściu w zapisie rzymskim.

Input:
I II
IV V
CXXIII CCLVI

Output:
III
IX
CCCLXXIX

Mój kod:

C/C++
#include <iostream>
#include <map>

using namespace std;

void translateRoman( string firstRomanLetter, string secondRomanLetter, map < int, string > rome )
{
    int a, b;
   
    for( map < int, string >::iterator itr = rome.begin(); itr != rome.end(); itr++ )
    {
        if( itr->second == firstRomanLetter )
        {
            a = itr->first;
            cout << a; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
        }
        if( itr->second == secondRomanLetter )
        {
            b = itr->first;
            cout << b; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
        }
    }
    int arabic = a + b;
   
    cout << arabic << endl; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
   
    for( map < int, string >::iterator itr = rome.begin(); itr != rome.end(); itr++ )
    {
        if( arabic == itr->first )
        {
            cout << itr->second << endl;
        }
        if( arabic != itr->first )
        {
            string newRomanLetter = "";
            for( map < int, string >::iterator itr = rome.begin(); itr != rome.end(); itr++ )
            {
                while( itr->first <= arabic )
                {
                    newRomanLetter += itr->second;
                    arabic -= itr->first;
                }
            }
            cout << newRomanLetter;
        }
    }
}

int main()
{
    string firstRomanLetter, secondRomanLetter;
    map < int, string > rome;
    map < int, string >::iterator itr;
   
    rome[ 1000 ] = "M";
    rome[ 900 ] = "CM";
    rome[ 500 ] = "D";
    rome[ 400 ] = "CD";
    rome[ 100 ] = "C";
    rome[ 90 ] = "XC";
    rome[ 50 ] = "L";
    rome[ 40 ] = "XL";
    rome[ 10 ] = "X";
    rome[ 9 ] = "IX";
    rome[ 8 ] = "VIII";
    rome[ 7 ] = "VII";
    rome[ 6 ] = "VI";
    rome[ 5 ] = "V";
    rome[ 4 ] = "IV";
    rome[ 3 ] = "III";
    rome[ 2 ] = "II";
    rome[ 1 ] = "I";
   
    cin >> firstRomanLetter;
    cin >> secondRomanLetter;
    translateRoman( firstRomanLetter, secondRomanLetter, rome );
   
    return 0;
}

Chcę to zrobić za pomocą mapy. Przy obliczeniu wyniku podaje mi odpowiedź ale jako wielokrotność I rzymskiej a nie tak jak trzeba. W zamyśle chodziło mi o to, żeby np. przy liczbie 1234 wstawić M i odjąć 1000 (mamy 234), potem wstawić C (mamy 134) itd. aż dojdziemy do zera.
P-176179
» 2020-02-06 17:16:31
Przy obliczeniu wyniku podaje mi odpowiedź ale jako wielokrotność I rzymskiej a nie tak jak trzeba. W zamyśle chodziło mi o to, żeby np. przy liczbie 1234 wstawić M i odjąć 1000 (mamy 234), potem wstawić C (mamy 134) itd. aż dojdziemy do zera.
W kodzie robisz dokładnie odwrotnie. Zaczynasz od I.
P-176180
Temat założony przez niniejszego użytkownika
» 2020-02-07 11:30:58
Zmieniłem pętlę w przypadku gdy arabic != itr -> first:
C/C++
#include <iostream>
#include <map>

using namespace std;

void translateRoman( string firstRomanLetter, string secondRomanLetter, map < int, string > rome )
{
    int a = 0, b = 0;
   
    for( map < int, string >::iterator itr = rome.begin(); itr != rome.end(); itr++ )
    {
        if( itr->second == firstRomanLetter )
        {
            a = itr->first;
            cout << a; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
        }
        if( itr->second == secondRomanLetter )
        {
            b = itr->first;
            cout << b; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
        }
    }
    int arabic = a + b;
   
    cout << arabic << endl; // na razie wstawilem, zeby sprawdzic czy dobrze liczy
   
    for( map < int, string >::iterator itr = rome.begin(); itr != rome.end(); itr++ )
    {
        if( arabic == itr->first )
        {
            cout << itr->second << endl;
        }
        if( arabic != itr->first )
        {
            string newRomanLetter = "";
            for( map < int, string >::iterator itr = rome.end(); itr != rome.begin(); itr-- )
            {
                while( itr->first <= arabic )
                {
                    newRomanLetter += itr->second;
                    arabic -= itr->first;
                }
            }
            cout << newRomanLetter;
        }
    }
}

int main()
{
    string firstRomanLetter = "", secondRomanLetter = "";
    map < int, string > rome;
    map < int, string >::iterator itr;
   
    rome[ 1000 ] = "M";
    rome[ 900 ] = "CM";
    rome[ 500 ] = "D";
    rome[ 400 ] = "CD";
    rome[ 100 ] = "C";
    rome[ 90 ] = "XC";
    rome[ 50 ] = "L";
    rome[ 40 ] = "XL";
    rome[ 10 ] = "X";
    rome[ 9 ] = "IX";
    rome[ 8 ] = "VIII";
    rome[ 7 ] = "VII";
    rome[ 6 ] = "VI";
    rome[ 5 ] = "V";
    rome[ 4 ] = "IV";
    rome[ 3 ] = "III";
    rome[ 2 ] = "II";
    rome[ 1 ] = "I";
   
    cin >> firstRomanLetter;
    cin >> secondRomanLetter;
    translateRoman( firstRomanLetter, secondRomanLetter, rome );
   
    return 0;
}

Ale gdy wpisuję C i C w wyniku podaje mi CCCCCCCCCCCII.
P-176188
» 2020-02-07 17:38:11
C/C++
for( map < int, string >::iterator itr = rome.end(); itr != rome.begin(); itr-- )
Ten zakres jest błędny. W pierwszym przebiegu pętli używasz niepoprawnego iteratora, a pierwszy element kolekcji jest zawsze pominięty. Do iterowania od końca jest rbegin() i rend().
P-176193
Temat założony przez niniejszego użytkownika
» 2020-02-08 19:36:05
Jestem już krok dalej, dziękuję za naprowadzenie :)
P-176198
Rzowiązanie
» 2020-02-08 19:53:38
Nie jestem przekonany czy mapa jest najlepszym z kontenerów dla tego algorytmu. Natomiast jeżeli upierasz się przy takim podejściu to trzeba pamiętać, o dwóch rzeczach. Po pierwsze niezależnie od sposobu inicjalizacji, mapa jest zawsze posortowana (dlatego w tym przypadku należy poruszać się po niej od tyłu). Po drugie, iterator mapy jest iteratorem dwukierunkowym (ang. bidirectional), a nie swobodnego dostępu (ang. random access). Skutek tego jest taki, że zdefiniowane są dla niego operatory inkrementacji (++) i dekrementacji, ale już wyrażenie iter += 1 jest niepoprawne. Mając to w pamięci twój program przy założeniu, że wprowadzane liczby rzymskie są poprawne, może wyglądać następująco (uczciwie mówię, że nie miałem czasu go dokładnie przetestować, więc będę wdzięczny za uwagi o napotkanych błędach):

C/C++
//Dodawanie dwóch liczb rzymskich, implementacja wykorzystująca mapę i C++
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::transform;

const map < int, string > roman {
    { 1000, "M" }, { 900, "CM" }, { 500, "D" }, { 400, "CD" }, { 100, "C" }, { 90, "XC" },
    { 50, "L" }, { 40, "XL" }, { 10, "X" }, { 9, "IX" }, { 5, "V" }, { 4, "IV" }, { 1, "I" }
};

//Konwersja liczba rzymska -> liczba dziesietna
int RomanToDec( std::string num ) {
    int len = num.size();
    int sum { 0 }, i { 0 };
    auto iter = roman.rbegin();
    while( i < len ) {
        if( num[ i ] == iter->second[ 0 ] && iter->second.size() == 1 ) {
            sum += iter->first;
            ++i;
        }
        else if( i < len - 1 && num.substr( i, 2 ) ==( ++iter )->second ) {
            sum += iter->first;
            i += 2;
            --iter;
        }
        else if( iter != roman.rend() ) {
            ++iter;
        }
    }
    return sum;
}

//Konwersja liczba dziesietna -> liczba rzymska
string DecToRoman( int n )
{
    string result = "";
    auto iter = roman.rbegin();
    while( n > 0 ) {
        if( n >= iter->first ) {
            n -= iter->first;
            result += iter->second;
        }
        else if( iter != roman.rend() )
             ++iter;
       
    }
    return result;
}

int main() {
    string firstRomanNum, secondRomanNum, result;
    cout << "Podaj pierwszy rzymski skladnik sumy: ";
    getline( cin, firstRomanNum );
    transform( firstRomanNum.begin(), firstRomanNum.end(), firstRomanNum.begin(),
    []( unsigned char c )->unsigned char { return std::toupper( c ); } );
    cout << "Podaj drugi rzymski skladnik sumy: ";
    getline( cin, secondRomanNum );
    transform( secondRomanNum.begin(), secondRomanNum.end(), secondRomanNum.begin(),
    []( unsigned char c )->unsigned char { return std::toupper( c ); } );
    result = DecToRoman( RomanToDec( firstRomanNum ) + RomanToDec( secondRomanNum ) );
    cout << "Rzymska suma wynosi: " << result << endl;
    cout << "co po przeliczeniu na system dziesietny daje: " << RomanToDec( result ) << endl;
    system( "PAUSE" );
    return 0;
}
P-176199
» 2020-02-08 20:00:04
Nie jestem przekonany czy mapa jest najlepszym z kontenerów dla tego algorytmu.
Skoro temat został już poruszony - oczywiście, że std::map<> się nie nadaje do tego zadania. Kontenery asocjacyjne służą do wyszukiwania, a te nie występuje w tym zadaniu, co czyni ten kontener jednym z najgorszych do tego zadania. To jest miejsce dla zwykłej tablicy.
P-176200
Temat założony przez niniejszego użytkownika
» 2020-02-08 21:08:43
Akurat do tego zadania dostałem dodatkowe zalecenie, żeby spróbować rozwiązać je za pomocą mapy - stąd moje próby.
P-176201
« 1 » 2
 Strona 1 z 2Następna strona