» Forum » Programowanie » [C, C++] Szukam pomocy

[C++] Zadanie SPOJ JSUMRZYM - Dodawanie rzymskie

Ostatnio zmodyfikowano 2020-11-15 19:51

Autor Wiadomość

Biedrzyk

Temat założony przez niniejszego użytkownika

» 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; // 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

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.

P-176180

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; // 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

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().

P-176193

Biedrzyk

Temat założony przez niniejszego użytkownika

» 2020-02-08 19:36:05

Jestem już krok dalej, dziękuję za naprowadzenie :)

P-176198

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):

//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

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.

P-176200

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.

P-176201

« 1 » 2

Strona 1 z 2

Następna strona

» Forum » Programowanie » [C, C++] Szukam pomocy