Zadanie maturalne o Przedziałach

Question

Witam. Robię zadanie polegające na wykonaniu sumy wszystkich 50-sięciu przedziałów znajdujących się w pliku, a następnie " w otrzymanym w ten sposób zbiorze wyszukaj najdłuższy nieprzerwany fragment zbioru. Jako rozwiązanie podaj zakres tego przedziału." (wartości A i B w przedziałach są liczbami całkowitymi z zakresu <-100,100>)

Mógłby ktoś doradzić co robię źle? moja odpowiedź ma zły koniec przedziału..

#include <iostream>
#include <fstream>

using namespace std;

struct S{
    char odkad, przecinek, dokad;
    int a, b;
};

S przedzialy[50];// <0, 200>
int suma[201];

void policz(int a, int b)
{
    for(int i = a; i <= b; i++)
    {
        suma[i] = 1;
    }
}

int main()
{
    ifstream wczytaj("przedzialy.txt");

    for(int i = 0; i < 50; i++)// wczytujemy dane
    {
        S X;
        wczytaj >> X.odkad >> X.a >> X.przecinek >> X.b >> X.dokad;
        X.a += 100; X.b += 100;
        przedzialy[i] = X;
    }

    for(int i = 0; i < 50; i++)
    {
        S akt = przedzialy[i];

        if(akt.odkad == '(' && akt.dokad == ')')
            policz(akt.a+1, akt.b-1);
        
        else if(akt.odkad == '(' && akt.dokad == '>')
            policz(akt.a+1, akt.b);
        
        else if(akt.odkad == '<' && akt.dokad == ')')
            policz(akt.a, akt.b-1);

        else// < >
            policz(akt.a, akt.b);
    }

    // cout << '\n';
    // for(int i = 0; i <= 200; i++)
    //     cout << "i = " << i << ": " << suma[i] << '\n';
    // cout << '\n';

    int najwiecej = 0;//0
    int licznik = 0;//0
    S wynik; wynik.odkad = '<'; wynik.dokad = '>'; wynik.przecinek = ',';
    for(int i = 0; i <= 200; i++) // każda liczba jest przesunięta o 100//
    {
        if(suma[i] == 1)
        {
            licznik++;
            if(licznik > najwiecej)//
            {
                najwiecej = licznik;
                wynik.b = i;//
                wynik.a = wynik.b-licznik+1;//
                // 0     1    1    1   0   1   0   0   1   1   1   1   1 
                //-100  -99 -98  -97 -96 -95 -94 -93 -92 -91 -90 -89  -88
            }
        }
        else
        {
            //cout << "konczymy i = " << i << ", na licznik = " << licznik << ", wynik(najwiecej): " << wynik.odkad << wynik.a << wynik.przecinek << ' ' << wynik.b << wynik.dokad << '\n';
            licznik = 0;
        }
    }

    wynik.a -= 100;
    wynik.b -= 100;
    cout << wynik.odkad << wynik.a << wynik.przecinek << ' ' << wynik.b << wynik.dokad << '\n';
    
    return 0;
}

 

Answer 1

(Rozumiem że treść zadania mówi że zakresy zbiorów są -100..100? Bo tego nie wspomniałeś)

W każdym razie, jeśli dobrze rozumiem treść (nie wrzuciłeś całej treści, więc mogłem kompletnie spudłować), to popełniłeś duże przeoczenie w samej definicji przedziałów: (10, 20) to nie jest to samo co <11, 19>. Jeśli zbiór wejściowy kończy się na ), to nie możesz na wyjściu udawać że to jest > (i to samo z początkiem).

Comments

No tak, to nie jest to samo. Podeślę treść aby wyjaśnić wszelkie nieścisłości.

---

Na początku filmu jest treść. Zerknij jeszcze w treść 1.3.

https://youtu.be/dtvPvm0cXws?si=KgMjatWp5qs8RvlH.

 

Ja rozumiem że to nie jest to samo bo my wyłączamy jedynie liczbę kończącą przedział gdy mamy do czynienia z ')'

---

Ja rozumiem że to nie jest to samo bo my wyłączamy jedynie liczbę kończącą przedział gdy mamy do czynienia z ')'

Kluczowe, że w zadaniu przedziały dotyczą liczb rzeczywistych, nawet jeśli na program dostajesz wyłącznie A,B jako liczby całkowite.

<0, 100> zawiera np liczby 0, 1, 50, 99, 100.

<0, 100) zawiera np liczby 0, 1, 50, 99, 99.5, 99.99999999... aż do 100, ale bez 100.

<0, 99> zawiera np liczby 0, 1, 50, 99.

Suma zakresów (0, 100), (100, 200) ma przerwę w punkcie 100.

Suma zakresów (0, 99>, <100, 200) też ma przerwę - cały zakres 99.1, 99.5, 99.999 etc.

 

---

Tak, mam to z tyłu głowy, lecz raczej nie o to chodzi w zadaniu aby zajmować się liczbami niecałkowitymi. Odpowiedź ma liczby całkowite. I ogólnie w zadaniach maturalnych to raczej INT'y.

---

Treść zadania, na samym samym początku:

przedziałem obustronnie otwartym nazywamy zbiór liczb rzeczywistych x spełniających warunek...

Tak, w zadaniu na wejściu i wyjściu są same liczby całkowite. Definicja przedziałów jest oparta na liczbach rzeczywistych, ale nikt nie powiedział że potrzebujesz je do wykonania zadania. Nie potrzebujesz liczb rzeczywistych, żeby zakodować że (0,10) i (10,20) nie są nieprzerwane ale (0,10) i <10,20) są nieprzerwane, albo że sumą (0,15> i <10,20> jest (0,20>.

EDIT: nie patrzyłem za długo, ale osoba rozwiązująca w tym filmiku na YT używa same inty, nie? ;)

---

Tak. Używa. Ale dalej nie wiem dlaczego nie mogę stworzyć sobie tablicy SUMA[] w której będę trzymał informację czy dana liczba jest w ostatecznym zbiorze czy też jej nie ma..

---

No, bo jak masz <0, 10> i <11, 20> to w obecnej implementacji wypełnisz suma[10] i suma[11] i będziesz myślał że przedział jest nieprzerwany, a ewidentnie ma przerwę.

---

A, jejku no faktycznie... a mógłbym zrobić coś podobnego ale interesowały by mnie wartości > 1 w tej tablicy suma[]? Edit: (chyba nie...)

---

Uhh... może? Mógłbyś zakodować w 2x większej tablicy czy częścią sumy jest 10, czy jest "obszar pomiędzy 10 i 11" i czy jest 11. Nie jestem pewny czy o to chodziło autorom zadania, ale możesz spróbować.

---

Okej. Dzięki za wyczerpującą odpowiedź. Wesołych Świąt!