Zadanie 1. Najdłuższy spójny podciąg niemalejący

Karol jest naukowcem w Republice Kernelowej. W ostatnim czasie przeprowadzał badania na temat stężenia pyłów przemysłowych w powietrzu. W tym celu w stolicy kraju zbudował stację pomiarową. Po kilku miesiącach pomiarów zestawił swoje wyniki w pliku pomiary.txt.

Plik pomiary.txt składa się ze 100 wierszy. W każdym z nich zapisano jedną liczbę naturalną.

RbXy7oLZjqbjB

Przycisk do pobrania pliku TXT z treścią zadania.

Plik TXT o rozmiarze 467.00 B w języku polskim

Pewnego dnia Karol został poproszony przez urzędników o podanie najdłuższego ciągu stężeń pyłów z dni, w których zanieczyszczenie bez przerwy utrzymywało się na tym samym poziomie lub rosło. Jeśli był więcej niż jeden taki okres, wszystkie powinny być wypisane w kolejnych liniach.

Przykład 1

Przykładowe dane:

Linia 1. 5. Linia 2. 27. Linia 3. 23. Linia 4. 20. Linia 5. 4. Linia 6. 26. Linia 7. 24. Linia 8. 12. Linia 9. 9. Linia 10. 1.

Wynik:

Linia 1. 5 27. Linia 2. 4 26.

Napisz program, który znajdzie najdłuższy spójny podciąg niemalejącynajdłuższy spójny podciąg niemalejącynajdłuższy spójny podciąg niemalejący dla danych z pliku pomiary.txt, a wynik zapisze do pliku powietrze.txt.

Do oceny oddajesz:

  • plik powietrze.txt z odpowiedzią (liczby wchodzące w skład najdłuższego spójnego niemalejącego podciągu liczb całkowitych dodatnich z pliku pomiary.txt; każdy podciąg w osobnej linii; linie powinny być oddzielone pojedynczym znakiem odstępu)

  • plik(i) z komputerową realizacją zadania

Praca domowa

Przedstaw rozwiązanie zadania, pisząc program w języku C++, Java lub Python.

Rozwiązanie

Rozwiązanie zadania przedstawimy w postaci pseudokodu, ponieważ na egzaminie maturalnym można korzystać z wybranego języka programowania: C++, Java lub Python.

Rozwiązanie podzielimy na dwa etapy. W pierwszej część określamy długość najdłuższego niemalejącego podciągu oraz indeksy tablicy, między którymi się on znajduje. Następnie, znając położenie podciągu, możemy przekopiować jego elementy do tablicy wynikowej. Na początku wczytajmy dane z zadania. Tablice indeksujemy od zera, zgodnie z zasadami indeksowania przyjętymi w językach programowania dostępnych na maturze:

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów.

W celu znalezienia położenia spójnego, niemalejącego podciągu definiujemy trzy dodatkowe zmienne: maxDlugosc, obecnaDlugosc oraz pustą tablicę poczatkiPodciagow, która będzie przechowywać indeksy początkowe wszystkich najdłuższych podciągów niemalejących.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych.

Następnie przechodzimy po wszystkich elementach tablicy pomiary oprócz pierwszego. Jeśli element o wartości indeksu o jeden mniejszej od wartości indeksu analizowanego elementu jest mniejszy lub równy, inkrementujemy zmienną obecnaDlugosc.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1.

Jeżeli element o wartości indeksu o jeden mniejszej od wartości indeksu analizowanego elementu jest większy, oznacza to koniec niemalejącego spójnego podciągu i rozpoczęcie zliczania na nowo — ustawiamy wartość zmiennej obecnaDlugosc na 1.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. obecnaDlugosc ← 1.

Jeśli wartość zmiennej obecnaDlugosc jest większa od maxDlugosc, aktualizujemy wartość maxDlugosc oraz czyścimy zawartość tablicy poczatkiPodciagow poprzez przypisanie jej pustej tablicy, a następnie dodajemy do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1 jako początek najdłuższego niemalejącego podciągu (jesteśmy w stanie wyliczyć początek podciągu, znając obecny indeks tablicy oraz wartość maxDlugosc).

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. obecnaDlugosc ← 1. Linia 12. jeżeli obecnaDlugosc zamknij nawias ostrokątny maxDlugosc dwukropek. Linia 13. maxDlugosc ← obecnaDlugosc. Linia 14. poczatkiPodciagow ← otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1.

Jeśli długość obecnego podciągu niemalejącego zapisana w zmiennej obecnaDlugosc jest równa długości dotychczasowego najdłuższego podciągu zapisanego w zmiennej maxDlugosc, dodajemy wartość i - maxDlugosc + 1 do tablicy poczatkiPodciagow.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. obecnaDlugosc ← 1. Linia 12. jeżeli obecnaDlugosc zamknij nawias ostrokątny maxDlugosc dwukropek. Linia 13. maxDlugosc ← obecnaDlugosc. Linia 14. poczatkiPodciagow ← otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1. Linia 16. jeżeli obecnaDlugosc znak równości maxDlugosc dwukropek. Linia 17. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1.

W kolejnym kroku w pętli dla pobieramy początki podciągów z tablicy poczatkiPodciagow i wypisujemy elementy tablicy pomiary od indeksu poczatekPodciagu do poczatekPodciagu + maxDlugosc - 1.

Następnie zapisujemy wartość elementu tablicy pomiary[j] do pliku powietrze.txt. W dalszej kolejności dodajemy nową linię do pliku, aby oddzielić od siebie podciągi.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. obecnaDlugosc ← 1. Linia 12. jeżeli obecnaDlugosc zamknij nawias ostrokątny maxDlugosc dwukropek. Linia 13. maxDlugosc ← obecnaDlugosc. Linia 14. poczatkiPodciagow ← otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1. Linia 16. jeżeli obecnaDlugosc znak równości maxDlugosc dwukropek. Linia 17. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1. Linia 19. dla poczatekPodciagu w poczatkiPodciagow wykonuj dwukropek. Linia 20. dla j znak równości poczatekPodciagu przecinek poczatekPodciagu plus 1 przecinek kropka kropka kropka przecinek poczatekPodciagu plus maxDlugosc minus 1 wykonuj dwukropek. Linia 21. zapisz pomiary otwórz nawias kwadratowy j zamknij nawias kwadratowy do pliku cudzysłów powietrze kropka txt cudzysłów. Linia 22. zapisz nową linię do pliku cudzysłów powietrze kropka txt cudzysłów.

Zamykamy pliki.

Linia 1. pomiary otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów pomiary kropka txt cudzysłów. Linia 3. maxDlugosc ← 1. Linia 4. obecnaDlugosc ← 1. Linia 5. poczatkiPodciagow otwórz nawias kwadratowy zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica liczb naturalnych. Linia 7. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 8. jeżeli pomiary otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości pomiary otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 9. obecnaDlugosc ← obecnaDlugosc plus 1. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. obecnaDlugosc ← 1. Linia 12. jeżeli obecnaDlugosc zamknij nawias ostrokątny maxDlugosc dwukropek. Linia 13. maxDlugosc ← obecnaDlugosc. Linia 14. poczatkiPodciagow ← otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1. Linia 16. jeżeli obecnaDlugosc znak równości maxDlugosc dwukropek. Linia 17. dodaj do tablicy poczatkiPodciagow wartość i minus maxDlugosc plus 1. Linia 19. dla poczatekPodciagu w poczatkiPodciagow wykonuj dwukropek. Linia 20. dla j znak równości poczatekPodciagu przecinek poczatekPodciagu plus 1 przecinek kropka kropka kropka przecinek poczatekPodciagu plus maxDlugosc minus 1 wykonuj dwukropek. Linia 21. zapisz pomiary otwórz nawias kwadratowy j zamknij nawias kwadratowy do pliku cudzysłów powietrze kropka txt cudzysłów. Linia 22. zapisz nową linię do pliku cudzysłów powietrze kropka txt cudzysłów. Linia 24. zamknij plik cudzysłów pomiary kropka txt cudzysłów. Linia 25. zamknij plik cudzysłów powietrze kropka txt cudzysłów.

Odpowiedź do zadania

powietrze.txt

Rl7UJ9bVBulVB

Przycisk do pobrania pliku TXT z wynikiem do zadania.

Plik TXT o rozmiarze 56.00 B w języku polskim

Słownik

najdłuższy spójny podciąg niemalejący
najdłuższy spójny podciąg niemalejący

fragment ciągu składający się z elementów ułożonych bezpośrednio po sobie, w kolejności niemalejącej, czyli w ten sposób, że każdy kolejny element jest równy poprzedniemu bądź większy od niego