Problem z funckją usunFragmenty

Question

Cześć mam problem z funkcją poniżej

Oto treść:

"funkcję usunFragmenty usuwającą ze sznura ciągi sąsiednich elementów sznura w następujący
sposób: usuwamy P elementów sznura (lub tyle ile jest, gdy jest mniej), następnie omijamy
najdłuższy możliwy przynajmniej 2-elementowy ciągły fragment tworzący ciąg rosnący (jeśli taki
fragment istnieje), usuwamy P elementów, omijamy ciąg rosnący, itd. (P jest liczbą całkowitą
dodatnią będącą parametrem funkcji). Pamięć zajmowana przez usuwane elementy ma zostać
zwolniona. Funkcja nie może używać tablic, pomocniczych sznurów ani struktur danych
dostępnych w bibliotece standardowej (wektorów, list, kolejek, itp);"

Oto mój kod:

void sznur::usunFragmenty(int P)
{
   Node*zaszuk=nullptr;
   Node*szuk=pocz;
   while(true)
   {
        for(int i=0;i<P && szuk!=nullptr;i++) {
            Node *killer = szuk;
            szuk = szuk->nast;
            if (zaszuk == nullptr) {
                pocz = szuk;
            } else {
                zaszuk->nast = szuk;
            }
            delete killer;
            ileJest--;
        }
        if (szuk == nullptr) {
           return;
        }
        bool czy_znalezione=false;
        if(szuk->nast!=nullptr && szuk->nast->dane>szuk->dane)
        {
            czy_znalezione=true;
            zaszuk=szuk;
            szuk=szuk->nast;
        }
        if(szuk->nast != nullptr && czy_znalezione==true) {
            zaszuk = szuk;
            szuk = szuk->nast;
        }
   }
}

problem dotyczy sznura o wartościach wejściowych dla P=3 to  4,7,5,1,6,6,1,7,7,3,2,1,2,3,1 uzyska postać 1,6,1,2,3, u mnie ta funkcja uzyskuje tylko to 1,6,1,2, nie mogę uzyskać liczby 3 nie wiem już gdzie leży problem proszę o pomoc

Comments

Czym jest "sznur"?
Jak wygląda struktura/klasa Node?
Co ma robić funkcja usunFragmenty?

---

już dodałe treść sorry zapomniałem

Answer 1

Twoja funkcja nie szuka ciągu rosnącego! Zamiast tego sprawdza czy istnieją dwa elementy takie, że drugi jest większy od pierwszego. Dodaj sobie do funkcji wpisy debugujące przebieg i przeanalizuj co się dzieje

void sznur::usunFragmenty(int P)
{
   Node*zaszuk=nullptr;
   Node*szuk=pocz;
   while(true)
   {
       cout << "@ PETLA @" << endl;
        for(int i=0;i<P && szuk!=nullptr;i++) {
            Node *killer = szuk;
            szuk = szuk->nast;
            if (zaszuk == nullptr) {
                pocz = szuk;
            } else {
                zaszuk->nast = szuk;
            }
            cout << "i=" << i << " usuwam " << killer->dane << endl;
            delete killer;
            ileJest--;
        }
        if (szuk == nullptr) {
           return;
        }
        bool czy_znalezione=false;
        
        cout << "aktualny: " << szuk->dane << " nastepny: ";
        if (szuk->nast == nullptr)
            cout << "brak" << endl;
        else
            cout << szuk->nast->dane << endl;
        
        if(szuk->nast!=nullptr && szuk->nast->dane>szuk->dane)
        {
            cout << "__ warunek 1__" << endl;
            czy_znalezione=true;
            zaszuk=szuk;
            szuk=szuk->nast;
        }
        if(szuk->nast != nullptr && czy_znalezione==true) {
            cout << "__warunek 2__" << endl;
            zaszuk = szuk;
            szuk = szuk->nast;
        }
   }
}

 

Comments

Mam pytanie jak zrobić żeby funkcja faktycznie szukała ten ciąg rosnący? dla innych wartości działa ok a dla tej co podałem nie jeśli ona nie szuka ciągu rosnącego to jakim cudem to działa a nie powinno proszę o wytłumaczenie tej sytuacji

---

Ale przecież nie działa dla innych wartości.
Przetestuj kod dla "sznura" 4,4,4,1,2,3,4. Funkcja powinna zostawić 1,2,3,4 a twoja implementacja zostawi 1,2.

Dzieje się tak dlatego, że po usunięciu P elementów sprawdzasz tylko dwa elementy (aktualny i następny). Zupełnie nie bierzesz pod uwagę, że do ciągu rosnącego mogą należeć kolejne elementy.

Jeżeli nie potrafisz napisać tej funkcji to rozbij problem na mniejsze części. Napisz sobie funkcje pomocnicze. Na przykład:

void sznur::usunFragmenty(int P) {
    Node *node = pocz;
    while (true) {
        node = usun_kilka_elementow(node, P);
        if (node == nullptr)
            return;
        int dlugosc_ciagu = oblicz_dlugosc_ciagu_rosnacego(node);
        node = przesun_o_kilka_elementow(dlugosc_ciagu)
        if (node == nullptr)
            return;
    }
}

Node* sznur::usun_kilka_elementow(Node* node, int N) {
    // znajdz rodzica wezla node (zeby go zaktualizowac)
    // usun N elementow i zwroc wskaznik na kolejny nieusuniety element
    // jezeli node == pocz to zaktualizuj pocz
}

Node* sznur::dlugosc_ciagu(Node *node) {
   // iteruj po kolejnych węzłach tak długo póki wartość rośnie
   // zwróć ilość przeskoczonych węzłów
}

Node* sznur::przesun_o_kilka_elementow(int N) {
   //zwroc N-ty następnik
}

 

---

Zadam jeszcze dodatkowe pytanie do mojego kodu co należało by poprawić w moim kodzie żeby nie sprawdzać tylko dwóch elementów (aktualny i nastepny) ale i też kolejne elementy

---

Masz już wykrycie że dwa elementy tworzą ciąg rosnący. Zastanów się co trzeba zrobić, żeby wykryć jeszcze jeden element i potem jeszcze jeden i może jeszcze jeden i ...
(podpowiedź: od czego są pętle?)