Biedrzyk 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: #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; } if( itr->second == secondRomanLetter ) { b = itr->first; cout << b; } } int arabic = a + b; cout << arabic << endl; 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. |
|
pekfos |
» 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. |
|
Biedrzyk Temat założony przez niniejszego użytkownika |
» 2020-02-07 11:30:58 Zmieniłem pętlę w przypadku gdy arabic != itr -> first: #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; } if( itr->second == secondRomanLetter ) { b = itr->first; cout << b; } } int arabic = a + b; cout << arabic << endl; 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. |
|
pekfos |
» 2020-02-07 17:38:11 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(). |
|
Biedrzyk Temat założony przez niniejszego użytkownika |
» 2020-02-08 19:36:05 Jestem już krok dalej, dziękuję za naprowadzenie :) |
|
mizie |
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): #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" } };
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; }
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; }
|
|
pekfos |
» 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. |
|
Biedrzyk 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. |
|
« 1 » 2 |