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ą.

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.

5
27
23
20
4
26
24
12
9
1

5 27
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

Rozwiązanie

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:

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

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.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // 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.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 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.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 1
	w przeciwnym wypadku:
		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).

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 1
	w przeciwnym wypadku:
		obecnaDlugosc ← 1
	jeżeli obecnaDlugosc > maxDlugosc:
		maxDlugosc ← obecnaDlugosc
        poczatkiPodciagow ← []
		dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 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.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 1
	w przeciwnym wypadku:
		obecnaDlugosc ← 1
	jeżeli obecnaDlugosc > maxDlugosc:
		maxDlugosc ← obecnaDlugosc
        poczatkiPodciagow ← []
		dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1
	jeżeli obecnaDlugosc = maxDlugosc:
    	dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 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.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 1
	w przeciwnym wypadku:
		obecnaDlugosc ← 1
	jeżeli obecnaDlugosc > maxDlugosc:
		maxDlugosc ← obecnaDlugosc
        poczatkiPodciagow ← []
		dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1
	jeżeli obecnaDlugosc = maxDlugosc:
    	dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1

dla poczatekPodciagu w poczatkiPodciagow wykonuj:
    dla j = poczatekPodciagu, poczatekPodciagu + 1, ..., poczatekPodciagu + maxDlugosc - 1 wykonuj:
        zapisz pomiary[j] do pliku "powietrze.txt"
    zapisz nową linię do pliku "powietrze.txt"

Zamykamy pliki.

pomiary[0..99] ← wczytaj dane z pliku "pomiary.txt"

maxDlugosc ← 1
obecnaDlugosc ← 1
poczatkiPodciagow[] // tablica liczb naturalnych

dla i = 1, 2, ..., 99 wykonuj:
	jeżeli pomiary[i] >= pomiary[i - 1]:
		obecnaDlugosc ← obecnaDlugosc + 1
	w przeciwnym wypadku:
		obecnaDlugosc ← 1
	jeżeli obecnaDlugosc > maxDlugosc:
		maxDlugosc ← obecnaDlugosc
        poczatkiPodciagow ← []
		dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1
	jeżeli obecnaDlugosc = maxDlugosc:
    	dodaj do tablicy poczatkiPodciagow wartość i - maxDlugosc + 1

dla poczatekPodciagu w poczatkiPodciagow wykonuj:
    dla j = poczatekPodciagu, poczatekPodciagu + 1, ..., poczatekPodciagu + maxDlugosc - 1 wykonuj:
        zapisz pomiary[j] do pliku "powietrze.txt"
    zapisz nową linię do pliku "powietrze.txt"
    
zamknij plik "pomiary.txt"
zamknij plik "powietrze.txt"

Odpowiedź do zadania

powietrze.txt

Słownik