• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z funckją usunFragmenty

Object Storage Arubacloud
0 głosów
274 wizyt
pytanie zadane 27 lutego 2023 w C i C++ przez martinez369 Początkujący (460 p.)
edycja 28 lutego 2023 przez martinez369

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

komentarz 27 lutego 2023 przez tangarr Mędrzec (154,860 p.)
Czym jest "sznur"?
Jak wygląda struktura/klasa Node?
Co ma robić funkcja usunFragmenty?
komentarz 28 lutego 2023 przez martinez369 Początkujący (460 p.)
już dodałe treść sorry zapomniałem

1 odpowiedź

0 głosów
odpowiedź 28 lutego 2023 przez tangarr Mędrzec (154,860 p.)

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

 

komentarz 28 lutego 2023 przez martinez369 Początkujący (460 p.)
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
komentarz 28 lutego 2023 przez tangarr Mędrzec (154,860 p.)

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
}

 

komentarz 28 lutego 2023 przez martinez369 Początkujący (460 p.)
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
komentarz 28 lutego 2023 przez tangarr Mędrzec (154,860 p.)
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?)

Podobne pytania

0 głosów
1 odpowiedź 149 wizyt
pytanie zadane 6 marca 2023 w C i C++ przez martinez369 Początkujący (460 p.)
0 głosów
1 odpowiedź 253 wizyt
0 głosów
2 odpowiedzi 112 wizyt
pytanie zadane 3 sierpnia 2023 w C i C++ przez martinez369 Początkujący (460 p.)

92,684 zapytań

141,589 odpowiedzi

320,073 komentarzy

62,044 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...