Działania na stringach

Działania na stringach
0

Witam,
mam na celu znalezienie NWD dla dużych liczb, wykraczających poza przedział long long. Operacji dokonuje na stringach, jednak pojawia się jeden szkopuł dla dużych liczb - program się crashuje z niewiadomych dla mnie przyczyn. Kilkakrotnie analizowałem kod, ale nie widzę, że niespójności logicznych. Proszę o pomoc. Kod ma 90 linijek, stąd wiem, że jego przejrzenie może okazać się nieco trudne.```

Kopiuj
#include <iostream>
#include <cstring>
using namespace std;

inline string odejmij(string a, string b){
    //WYNIK WYJSCIOWY Z DODAWANIA
    string wynik = "";

    //DLUGOSC STRINGOW
    int strAd, strBd;

    //PRZENIESIENIE
    int p = 0;

    //WYROWNANIE LICZB
    while(a.size() - b.size() > 0) b = "0" + b;

    cout << a << ' ' << b << endl;

    strAd = a.size() - 1;
    strBd = b.size() - 1;

    while(strAd >= 0 || strBd >= 0){
        //buforA, buforB, wynik
        int bufA = 0;
        int bufB = 0;
        int w = 0;

        if(strAd >= 0) bufA = a[strAd] - 48; else bufA = 0;
        if(strBd >= 0) bufB = b[strBd] - 48; else bufB = 0;

        if((bufA - bufB - p ) < 0) { w = bufA - bufB - p + 10; p = 1; }
        else if((bufA - bufB - p) == 0) { w = 0; p = 0; }
        else {w = bufA - bufB - p; p = 0;}

        wynik = "0" + wynik;
        wynik[0] = 48 + w;

        strAd--;
        strBd--;
    }

    string wynikF = "";

    //USUNIECIE ZER Z POCZATKU
    int s = 0;
    for(int i = 0; i < wynik.size(); i++){
        if(wynik[i] == 48) s += 1;
        else break;
    }

    for(int i = s; i < wynik.size(); i++){
        wynikF += wynik[i];
    }

    if(wynikF.size() == 0) wynikF += 48;

    return wynikF;
}

inline string NWD(string, string);

inline string wiekszy(string strA, string strB){
    int dlA = strA.size();
    int dlB = strB.size();

    if(dlA > dlB) { return NWD(odejmij(strA, strB), strB); }
    else if(dlB > dlA) { return NWD(odejmij(strB, strA), strA); }
    else{
        for(int i = 0; i < dlA; i++){
            if(strA[i] > strB[i]) { return NWD(odejmij(strA, strB), strB);}
            else if(strA[i] < strB[i]) { return NWD(odejmij(strB, strA), strA);}
        }
    }
}

inline string NWD(string a, string b){
    if(a == b) return a;
    else return wiekszy(a, b);
}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);

    string strA, strB;
    cin >> strA >> strB;

    cout << NWD(strA, strB);
}
edytowany 1x, ostatnio: kq
lion137
Po co wymyslac kolo, Nie lepiej uzyc bibliotek?
0
Wielki Kaczor napisał(a):

Witam,
mam na celu znalezienie NWD dla dużych liczb, wykraczających poza przedział long long. Operacji dokonuje na stringach, jednak pojawia się jeden szkopuł dla dużych liczb - program się crashuje z niewiadomych dla mnie przyczyn. Kilkakrotnie analizowałem kod, ale nie widzę, że niespójności logicznych. Proszę o pomoc. Kod ma 90 linijek, stąd wiem, że jego przejrzenie może okazać się nieco trudne.```

Kopiuj
#include <iostream>
#include <cstring>
using namespace std;

inline string odejmij(string a, string b){
    //WYNIK WYJSCIOWY Z DODAWANIA
    string wynik = "";

    //DLUGOSC STRINGOW
    int strAd, strBd;

    //PRZENIESIENIE
    int p = 0;

    //WYROWNANIE LICZB
    while(a.size() - b.size() > 0) b = "0" + b;

    cout << a << ' ' << b << endl;

    strAd = a.size() - 1;
    strBd = b.size() - 1;

    while(strAd >= 0 || strBd >= 0){
        //buforA, buforB, wynik
        int bufA = 0;
        int bufB = 0;
        int w = 0;

        if(strAd >= 0) bufA = a[strAd] - 48; else bufA = 0;
        if(strBd >= 0) bufB = b[strBd] - 48; else bufB = 0;

        if((bufA - bufB - p ) < 0) { w = bufA - bufB - p + 10; p = 1; }
        else if((bufA - bufB - p) == 0) { w = 0; p = 0; }
        else {w = bufA - bufB - p; p = 0;}

        wynik = "0" + wynik;
        wynik[0] = 48 + w;

        strAd--;
        strBd--;
    }

    string wynikF = "";

    //USUNIECIE ZER Z POCZATKU
    int s = 0;
    for(int i = 0; i < wynik.size(); i++){
        if(wynik[i] == 48) s += 1;
        else break;
    }

    for(int i = s; i < wynik.size(); i++){
        wynikF += wynik[i];
    }

    if(wynikF.size() == 0) wynikF += 48;

    return wynikF;
}

inline string NWD(string, string);

inline string wiekszy(string strA, string strB){
    int dlA = strA.size();
    int dlB = strB.size();

    if(dlA > dlB) { return NWD(odejmij(strA, strB), strB); }
    else if(dlB > dlA) { return NWD(odejmij(strB, strA), strA); }
    else{
        for(int i = 0; i < dlA; i++){
            if(strA[i] > strB[i]) { return NWD(odejmij(strA, strB), strB);}
            else if(strA[i] < strB[i]) { return NWD(odejmij(strB, strA), strA);}
        }
    }
}

inline string NWD(string a, string b){
    if(a == b) return a;
    else return wiekszy(a, b);
}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);

    string strA, strB;
    cin >> strA >> strB;

    cout << NWD(strA, strB);
}

biblioteki do czego?

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:około 14 godzin
  • Postów:4896
0

"biblioteki do czego?"
Na przyszłość, na komentarze Odpowiadaj w komentarzach, bo po dodaniu komentarza jeszcze nie obserwuje się wątku. A co do meritum, biblioteki do liczenia NWD dla bigintegerów, na przykład takiej jak ta. Zadałem proste pytanie, można na nie prosto odpowiedzieć, a nie odbijać piłeczkę.


edytowany 1x, ostatnio: lion137
MarekR22
goście nie mogą dodawać komentarzy
0
lion137 napisał(a):

"biblioteki do czego?"
Na przyszłość, na komentarze Odpowiadaj w komentarzach, bo po dodaniu komentarza jeszcze nie obserwuje się wątku. A co do meritum, biblioteki do liczenia NWD dla bigintegerów, na przykład takiej jak ta. Zadałem proste pytanie, można na nie prosto odpowiedzieć, a nie odbijać piłeczkę.

Z tego, co widzę, jako użytkownik niezarejestrowany nie mogę dodawać odpowiedzi bezpośrednio pod pytanie. Złośliwości w moim pytaniu nie było, pytam do czego mogłaby się biblioteka odnosić, bo jakoś nie spotkałem się nigdy z budowanymi funkcjami bibliotecznymi dla wyznaczania NWD, operując na stringach. Mimo wszystko jednak najbardziej zależy mi na znalezieniu nieścisłości w tym, co już napisałem, dlatego założyem ten wątek. ;) Jeżeli masz jakieś uwagi i zastrzeżenia do kodu, dlaczego program się crashuje, to z wdzięcznością przeczytam.

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:około 14 godzin
  • Postów:4896
0
Wielki Kaczor napisał(a):
lion137 napisał(a):

"biblioteki do czego?"
Na przyszłość, na komentarze Odpowiadaj w komentarzach, bo po dodaniu komentarza jeszcze nie obserwuje się wątku. A co do meritum, biblioteki do liczenia NWD dla bigintegerów, na przykład takiej jak ta. Zadałem proste pytanie, można na nie prosto odpowiedzieć, a nie odbijać piłeczkę.

Z tego, co widzę, jako użytkownik niezarejestrowany nie mogę dodawać odpowiedzi bezpośrednio pod pytanie. Złośliwości w moim pytaniu nie było, pytam do czego mogłaby się biblioteka odnosić, bo jakoś nie spotkałem się nigdy z budowanymi funkcjami bibliotecznymi dla wyznaczania NWD, operując na stringach. Mimo wszystko jednak najbardziej zależy mi na znalezieniu nieścisłości w tym, co już napisałem, dlatego założyem ten wątek. ;) Jeżeli masz jakieś uwagi i zastrzeżenia do kodu, dlaczego program się crashuje, to z wdzięcznością przeczytam.

Nie doszukiwałem się złosliwości, zwróciłem tylko uwagę, że zadałem proste pytanie, a Ty Odbiłeś piłeczkę. Do rzeczy.
To właśnie Spotkałeś taką bibliotekę liczacą NWD na stringach.
A co do Twojego kodu, to Przejechałęś go debugerem?


PanRiK
  • Rejestracja:ponad 7 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Szczecin
  • Postów:104
0
Kopiuj
       for(int i = 0; i < dlA; i++){
            if(strA[i] > strB[i]) { return NWD(odejmij(strA, strB), strB);}
            else if(strA[i] < strB[i]) { return NWD(odejmij(strB, strA), strA);}

Ta pętla nie ma sensu, bo nigdy nie wykona się do końca, ponieważ po pierwszym przebiegu zawsze zakończy działanie funkcji i zwróci daną wartość.

Czyli zawsze i = 0.


Jeśli widzisz mój błąd to mnie popraw.
Pisanie błędnych wypowiedzi utrwala złe praktyki.
Kiedyś możesz dostać do ręki mój kod.
edytowany 1x, ostatnio: PanRiK
0
PanRiK napisał(a):
Kopiuj
       for(int i = 0; i < dlA; i++){
            if(strA[i] > strB[i]) { return NWD(odejmij(strA, strB), strB);}
            else if(strA[i] < strB[i]) { return NWD(odejmij(strB, strA), strA);}

Ta pętla nie ma sensu, bo nigdy nie wykona się do końca, ponieważ po pierwszym przebiegu zawsze zakończy działanie funkcji i zwróci daną wartość.

Czyli zawsze i = 0.

ale przecież może zajść sytuacja strA[i] == strB[i]? wtedy w celu ustalenia, który string przechowuje większą wartość musimy dalej iterować po tablicy i przejść do jej następnej komórki?

PanRiK
faktycznie to się zgadza
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:mniej niż minuta
0

Wygląda mi to na zadanie ze SPOJ-a, lub czegoś pokrewnego.
Najlepiej jakbyś tego nie ukrywał i pokazał link. Często są triki, które pozwalają uniknąć operacji na dużych liczbach i obliczyć coś dużo szybciej.
NWD dla dużych liczb zrobiony za pomocą jedynie odejmowania, to będzie bardzo wolne.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
0
MarekR22 napisał(a):

Wygląda mi to na zadanie ze SPOJ-a, lub czegoś pokrewnego.
Najlepiej jakbyś tego nie ukrywał i pokazał link. Często są triki, które pozwalają uniknąć operacji na dużych liczbach i obliczyć coś dużo szybciej.
NWD dla dużych liczb zrobiony za pomocą jedynie odejmowania, to będzie bardzo wolne.

screenshot-20171211170042.png

Linka nie jestem w stanie podrzucić, jedynie zdjęcie zadania.

MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:mniej niż minuta
0

I jeszce to:

Kopiuj
prog.cc:47:22: warning: comparison of integers of different signs: 'int' and 'std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-compare]
    for(int i = 0; i < wynik.size(); i++){
                   ~ ^ ~~~~~~~~~~~~
prog.cc:52:22: warning: comparison of integers of different signs: 'int' and 'std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-compare]
    for(int i = s; i < wynik.size(); i++){
                   ~ ^ ~~~~~~~~~~~~
prog.cc:75:1: warning: control may reach end of non-void function [-Wreturn-type]
}
^
prog.cc:83:31: warning: implicit conversion of NULL constant to 'bool' [-Wnull-conversion]
    ios_base::sync_with_stdio(NULL);
    ~~~~~~~~                  ^~~~
                              false
4 warnings generated.

trzeci warning jest największym problemem.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
0
MarekR22 napisał(a):

I jeszce to:

Kopiuj
prog.cc:47:22: warning: comparison of integers of different signs: 'int' and 'std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-compare]
    for(int i = 0; i < wynik.size(); i++){
                   ~ ^ ~~~~~~~~~~~~
prog.cc:52:22: warning: comparison of integers of different signs: 'int' and 'std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-compare]
    for(int i = s; i < wynik.size(); i++){
                   ~ ^ ~~~~~~~~~~~~
prog.cc:75:1: warning: control may reach end of non-void function [-Wreturn-type]
}
^
prog.cc:83:31: warning: implicit conversion of NULL constant to 'bool' [-Wnull-conversion]
    ios_base::sync_with_stdio(NULL);
    ~~~~~~~~                  ^~~~
                              false
4 warnings generated.

trzeci warning jest największym problemem.

rzeczywiście niedopuszczalny. wychodzi na to, że z funkcją inline string wiekszy(string, string) jest coś nie tak. ale co? przecież na moje oko nie pomijam żadnego przypadku i zawsze zostanie zwrócona jakiś string. można jeszcze dopuścić się dopisania po pętli for() return NWD(odejmij(strA, strB), strA) - tak dla pewności. jednak i tak nic to nie daje.

0

problem pojawia się także przy większych liczbach, działając na mniejszych, zwraca poprawny wynik

vpiotr
  • Rejestracja:ponad 13 lat
  • Ostatnio:prawie 3 lata
0

Mnie ciekawi skad takie zainteresowanie akurat tym tematem (patrz strona glowna). Czyzby chwytliwy tytul?

0
vpiotr napisał(a):

Mnie ciekawi skad takie zainteresowanie akurat tym tematem (patrz strona glowna). Czyzby chwytliwy tytul?

Zawsze mogłem dodać "odejmowanie stringów", nie mówiąc już o ich zdejmowaniu. ;)

PanRiK
  • Rejestracja:ponad 7 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Szczecin
  • Postów:104
0

Ogólnie problem leży po stronie kompilatora, bo jeżeli dasz NWD z cyfr np. co ma jedna ma 99znaków, a druga 10, to kompilator uznaje, że za długo będzie się to robiło i do niczego to nie dojdzie.

W odejmowaniu, przed wyświetlaniem zmiennych wstawiłem sleepa, z biblioteką:

Kopiuj
Sleep(10);
Kopiuj
#include "windows.h"

i to:

Kopiuj
        wynik = "0" + wynik;
        wynik[0] = 48 + w;

zmieniłem na:

Kopiuj
wynik = to_string(w)+ wynik;

Tak, jest to dokładnie to samo, ale działa dla większych liczb, lub przez przypadek mi zadziałało.

Sleepa dałem, bo jakoś mój kompilator nie wywalał tak szybko błędów, tylko jechał do samego końca.

Chyba gdzieś w ustawieniach kompilatora można zmienić , żeby nie wywalał tak szybko

Do testowania zadania polecam cyfry, które się od siebie różnią.


Jeśli widzisz mój błąd to mnie popraw.
Pisanie błędnych wypowiedzi utrwala złe praktyki.
Kiedyś możesz dostać do ręki mój kod.
edytowany 3x, ostatnio: PanRiK
0
PanRiK napisał(a):

Ogólnie problem leży po stronie kompilatora, bo jeżeli dasz NWD z cyfr np. co ma jedna ma 99znaków, a druga 10, to kompilator uznaje, że za długo będzie się to robiło i do niczego to nie dojdzie.

W odejmowaniu, przed wyświetlaniem zmiennych wstawiłem sleepa, z biblioteką:

Kopiuj
Sleep(10);
Kopiuj
#include "windows.h"

i to:

Kopiuj
        wynik = "0" + wynik;
        wynik[0] = 48 + w;

zmieniłem na:

Kopiuj
wynik = to_string(w)+ wynik;

Tak, jest to dokładnie to samo, ale działa dla większych liczb, lub przez przypadek mi zadziałało.

Sleepa dałem, bo jakoś mój kompilator nie wywalał tak szybko błędów, tylko jechał do samego końca.

Chyba gdzieś w ustawieniach kompilatora można zmienić , żeby nie wywalał tak szybko

Do testowania zadania polecam cyfry, które się od siebie różnią.

Dziękuję za inicjatywę, ale to jednak nie to. Pozmieniałem tak, jak zaleciłeś, ale dla danych: 1111111 55 wciąż wywala błąd. To problem nam się trafił...

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:około 14 godzin
  • Postów:4896
0

Dalej uważam, że lepiej użyć gotowej biblioteki do wielkich liczb, ale skoro Chcesz tak. Jakyś miał działające odejmowanie - znaczy takie, że przy próbie odjęcia wiekszej od mniejszej da w wyniku zero, to można by to łatwo zaimplementować.
Potrzeba tylko dwóch funkcji: <=, oraz mod.
Mniejszy lub równy mógłby wyglądać tak:

Kopiuj
fun less_or_eq(a, b):
    if sub(a, b) == ZERO:
        return true;
    else:
        return false;

I modulo:

Kopiuj
fun mod(a, b):
    if less_or_eq(b, a):
        return mod(sub(a, b), b);
    else:
        return a;

I finalnie GCD:

Kopiuj
fun gcd(a, b):
    if b = 0:
        return a;
    else:
        return gcd(b, mod(a, b));

Predykat równości, jeśli wszystko działa dobrze, to powinno być sprawdzenie czy string jest postaci: "0".
A jesli odejmowanie wywala błąd przy próbie odjęcia większej od mniejszej, to albo je zmienić (tak by było najlepiej, bo Miałbys już gotowe - tylko przepisać funkcje, które Ci podałem w pseudokodzie), albo napisać porównanie:
Nie jestem tego pewien, ale algorytm mógłby być taki:

  • Dłuższy string, to większa liczba;
  • Gdy równej długości, to ten z pierwszą cyfrą większą (jako int, oczywiście) jest wiekszy;
  • Gdy pierwsze cyfry równe, to ten z następną wiekszą cyfrą jest większy;
  • I tak dalej aż do ostatniej cyferki.

EDIT:
wydaje sie, że ten sposób na zaimplementowanie <=, powinien działać:

Kopiuj
fun less_or_eq(m, n):
    if length(m) > length(n):
        return False
    else if length(n) > length(m):
        return True
    else:
        for indeks in length(m):
            if int(m[indeks]) > int(n[indeks]):
                return False
            else if int(n[indeks]) > int(m[indeks]):
                return True
            else:
                continue
        return True

edytowany 1x, ostatnio: lion137
0
lion137 napisał(a):

Dalej uważam, że lepiej użyć gotowej biblioteki do wielkich liczb, ale skoro Chcesz tak. Jakyś miał działające odejmowanie - znaczy takie, że przy próbie odjęcia wiekszej od mniejszej da w wyniku zero, to można by to łatwo zaimplementować.
Potrzeba tylko dwóch funkcji: <=, oraz mod.
Mniejszy lub równy mógłby wyglądać tak:

Kopiuj
fun less_or_eq(a, b):
    if sub(a, b) == ZERO:
        return true;
    else:
        return false;

I modulo:

Kopiuj
fun mod(a, b):
    if less_or_eq(b, a):
        return mod(sub(a, b), b);
    else:
        return a;

I finalnie GCD:

Kopiuj
fun gcd(a, b):
    if b = 0:
        return a;
    else:
        return gcd(b, mod(a, b));

Predykat równości, jeśli wszystko działa dobrze, to powinno być sprawdzenie czy string jest postaci: "0".
A jesli odejmowanie wywala błąd przy próbie odjęcia większej od mniejszej, to albo je zmienić (tak by było najlepiej, bo Miałbys już gotowe - tylko przepisać funkcje, które Ci podałem w pseudokodzie), albo napisać porównanie:
Nie jestem tego pewien, ale algorytm mógłby być taki:

  • Dłuższy string, to większa liczba;
  • Gdy równej długości, to ten z pierwszą cyfrą większą (jako int, oczywiście) jest wiekszy;
  • Gdy pierwsze cyfry równe, to ten z następną wiekszą cyfrą jest większy;
  • I tak dalej aż do ostatniej cyferki.

EDIT:
wydaje sie, że ten sposób na zaimplementowanie <=, powinien działać:

Kopiuj
fun less_or_eq(m, n):
    if length(m) > length(n):
        return False
    else if length(n) > length(m):
        return True
    else:
        for indeks in length(m):
            if int(m[indeks]) > int(n[indeks]):
                return False
            else if int(n[indeks]) > int(m[indeks]):
                return True
            else:
                continue
        return True

czyli zakładasz, że błąd wynika z tego, iż w którymś momencie liczba w string się zeruje / staje się ujemna?

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:około 14 godzin
  • Postów:4896
0
Wielki Kaczor napisał(a):

czyli zakładasz, że błąd wynika z tego, iż w którymś momencie liczba w string się zeruje / staje się ujemna?

Nie wiem, nie wiem jak ma działać Twoje gcd bez funkjcji modulo. Ja bym tego nie poprawiał tylko od nowa napisał tak jak podałem; jak będa jakies błędy będzie łatwiej debugować, bo jest podzielone na jak najmniejsze funkcje.


0

Napisałem kod od nowa:

Kopiuj
#include <iostream>
#include <cstring>
#include <windows.h>
using namespace std;

inline string odejmij(string a, string b){
    //WYNIK WYJSCIOWY Z DODAWANIA
    string wynik = "";

    //DLUGOSC STRINGOW
    int strAd, strBd;

    //PRZENIESIENIE
    int p = 0;

    //WYROWNANIE LICZB
    while(a.size() - b.size() > 0) b = "0" + b;

    strAd = a.size() - 1;
    strBd = b.size() - 1;

    while(strAd >= 0 || strBd >= 0){
        //buforA, buforB, wynik
        int bufA = 0;
        int bufB = 0;
        int w = 0;

        if(strAd >= 0) bufA = a[strAd] - 48; else bufA = 0;
        if(strBd >= 0) bufB = b[strBd] - 48; else bufB = 0;

        if((bufA - bufB - p ) < 0) { w = bufA - bufB - p + 10; p = 1; }
        else if((bufA - bufB - p) == 0) { w = 0; p = 0; }
        else {w = bufA - bufB - p; p = 0;}

        wynik = to_string(w) + wynik;

        strAd--;
        strBd--;
    }

    string wynikF = "";

    //USUNIECIE ZER Z POCZATKU
    int s = 0;
    for(int i = 0; i < wynik.size(); i++){
        if(wynik[i] == 48) s += 1;
        else break;
    }

    for(int i = s; i < wynik.size(); i++){
        wynikF += wynik[i];
    }

    if(wynikF.size() == 0) wynikF += 48;

    return wynikF;
}

inline string NWD(string, string);

inline string wiekszy(string strA, string strB){
    int dlA = strA.size();
    int dlB = strB.size();


    if(dlA > dlB) { return NWD(odejmij(strA, strB), strB); }
    else if(dlA < dlB) { return NWD(odejmij(strB, strA), strA); }
    else{
        for(int i = 0; i < dlA; i++){
            if(strA[i] > strB[i]) { return NWD(odejmij(strA, strB), strB);}
            else if(strA[i] < strB[i]) { return NWD(odejmij(strB, strA), strA);}
            else continue;
        }
        return NWD(odejmij(strA, strB), strB);
    }
}

inline string NWD(string a, string b){
    if(a == b) return a;
    else return wiekszy(a, b);
}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);

    string strA, strB;
    cin >> strA;
    cin >> strB;

    cout << NWD(strA, strB);
}

problem nie zniknął, pojawia się dla tych samych par danych wejściowych. ja już niczego nie wymyślę na chwilę obecną. pozostało mi biernie poddać się wskazówkom

0

EDIT:
Zły kod źródłowy podałem:

Kopiuj
#include <iostream>
#include <cstring>
using namespace std;

inline string odejmij(string a, string b){
    //WYNIK WYJSCIOWY Z DODAWANIA
    string wynik = "";

    //DLUGOSC STRINGOW
    int strAd, strBd;

    //PRZENIESIENIE
    int p = 0;

    //WYROWNANIE LICZB
    while(a.size() - b.size() > 0) b = "0" + b;

    strAd = a.size() - 1;
    strBd = b.size() - 1;

    while(strAd >= 0 || strBd >= 0){
        //buforA, buforB, wynik
        int bufA = 0;
        int bufB = 0;
        int w = 0;

        if(strAd >= 0) bufA = a[strAd] - 48; else bufA = 0;
        if(strBd >= 0) bufB = b[strBd] - 48; else bufB = 0;

        if((bufA - bufB - p ) < 0) { w = bufA - bufB - p + 10; p = 1; }
        else if((bufA - bufB - p) == 0) { w = 0; p = 0; }
        else {w = bufA - bufB - p; p = 0;}

        wynik = to_string(w) + wynik;

        strAd--;
        strBd--;
    }

    string wynikF = "";

    //USUNIECIE ZER Z POCZATKU
    int s = 0;
    for(int i = 0; i < wynik.size(); i++){
        if(wynik[i] == 48) s += 1;
        else break;
    }

    for(int i = s; i < wynik.size(); i++){
        wynikF += wynik[i];
    }

    if(wynikF.size() == 0) wynikF += 48;

    return wynikF;
}

inline bool mniejsze_rowne(string strA, string strB){
    if(strA.size() > strB.size()) return false;
    else if(strA.size() < strB.size()) return true;
    else{
        for(int i = 0; i < strA.size(); i++){
            if(strA[i] > strB[i]) return false;
            else if(strA[i] < strB[i]) return true;
            else continue;
        }
        return true;
    }
}

inline string mod(string strA, string strB){
    if(mniejsze_rowne(strB, strA))
        return mod(odejmij(strA, strB), strB);
    else
        return strA;
}

inline string nwd(string strA, string strB){
    if(strB == "0")
        return strA;
    else
        return nwd(strB, mod(strA, strB));
}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);

    string strA, strB;
    cin >> strA >> strB;

    cout << nwd(strA, strB);
}

PanRiK
  • Rejestracja:ponad 7 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Szczecin
  • Postów:104
0
Kopiuj
 while(strAd >= 0 || strBd >= 0)

Zamień na:

Kopiuj
 while(strAd > 0 || strBd > 0)

Wychodzisz po za zakres , bo w while masz odejmowanie tej wielkości

Edit: U mnie działa :D , tylko błędne wyniki są


Jeśli widzisz mój błąd to mnie popraw.
Pisanie błędnych wypowiedzi utrwala złe praktyki.
Kiedyś możesz dostać do ręki mój kod.
edytowany 3x, ostatnio: PanRiK
0
PanRiK napisał(a):
Kopiuj
 while(strAd >= 0 || strBd >= 0)

Zamień na:

Kopiuj
 while(strAd > 0 || strBd > 0)

Wychodzisz po za zakres , bo w while masz odejmowanie tej wielkości

Edit: U mnie działa :D , tylko błędne wyniki są

no właśnie, są błędne wyniki. uwaga słuszna i rzeczywiście przez moją nieuwagę docieraliśmy do -1 elementu tablicy, co mogło być potencjalnym powodem błędu. zrobiłem jeszcze w środku while() sprawdzenie:

Kopiuj
if(strAd == 0 || strBd == 0) break; else { strAd--; strBd--; }

bez skutku jednak :)

PanRiK
zrobiłem też warunek , przy definiowaniu: strAd i strBd, również bez skutku
0

Już brak pomysłów, co może być problemem? Zależy mi na rozwiązaniu, stąd moje zawzięcie.

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:około 14 godzin
  • Postów:4896
0
Wielki Kaczor napisał(a):

Już brak pomysłów, co może być problemem? Zależy mi na rozwiązaniu, stąd moje zawzięcie.

Czyli co, odejmowanie Nie dziala?


0

Panie tu dużo nie trzeba do zrobienia tego zadania.

BigInteger, musisz zrobić odejmowanie i porównywanie liczb.

czyli jak masz 24 tekst i 13 tekst to dodajesz od prawej do lewej 4+3 = 7, 0 przeniesienia. i 2+1 = 3 i 0 przeniesienia, a dalej pierwszy string się kończy i drugi tak samo.
Ewentualnie wspak możesz to zapisać to wtedy od lewej do prawej pojedziesz.

Porównywanie możesz zrobić kilku etapowo jeśli jeden string jest dłuższy od drugiego w sensie czy mają tyle samo znaków.
Jeśli nie mają to są różne (!=).

jeśli mają tyle samo znaków, to sprawdzasz od najbardziej znaczącego i dopóki najbardziej znaczący nie jest większy to przechodzisz tak aż do ostatniego.
Najbardziej znaczący to np. z 1234 to liczba 1, a najmniej znacząca, to 4, jeśli najbardziej znacząca jest większa w jednym ze stringów, to nie ma co dalej sprawdzać.

Jak odejmowanie będzie działać, bo w sumie dodawanie nie potrzebne, to wtedy implementujesz NWD algorytm na tym odejmowaniu.

Łączysz to razem i masz gotowy program.

0
lion137 napisał(a):
Wielki Kaczor napisał(a):

Już brak pomysłów, co może być problemem? Zależy mi na rozwiązaniu, stąd moje zawzięcie.

Czyli co, odejmowanie Nie dziala?

Na to wygląda.

0
0
Bogaty Rycerz napisał(a):

https://ideone.com/cuM6DU

odejmowania na a - b, gdzie a > b raczej nie powinniśmy rozpatrywać

0
Wielki Kaczor napisał(a):
Bogaty Rycerz napisał(a):

https://ideone.com/cuM6DU

odejmowania na a - b, gdzie a > b raczej nie powinniśmy rozpatrywać

  • b > a
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)