Zadanie: Spis pingwinów

Ogród zoologiczny w Bajtowie przeprowadza spis 270 pingwinów znajdujących się na wszystkich wybiegach.

Dane w spisie dotyczące pingwinów zawierają:

• Id – identyfikator ID (unikatowy dla każdego osobnika) lub „0”, gdy brak danych,

• Płeć – „samiec” lub „samica”,

• Gatunek – nazwa gatunku w postaci ciągu znaków,

• Wiek – zapisany w miesiącach (liczba naturalna zapisana z zerami wiodącymi, o długości dokładnie trzech znaków).

Aby uporządkować dane w spisie, pracownicy zoo zapisali zebrane informacje w pliku pingwiny.txt – każdy osobnik w nowej linii, każda z czterech informacji oddzielona pojedynczym znakiem odstępu.

W spisie brakuje jednak informacji dotyczących niektórych numerów ID – luki zostały oznaczone jako „0”. Wiadomo natomiast, że ID każdego pingwina tworzone jest w następujący sposób:

1. pierwsza cyfra to cyfra oznaczająca płeć – „1” to samiec, „2” to samica,

2. druga, trzecia i czwarta cyfra to kod ASCII pierwszego znaku nazwy gatunku pingwina (np. dla wartości 97 powinno to być 097),

3. piąta, szósta i siódma cyfra to wiek pingwina w miesiącach (np. dla osobnika w wieku sześciu miesięcy cyfry wieku podane są w następujący sposób: 006).

W wybranym przez siebie języku programowania napisz program, który:

1. uzupełni brakujące dane dotyczące pingwinów,

2. posortuje informacje niemalejąco według numerów ID, a następnie zapisze do pliku gatunki.txt gatunki pingwinów, których dane w spisie znajdują się na pozycjach 1, 20 oraz 200, każdy w osobnej linii.

Do oceny oddajesz:

• plik gatunki.txt zawierający odpowiedź (gatunki pingwinów z pliku pingwiny.txt, które po posortowaniu według ID znalazły się na 1., 20. oraz 200. miejscu),

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

Rozwiązanie

Rozwiązanie zadania przedstawimy w postaci pseudokodu.

Stworzenie struktury oraz import danych

struktura Pingwin
	Id: liczba całkowita
    Płeć: tekst
    Gatunek: tekst
    Wiek: liczba całkowita
    
utwórz tablicę Pingwiny[]    

dla i = 0, 1, ..., 269 wykonuj:
	Informacje[0..3] ← wczytaj i-tą linię z pliku "pingwiny.txt"
	Pingwiny[i] ← nowy element typu Pingwin
    Pingwiny[i].Id ← Informacje[0]
    Pingwiny[i].Płeć ← Informacje[1]
    Pingwiny[i].Gatunek ← Informacje[2]
    Pingwiny[i].Wiek ← Informacje[3]

1. Tworzymy strukturę opisującą dane dotyczące pingwinów oraz określamy typy danych zawartych w niej elementów. [linie od 1 do 5]

2. Importujemy dane z każdej linii pliku oraz zapisujemy je do struktur reprezentujących pingwiny. [linie od 9 do 15]

Przykładowa implementacja struktury Pingwin (z użyciem struktury słownika wypełnionej przykładowymi danymi):

Pingwin = {
	"Id" : 1,
    "Płeć" : "samiec",
    "Gatunek" : "grubodzioby",
    "Wiek" : 102
}

Rozwiązanie zadań

funkcja zamień(x, y)
	pom ← x
    x ← y
    y ← pom

Rozpoczynamy od definicji funkcji zamień(x, y), która zamieni ze sobą wartości dwóch argumentów do niej przekazanych. [linia od 1 do 4]

Zapiszemy algorytm sortowania bąbelkowego tablicy.

funkcja sortuj(Pingwiny[])
    n ← długość(Pingwiny[])
	dla i = 0, 1, 2, ... n - 1 wykonuj:
		zamiana ← fałsz
		dla j = 1, 2, ..., n - i - 1 wykonuj:
			jeżeli Pingwiny[j - 1].Id > Pingwiny[j].Id :
				zamień(Pingwiny[j - 1], Pingwiny[j])
				zamiana ← prawda
		jeżeli zamiana = fałsz:
			przerwij pętlę

1. Definiujmy funkcję sortowania bąbelkowego. [linia 1]

2. Zapisujemy zewnętrzną pętlę przechodzącą po wszystkich pozycjach tablicy. Wewnątrz definiujemy zmienną logiczną zamiana, której wartość będzie decydować, czy zakończyć sortowanie (unikniemy pustych przebiegów pętli, jeśli tablica będzie posortowana wcześniej). [linie 2, 3, 4]

3. W pętli wewnętrznej przechodzącej po nieuporządkowanych elementach (i pingwinów od końca znajduje się już na właściwych pozycjach) porównujemy ID pingwinów. Jeżeli osobnik na wcześniejszej pozycji ma większe ID, zamieniamy go z sąsiadem po prawej i aktualizujemy wartość zmiennej zamiana. [linie 5–8]

4. W przypadku niewystąpienia jakiejkolwiek zamiany wartość zmiennej zamiana pozostanie równa fałsz, co oznacza, że tablica jest już posortowana i można przerwać zewnętrzną pętlę. [linie 9, 10]

Sortowanie możemy wykonać wyłącznie wtedy, kiedy wszystkie pingwiny będą miały nadane właściwe identyfikatory. Powinniśmy zatem sprawdzić, które ich nie mają, a następnie im je nadać. Zapiszemy zatem pętlę, która sprawdzi, które pingwiny nie mają nadanych poprawnie identyfikatorów, a następnie przypisze im je na podstawie płci, gatunku oraz wieku. Ostatnim krokiem będzie posortowanie całej struktury oraz zapisanie odpowiednich danych do pliku wynikowego.

dla i = 0, 1, ..., długość(Pingwiny[]) - 1 wykonuj:
	jeżeli Pingwiny[i].Id = 0:
    	jeżeli Pingwiny[i].Płeć = "samiec":
        	Pingwiny[i].Id ← 1
        w przeciwnym razie:
        	Pingwiny[i].Id ← 2
        
        Pingwiny[i].Id ← Pingwiny[i].Id * 1000
        Pingwiny[i].Id ← Pingwiny[i].Id + ASCII(Pingwiny[i].Gatunek[0])
        
        Pingwiny[i].Id ← Pingwiny[i].Id * 1000
        Pingwiny[i].Id ← Pingwiny[i].Id + Pingwiny[i].Wiek
        
sortuj(Pingwiny)

zapisz Pingwiny[0].Gatunek, Pingwiny[19].Gatunek, Pingwiny[199].Gatunek do pliku "gatunki.txt"

1. W celu rozwiązania zadania przechodzimy po wszystkich indeksach tablicy Pingwiny, a następnie sprawdzamy, które numery ID są błędnie zapisane (wpisane do struktury jako 0) [linie 1, 2].  Co istotne, ID można było tworzyć i uzupełniać na bieżąco, podczas wczytywania danych. W kodzie ilustrującym tworzenie struktury w linii 12 można dodać tworzenie ID, umieszczając tam linie 2–12 z powyższego kodu.

2. Gdy natrafimy na błędny numer ID, należy go stworzyć zgodnie ze wzorem opisanym w zadaniu:

• Jeżeli osobnik jest samcem, pierwszą cyfrą będzie 1. Jeśli zaś jest samicą, pierwszą cyfrą będzie 2. [linie od 3 do 6]

• Następnie mnożymy wartość zmiennej strukturalnej ID przez 1000 (dopisując na końcu trzy zera – w ten sposób nie musimy rozważać, czy kod ASCII jest trzy-, czy dwucyfrowy). Dodajemy teraz wartość kodu ASCII pierwszej litery gatunku osobnika do jego ID. [linie 8, 9]

• Tym samym sposobem ponownie dopisujemy trzy zera do wartości zmiennej ID, a następnie dodajemy wiek osobnika. [linie 11, 12]

3. Sortujemy teraz całą strukturę – w przedstawionym przykładzie użyty został algorytm sortowania bąbelkowego. [linia 14]

4. Następnie zapisujemy odpowiednio dane do pliku wynikowego (pamiętamy, że w językach programowania dostępnych na egzaminie maturalnym indeksowanie elementów tablicy zaczyna się od zera). [linia 16]

Odpowiedź do zadania

Odpowiedź dla danych z pliku pingwiny.txt:

adeli
bialobrewy
krolewski

Słownik