Zadanie 1. Znaczki pocztowe

Pani Rekursywna ma kolekcję $300$ znaczków. Każdy znaczek określony jest $6$-cyfrową liczbą oznaczającą rok (cztery pierwsze cyfry od lewej strony) oraz miesiąc powstania (dwie cyfry z prawej strony) znaczka.

Pani Rekursywna chce znaleźć znaczki, które zostały wydrukowane w 2013 roku, oraz uporządkować je w kolejności od najnowszego do najstarszego.

Plik znaczki.txt zawiera 300 wierszy z oznaczeniami znaczków, które posiada pani Rekursywna. Każde oznaczenie zapisane jest w osobnej linii.

Napisz program (w wybranym języku programowania), który znajdzie i uporządkuje poszukiwane kody znaczków od najnowszego do najstarszego, a następnie zapisze je w pliku znalezione.txt, każdy kod w osobnej linii.

Do oceny oddajesz:

• plik znalezione.txt zawierający odpowiedź (uporządkowane od najnowszego do najstarszego kody znaczków, każdy kod zapisany w osobnej linii)

• plik(i) z komputerową realizacją zadania (kodem programu)

Rozwiązanie

Do rozwiązania zadania potrzebna będzie tablica zawierająca znaczki wyprodukowane w 2013 roku. Następnie, w celu uporządkowania ich w kolejności od najnowszego do najstarszego, skorzystamy z dwóch algorytmów sortowania. Przyjmujemy indeksowanie tablic od $0$, tak jak jest to reprezentowane w komputerze.

Pierwszym będzie sortowanie bąbelkowe, które ma dużą czasową złożoność obliczeniową $O\left(n^2\right)$. Dokładne informacje na temat działania tego algorytmu znajdziesz w e‑materiale Sortowanie bąbelkoweDcy2OAkUuSortowanie bąbelkowe.

Drugim algorytmem, który przeanalizujemy, będzie sortowanie szybkie. Ma ono lepszą złożoność czasową: liniowo‑logarytmiczną $O(n\log \left(n\right))$. Zagadnienie to zostało omówione w e‑materiale Sortowanie szybkieDXfvQGXppSortowanie szybkie.

Przykładowe rozwiązanie

Znaczki[0..299] ← wczytaj dane z pliku "znaczki.txt"
liczbaZnaczków ← 300

Znaczki2013[0..299]
liczbaZnaczków2013 ← 0

dla i = 0, 1, ..., liczbaZnaczków - 1 wykonuj:
	jeżeli Znaczki[i] > 201300 oraz Znaczki[i] < 201400:
		Znaczki2013[liczbaZnaczków2013] ← Znaczki[i]
		liczbaZnaczków2013 ← liczbaZnaczków2013 + 1

sortowanie(Znaczki2013, liczbaZnaczków2013)

dla i = 0, 1, ..., liczbaZnaczków2013 - 1 wykonuj:
	zapisz Znaczki2013[i] do pliku "znalezione.txt"

1. Główną część kodu rozpoczynamy od wczytania danych z pliku oraz zadeklarowania długości tablicy ze znaczkami. [linie kodu 1, 2]

2. Następnie deklarujemy pustą tablicę przeznaczoną do przechowywania znaczków wydrukowanych w 2013 roku oraz zmienną, do której będziemy zapisywać liczbę tych znaczków. [linie kodu 4, 5]

3. Kolejnym krokiem jest iteracja po wszystkich elementach tablicy Znaczki w celu odnalezienia tych, które zostały wyprodukowane w 2013 roku. Kiedy natrafimy na taki znaczek, zapisujemy go do tablicy Znaczki2013 na pierwszą wolną pozycję oraz zwiększamy zmienną liczbaZnaczków2013. [linie kodu 7, 8, 9, 10]

4. W tym momencie następuje wywołanie funkcji sortującej, której implementację omówimy, uwzględniając wybrany wariant sortowania.  [linia kodu 12]

5. Ostatnim krokiem jest zapisanie posortowanych danych do pliku wynikowego. [linie kodu 14, 15]

Sortowanie bąbelkowe

sortowanieBąbelkowe(Znaczki[], długośćTablicy)
	dla i = 0, 1, 2, ... długośćTablicy - 1, wykonuj:
		zamiana ← fałsz
		dla j = 1, 2, ... długośćTablicy - i - 1, wykonuj:
			jeżeli Znaczki[j - 1] > Znaczki [j]:
				zamiana ← prawda
				zamień Znaczki[j - 1] z Znaczki[j]
		jeżeli zamiana = fałsz przerwij pętlę

1. Definiujemy funkcję sortowania bąbelkowego, która ułoży dane w tablicy w kolejności niemalejącej. [linia kodu 1]

2. Inicjujemy pętlę, która pozwoli nam przejść po każdym indeksie komórki w tablicy tyle razy, ile wynosi długość tablicy. Definiujemy zmienną zamiana, która będzie przechowywać informację, czy w danej serii porównań nastąpiła zamiana. Liczba przejść po tablicy gwarantuje, że dla najgorszego przypadku (tablica posortowana odwrotnie do ustalonego porządku) wszystkie elementy znajdą się na odpowiednich pozycjach. W drugiej pętli pomijamy pierwszy indeks, ponieważ każda komórka sprawdzana jest z poprzednią (musimy zatem uważać, żeby nie wyjść poza zakres tablicy). [linie kodu 2, 3, 4]

3. Sprawdzamy, czy następny element w tablicy nie jest większy od obecnie badanego. Jeżeli jest, zamieniamy ich kolejność oraz ustawiamy wartość zmiennej zamiana na prawdę. [linie kodu 6, 7]

4. Jeżeli w poprzedniej serii porównań nie wystąpiła zamiana, oznacza to, że elementy są już posortowane i możemy przerwać działanie pętli. [linia kodu 8]

Sortowanie szybkie

sortowanieSzybkie(Znaczki[], lewy, prawy)
	jeżeli lewy < prawy
		punktPodziału ← podział(Znaczki, lewy, prawy)
		sortowanieSzybkie(Znaczki, lewy, punktPodziału)
		sortowanieSzybkie(Znaczki, punktPodziału + 1, prawy)

1. Definiujemy funkcję sortowania szybkiego, która będzie dzielić tablicę na części, a następnie sortować je osobno. [linia kodu 1]

2. Sprawdzamy, czy tablica, na której chcemy dokonać podziału, nie jest jednoelementowa. [linia kodu 2]

3. Wywołujemy funkcję, która wyznaczy punkt podziału tablic. [linia kodu 3]

4. Inicjujemy rekurencyjnerekurencjarekurencyjne wywołanie funkcji dla utworzonych podtablic. [linie kodu 4, 5]

podział(Znaczki[], lewy, prawy)
	punktPodziału ← Znaczki[prawy]
   	i ← lewy - 1
	j ← prawy + 1
	dopóki prawda wykonuj:
		i ← i + 1
		dopóki Znaczki[i] < punktPodziału wykonuj 
			i ← i + 1
		j ← j - 1
		dopóki Znaczki[j] > punktPodziału wykonuj:
			j ← j - 1
		jeżeli i < j:
			zamień Znaczki[i] z Znaczki[j]
		w przeciwnym razie:
			zwróć j

1. Definiujemy funkcję, która wyznaczy element środkowy punktPodziału, a następnie ułoży dane według następującej zasady: punktPodziału na środku, równe lub mniejsze od punktPodziału po lewej stronie tablicy, większe od punktPodziału po prawej stronie tablicy. [linia kodu 1]

2. Wybieramy element środkowy (na przykład ostatni). Następnie w zmiennych i oraz j zapisujemy miejsca przed pierwszym oraz za ostatnim elementem tablicy, którą chcemy posortować. [linie kodu 2, 3, 4]

3. Zwiększamy indeks i, do momentu znalezienia elementu tablicy większego niż punktPodziału. Indeks j zmniejszamy, aby w końcu znaleźć element mniejszy od punktPodziału. [linie kodu od 6 do 11]

4. Po znalezieniu mniejszego elementu zmieniamy te elementy, aby uzyskać w podtablicach odpowiednie wartości. [linie kodu 12, 13]

5. Powtarzamy dwa powyższe punkty do momentu, gdy i osiągnie wartość większą lub równą j. Wtedy zwracamy j, czyli punkt podziału tablicy. [linie kodu 14, 15]

Odpowiedź do zadania

Słownik