JSUMRZYM Spoj, problem na wejściu

0

Rozwiązuję zadanie z serwisu SPOJ: https://pl.spoj.com/problems/JSUMRZYM/ Muszę użyć mapy. Po wpisaniu danych wejściowych program przestaje działać. Nie można wpisać innych danych, ani też nic się nie wyświetla. Czy problem dotyczy funkcji konwertujących, a może zamiany string na int?

#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;

const map < int, string > mapa {
    { 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 zRzymskiegoNaArabski (string liczba) {
    int dlugoscLiczby = liczba.size();
    int suma = 0;
    int i = 0;
    auto iter = mapa.rbegin();
    map <int, string> mapa;

    while (i < dlugoscLiczby) {
        if ((liczba[i] == iter -> second[0]) && (iter -> second.size() == 1)){
            suma += iter -> first;
            i++;
        }
        else if (i < dlugoscLiczby - 1 && liczba.substr (i, 2) == (++iter) -> second) {
            suma += iter -> first;
            i += 2;
            --iter;
        }
        else if (iter != mapa.rend()) {
            ++iter;
        }
    }

    return suma;
}

string zArabskiegoNaRzymski (int liczba) {
    string wynik = " ";
    auto iter = mapa.rbegin();

    while (liczba > 0) {
        if (liczba >= iter -> first) {
            liczba -= iter -> first;
            wynik += iter -> second;
        }
        else if (iter != mapa.rend()) {
            iter++;
        }
    }

    return wynik;

}


int main()
{
    string wynik;
    string liczbyRzymskie;
    std::string str = " ";
    int dlugosc, cyfra;



    do {
            getline (cin, liczbyRzymskie);

            liczbyRzymskie = str;

            zRzymskiegoNaArabski(liczbyRzymskie);

            cyfra = atoi(str.c_str());

            zArabskiegoNaRzymski(cyfra);

            wynik += cyfra;
            cout << liczbyRzymskie;


    } while (cin.get() != '\n');


    return 0;
}

0

A co mówi debugger? Program wywala się nawet dla danych testowych: https://wandbox.org/permlink/2RvfoNEhUnLDvtTc

0
kq napisał(a):

A co mówi debugger? Program wywala się nawet dla danych testowych: https://wandbox.org/permlink/2RvfoNEhUnLDvtTc
Błąd SIGSEV, dlatego podejrzewam, że problem jest w funkcji.

0

I debugger nic więcej nie mówi? Tylko SIGSEGV?

0
kq napisał(a):

I debugger nic więcej nie mówi? Tylko SIGSEGV?
Mówi, że jest jakiś 'thread' właśnie w tej funkcji

3
$ g++ -g -std=c++17 -Wall -Wextra -fsanitize=address 4progRoman.cpp -o 4progRoman
4progRoman.cpp:62:9: warning: unused variable 'dlugosc' [-Wunused-variable]
    int dlugosc, cyfra;
        ^
1 warning generated.
$ ./4progRoman
IV V
=================================================================
==33763==ERROR: AddressSanitizer: global-buffer-overflow on address 0x000100b4a7d8 at pc 0x000100b3aa19 bp 0x7ffeef0c9460 sp 0x7ffeef0c9458
READ of size 8 at 0x000100b4a7d8 thread T0
    #0 0x100b3aa18 in bool std::__1::__tree_is_left_child<std::__1::__tree_node_base<void*>*>(std::__1::__tree_node_base<void*>*) __tree:81
    #1 0x100b3a8af in std::__1::__tree_node_base<void*>* std::__1::__tree_prev_iter<std::__1::__tree_node_base<void*>*, std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>*>(std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>*) __tree:200
    #2 0x100b3a7c7 in std::__1::__tree_const_iterator<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::__tree_node<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, void*>*, long>::operator--() __tree:936
    #3 0x100b3a73b in std::__1::__map_const_iterator<std::__1::__tree_const_iterator<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::__tree_node<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, void*>*, long> >::operator--() map:875
    #4 0x100b3a691 in std::__1::reverse_iterator<std::__1::__map_const_iterator<std::__1::__tree_const_iterator<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::__tree_node<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, void*>*, long> > >::operator*() const iterator:697
    #5 0x100b38814 in std::__1::reverse_iterator<std::__1::__map_const_iterator<std::__1::__tree_const_iterator<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::__tree_node<std::__1::__value_type<int, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, void*>*, long> > >::operator->() const iterator:699
    #6 0x100b37ef0 in zRzymskiegoNaArabski(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >) 4progRoman.cpp:22
    #7 0x100b39ee1 in main 4progRoman.cpp:69
    #8 0x7fff67ecacc8 in start (libdyld.dylib:x86_64+0x1acc8)

0x000100b4a7d8 is located 0 bytes to the right of global variable 'mapa' defined in '4progRoman.cpp:9:27' (0x100b4a7c0) of size 24
SUMMARY: AddressSanitizer: global-buffer-overflow __tree:81 in bool std::__1::__tree_is_left_child<std::__1::__tree_node_base<void*>*>(std::__1::__tree_node_base<void*>*)
Shadow bytes around the buggy address:
  0x1000201694a0: f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
  0x1000201694b0: f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
  0x1000201694c0: f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9 f9
  0x1000201694d0: f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00
  0x1000201694e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1000201694f0: 00 00 00 00 00 00 00 00 00 00 00[f9]f9 f9 f9 f9
  0x100020169500: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100020169510: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100020169520: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100020169530: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100020169540: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==33763==ABORTING
Abort trap: 6
2

int zRzymskiegoNaArabski (string liczba) {
    int dlugoscLiczby = liczba.size();
    int suma = 0;
    int i = 0;
    auto iter = mapa.rbegin(); // zwróć uwagę na to
    map <int, string> mapa; // co to jest 
......
        else if (iter != mapa.rend()) { // a tu niespodzianka!!!! bo nie o to mapa.rend() chodzi
            ++iter;
        }
    }

    return suma;
}
2
else if (iter != mapa.rend()) {

masz tu podwójny błąd.

  1. porównujesz iteratory różnych map (masz w funkcji obiekt mapa zasłaniający ten globalny, którego iteratorem jest iter)
  2. nie obsługujesz poprawnie dojścia do końca iteracji.

Przyznam że to dość nietrywialny problem do zdiagnozowania. Mimo wszystko, sugeruję abyś się podszkoliła w obsłudze debuggera i innych narzędzi takich jak cośtam-sanitizery - to znakomite narzędzia, które będą Ci przydatne w przyszłości.

2

Jeżeli mogę coś jeszcze doradzić, oprócz solidnej nauki obsługi debuggera, to warto zmienić podejście do pisania kodu.
Zamiast pisać na ślepo i zmieniać kawałki kodu wyczekując momentu aż zadziała, zdefiniować cel, zaprojektować algorytm, zbudować mapę koncepcyjną, najlepiej na kartce papieru. Zastanowić się jakie warunki muszę być spełnione w poszczególnych miejscach w kodzie. Jakie są warunki stopu. I sprawdzić dla paru przypadków na kartce czy na pewno zadziała.

0

Dodam jeszcze, że z rzymskiego na arabki można przerobić prościej:

static const unordered_map<char, int> _roman_to_arabic {
    {'M', 1000}, {'D', 500}, {'C', 100}, {'L', 50}, {'X', 10}, {'V', 5}, {'I', 1}
};

int roman_to_arabic(const string &roman_num) {
    int result = 0, prev_val = 0;
    for (auto roman_symbol : roman_num) {
        int val = _roman_to_arabic.at(roman_symbol);
        result += (prev_val < val) ? val - 2 * prev_val : val;
        prev_val = val;
    }
    return result;
}

W drugą stronę nie potrzeba nawet pętli.

PS. Ciekawe, że na spoju można sprawdzić, że ostatnie submity dla tego problemu nie pochodzą od kobiety tylko od niejakiego Pana T.N. :D Ktoś tu podszywa się pod kobietę, by uzyskać pomoc? :D

0

Dlaczego teraz mój program nie dodaje poprawnie większych liczb, tj. IV + V. Zamiast dostać poprawny wynik, otrzymuję IIIIIIIIIIII ? Przy takim inpucie nie działają funkcje (nie następuje konwersja). Program od razu przechodzi do wyniku.

#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;
using std::transform;

const map < int, string > mapaRzymska {
    { 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 zRzymskiegoNaArabski (string liczba) {
    int dlugoscLiczby = liczba.size();
    int suma = 0;
    int i = 0;
    auto iter = mapaRzymska.begin();

    while (i < dlugoscLiczby) {
        if ((liczba[i] == iter -> second[0])) {//&& (iter -> second.size() == 1)){
            suma += iter -> first;
            i++;
        }
        else if (i < dlugoscLiczby - 1 && liczba.substr (i, 2) == (++iter) -> second) {
            suma += iter -> first;
            i += 2;
            --iter;
        }
        else if (iter != mapaRzymska.end()) {
            ++iter;
        }
    }

    return suma;
}

string zArabskiegoNaRzymski (int liczba) {
    string wynik = " ";
    auto iter = mapaRzymska.begin();

    while (liczba > 0) {
        if (liczba >= iter -> first) {
            liczba -= iter -> first;
            wynik += iter -> second;
        }
        else if (liczba >= iter -> first) {
            liczba -= iter -> first;
            wynik += iter -> first;
        }
        else if (iter != mapaRzymska.end()) {
            iter++;
        }
    }

    return wynik;

}


int main()
{
    string wynik;
    string liczbaRzymska1, liczbaRzymska2;
    int dlugosc, cyfra;



    while (cin >> liczbaRzymska1 >> liczbaRzymska2) {

            transform(liczbaRzymska1.begin(), liczbaRzymska1.end(), liczbaRzymska1.begin(),
            [] (unsigned char c) ->unsigned char {return std::toupper( c ); } );

            transform(liczbaRzymska2.begin(), liczbaRzymska2.end(), liczbaRzymska2.begin(),
            [] (unsigned char c) ->unsigned char {return std::toupper( c ); } );

      
            wynik = zArabskiegoNaRzymski(zRzymskiegoNaArabski(liczbaRzymska1) + zRzymskiegoNaArabski(liczbaRzymska2));
            cout << wynik;
            cout << endl;
    }


    cin.get(); cin.get();
//cin.get() != '\n'

    return 0;
}

0

Musisz mieć jakiś błąd w logice programu. Napisz testy dla obu funkcji i zobacz czy dobrze konwertuje.
Wyżej podałem sposób konwersji w jedną stronę. Na arabski łatwo konwertuje się zapamiętując ostatni przed obecnym symbol.
W drugą stronę, z z arabskich na rzysmkie, można sprawdzić ile raz liczba dzieli się przez 1000 (tysiace), potem ile razy liczba modulo 1000 dzieli się przez 100 (setki), ile razy liczba modulo 100 dzieli się przez 10 (dziesiętne) i na koniec to co zostało (jedności). Dla każdej z wygenerowanych liczb odszukać zahardkodowaną sekwencję ("jest ich 10 dla setek, 10 dla dziesiątek i 10 dla jedności, dla tysięcy wystarczy wstawić odpowiednią ilość M, ale chyba w treści napisali, że liczba nie przekracza 1000).

2

Dlaczego teraz mój program nie dodaje poprawnie większych liczb

W mapie **mapaRzymska **pierwszym elementem jest 1->"I", a nie 1000->"M". Zamień w funkcji **zArabskiegoNaRzymski ** wszystkie **begin() **na rbegin() oraz end() na rend();

0
Magda Pietrzykowska napisał(a):

Dlaczego teraz mój program nie dodaje poprawnie większych liczb, tj. IV + V. Zamiast dostać poprawny wynik, otrzymuję IIIIIIIIIIII ? Przy takim inpucie nie działają funkcje (nie następuje konwersja). Program od razu przechodzi do wyniku.

#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;
using std::transform;

const map < int, string > mapaRzymska {
    { 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 zRzymskiegoNaArabski (string liczba) {
    int dlugoscLiczby = liczba.size();
    int suma = 0;
    int i = 0;
    auto iter = mapaRzymska.begin();

    while (i < dlugoscLiczby) {
        if ((liczba[i] == iter -> second[0])) {//&& (iter -> second.size() == 1)){
            suma += iter -> first;
            i++;
        }
        else if (i < dlugoscLiczby - 1 && liczba.substr (i, 2) == (++iter) -> second) {
            suma += iter -> first;
            i += 2;
            --iter;
        }
        else if (iter != mapaRzymska.end()) {
            ++iter;
        }
    }

    return suma;
}

string zArabskiegoNaRzymski (int liczba) {
    string wynik = " ";
    auto iter = mapaRzymska.begin();

    while (liczba > 0) {
        if (liczba >= iter -> first) {
            liczba -= iter -> first;
            wynik += iter -> second;
        }
        else if (liczba >= iter -> first) {
            liczba -= iter -> first;
            wynik += iter -> first;
        }
        else if (iter != mapaRzymska.end()) {
            iter++;
        }
    }

    return wynik;

}


int main()
{
    string wynik;
    string liczbaRzymska1, liczbaRzymska2;
    int dlugosc, cyfra;



    while (cin >> liczbaRzymska1 >> liczbaRzymska2) {

            transform(liczbaRzymska1.begin(), liczbaRzymska1.end(), liczbaRzymska1.begin(),
            [] (unsigned char c) ->unsigned char {return std::toupper( c ); } );

            transform(liczbaRzymska2.begin(), liczbaRzymska2.end(), liczbaRzymska2.begin(),
            [] (unsigned char c) ->unsigned char {return std::toupper( c ); } );

      
            wynik = zArabskiegoNaRzymski(zRzymskiegoNaArabski(liczbaRzymska1) + zRzymskiegoNaArabski(liczbaRzymska2));
            cout << wynik;
            cout << endl;
    }


    cin.get(); cin.get();
//cin.get() != '\n'

    return 0;
}

Zapewne dlatego, że std::map < int, std::string > ustawia klucze w kolejności rosnącej, a nie tak jak są wpisane. (nie analizowałem dokładnie twojego kodu).

1 użytkowników online, w tym zalogowanych: 0, gości: 1