Zadanie 3. Najdłuższy niemalejący podciąg

Problem najdłuższego niemalejącego podciągu jest klasycznym problemem optymalizacyjnym. Oznacza to, że posiada on własność optymalnej podstrukturywłasność optymalnej podstrukturywłasność optymalnej podstruktury. Problem ten jest następujący: mamy ciąg n liczb całkowitych aIndeks dolny 1 Indeks dolny koniec1,aIndeks dolny 2 Indeks dolny koniec2,...,aIndeks dolny n Indeks dolny koniec_n , należy znaleźć najdłuższy podciąg bIndeks dolny 1 Indeks dolny koniec1,bIndeks dolny 2 Indeks dolny koniec2,...,bIndeks dolny k Indeks dolny koniec_k ciągu aIndeks dolny i Indeks dolny koniec_i, że dla każdego i>0 prawdą jest bIndeks dolny i Indeks dolny konieci≤ bIndeks dolny i+1 Indeks dolny koniec_i+1.

Przykładowo: dla ciągu [4, 6, 3, 9, 1, 0, 1, 4, 7, 2, 5, 8, 9, 3, 5] maksymalny niemalejący podciąg to [1, 1, 4, 7, 8, 9].

W pliku liczby.txt znajduje się 1000 liczb całkowitych dodatnich, zapisanych dziesiętnie, maksymalnie sześciocyfrowych. Każda liczba umieszczona jest w osobnym wierszu.

Przykładowe dane:

• 65173

• 818677

• 18065

a) Napisz program, który zwróci długość maksymalnego niemalejącego podciągu. Wykorzystaj programowanie dynamiczne.

Specyfikacja problemu:

Dane:

• n – długość wejściowego ciągu liczb; liczba naturalna

• liczby[] – tablica liczb naturalnych, wśród których należy znaleźć najdłuższy niemalejący podciąg

Wynik:

• maks_dlugosc – długość najdłuższego niemalejącego podciągu; liczba naturalna

b) Napisz program, który wypisze liczby należące do najdłuższego niemalejącego podciągu, oddzielone od siebie spacją. Jeśli najdłuższych ciągów jest wiele, to zwróć taki, który kończy się na wyrazie liczby[i], gdzie i jest najmniejsze.

Specyfikacja problemu:

Dane:

• n – długość wejściowego ciągu liczb

• liczby[] – tablica liczb naturalnych, wśród których należy znaleźć najdłuższy niemalejący podciąg

Wynik:

• najdluzszy_niemalejacy_podciag[] – tablica zawierająca najdłuższy niemalejący podciąg; tablica liczb naturalnych

Rozwiązania obu poleceń zapisz w pliku wyniki.txt, każde w osobnej linii.

Rozwiązanie

Zdefiniujmy tablicę d[] rozmiaru n. Wartość d[i] tej tablicy oznacza długość maksymalnego podciągu niemalejącego dla ciągu liczby[0,...,i] który kończy się na liczby[i]. Wyliczamy wartości w tablicy d[], zaczynając od i = 0 aż do i = n - 1. Maksymalna wartość w uzupełnionej tablicy d[] jest równa długości maksymalnego ciągu niemalejącego.

Jeśli d[0] = 1, to każdą wartość d[i] dla 1 <= i < n można wyznaczyć z równania rekurencyjnego.

d[i] = max(d[j], gdzie j=0,..,i‑1 i liczby[i] >= liczby[j]) + 1

a) Rozwiązanie przedstawionego problemu zapisanego w pseudokodzie jest następujące:

funkcja najdluzszyNiemalejacyPodciag(liczby[], n):
	d[n] ← tablica długości n, wypełniona 1
	maks_dlugosc ← 0

	dla i = 1, 2, ..., n - 1 wykonuj:
		dla j = 0, 1, ..., i - 1 wykonuj:
			jeżeli liczby[i] >= liczby[j] ORAZ d[j] + 1 > d[i]:
				d[i] ← d[j] + 1
		
		jeżeli d[i] > maks_dlugosc:
			maks_dlugosc ← d[i]

	zwróć maks_dlugosc

b) Aby przechowywać obecnie znaleziony najdłuższy podciag niemalejacy, a na końcu go zwrócić potrzebujemy dodatkowo 2 tablic oraz 1 pomocniczej zmiennej.

Tablica poprzedni_element_podciagu[] ma rozmiar n i początkowo wypełniona jest -1. Jeżeli w tablicy d[] pod indeksem i zapiszemy nowe znalezione rozwiązanie (znajdziemy dłuższy podciąg), które bierze rozwiązanie w d[j] i rozszerza je o element liczby[i], to w tablicy poprzedni_element_podciagu[] na pozycji i zapiszemy j jako poprzedni element znalezionego podciągu.

Zmienna ostatni_element_ciągu będzie pamiętać indeks, pod którym znajduje się ostatni element znalezionego najdłuższego niemalejącego podciągu. Dzięki niej będziemy mogli odtworzyć ten ciąg przy użyciu tablicy poprzedni_element_podciagu[].

Tablica najdluzszy_niemalejacy_podciag[] długości maks_dlugosc posłuży nam do zapisania wynikowego podciągu w przystępnej formie i zwrócenia go.

Zapisany za pomocą pseudokodu algorytm wyznaczający maksymalny podciąg niemalejący wygląda następująco:

funkcja najdluzszyNiemalejacyPodciag(liczby[], n):
	d[n] ← tablica długości n, wypełniona 1
	poprzedni_element_podciagu ← tablica długości n, wypełniona -1
	ostatni_element_podciagu ← -1
	maks_dlugosc ← 0

	dla i = 1, 2, ..., n - 1 wykonuj:
		dla j = 0, 1, ..., i - 1 wykonuj:
			jeżeli liczby[i] >= liczby[j] ORAZ d[j] + 1 > d[i]:
				d[i] ← d[j] + 1
				poprzedni_element_podciagu[i] ← j

		
		jeżeli d[i] > maks_dlugosc:
			maks_dlugosc ← d[i]
			ostatni_element_podciagu ← i

	najdluzszy_niemalejacy_podciag ← tablica długości maks_dlugosc, wypełniona -1, która będzie zawierała znaleziony podciąg

	dla i = maks_dlugosc - 1, maks_dlugosc - 2, ..., 0 wykonuj:
		najdluzszy_niemalejacy_podciag[i] ← liczby[ostatni_element_podciagu]
		ostatni_element_podciagu ← poprzedni_element_podciagu[ostatni_element_podciagu]

	zwróć najdluzszy_niemalejacy_podciag

Zadanie zostało opracowane na podstawie zadania 62.2. ze zbiorów zadań maturalnych CKE.

Schemat oceniania

• 2 pkt – za poprawną odpowiedź do obu podpunktów zadania

• 1 pkt – za poprawną odpowiedź do jednego z podpunktów zadania

• 0 pkt – za niepoprawną odpowiedź do obu podpunktów lub brak odpowiedzi

Odpowiedź do zadania

Prawidłowe wyniki dla danych z pliku znajdują się w załączniku:

Słownik