Zadanie 1. Listonosz Patryk

Patryk jest listonoszem. Codziennie ma do dostarczenia bardzo dużo listów. Na każdym liście jest napisany pięciocyfrowy kod pocztowy – dzięki niemu listonosz wie, dokąd ma jechać, aby trafić do adresata.

Patryk pewnego dnia otrzymał do dostarczenia 500 listów. Niestety, nie były one posortowane.

W pliku kody.txt znajduje się 500 pięciocyfrowych liczb naturalnych - są to kody pocztowe listów, które Patryk ma do dostarczenia.

Patryk jest również entuzjastą statystyki. Posortował on listy według kodów pocztowych niemalejąco, a teraz chce się dowiedzieć, ile wynosi średnia arytmetyczna z liczb znajdujących się na co trzeciej pozycji (czyli kodów, które znajdują się na co trzecim liście).

Napisz program, który dla danych z pliku kody.txt obliczy, ile wynosi średnia arytmetyczna z liczb oznaczających kody pocztowe, które po uporządkowaniu ich niemalejąco znajdowałyby się na pozycjach będących wielokrotnościami liczby 3. Kody numerujemy od 1. Wyniki zapisz do pliku wynik.txt.

Wynik zaokrąglij do liczby całkowitej.

Przykładowo, jeżeli listów byłoby 8, to interesowałyby nas listy, które po posortowaniu niemalejąco znajdują się na miejscu trzecim i szóstym. Listy numerowane są od 1.

58940 
20992 
66027 
65212 
13366 
60493 
21073 
10494 
74230 
55970

Do oceny oddajesz:

• plik wynik.txt, zawierający odpowiedź do zadania (jedna liczba oznaczająca średnią z co trzeciego kodu pocztowego, z pliku kody.txt, gdyby liczby były uporządkowane niemalejąco),

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

Rozwiązanie

Ponieważ każdy kod pocztowy jest liczbą pięciocyfrową, a my chcemy wiedzieć, jak wyglądałaby lista posortowana niemalejąco, użyjemy sortowania pozycyjnego. Po posortowaniu liczb obliczymy średnią arytmetyczną z tych, które znajdują się na co trzeciej pozycji. Sortowanie pozycyjne wykorzystuje inne stabilne algorytmy sortowaniasortowanie stabilnestabilne algorytmy sortowania, w rozwiązaniu tego zadania, użyjemy stabilnego algorytmu sortowania przez zliczaniePNx8quWZlsortowania przez zliczanie.

Załóżmy, że do posortowania mamy tablicę tablica – chcemy ją posortować według pozycji r. Przykładowo, jeżeli chcemy ją posortować według pozycji jedności, r wynosi 1, jeżeli natomiast według pozycji dziesiątek, r wynosi 10 - i tak dalej. Algorytm sortowania przez zliczanie wygląda wtedy następująco:

sortowaniePrzezZliczanie(tablica,r)
    n ← długość(tablica)
    liczniki[0..9] ← {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    dla i = 0, 1, ..., n-1 wykonuj:
        indeks ← (tablica[i] div r) mod 10
        liczniki[indeks] ← liczniki[indeks] + 1

    dla i = 1, 2, ..., 9 wykonuj:
        liczniki[i] ← liczniki[i] + liczniki[i-1]

    dla i = n-1, n-2, ..., 0 wykonuj:
        indeks ← (tablica[i] div r) mod 10
        liczniki[indeks] ← liczniki[indeks] - 1
        posortowanaTablica[liczniki[indeks]] ← tablica[i]

    zwróć posortowanaTablica

Zapisany za pomocą pseudokodu algorytm sortujący niemalejąco liczby, a następnie wyliczający średnią arytmetyczną z elementów znajdujących się na co trzeciej pozycji wygląda następująco:

tablica ← wczytaj dane z pliku "kody.txt"
r ← 1
liczbaCyfr ← 5
średnia ← 0
ile ← 0

dla i = 4, 3, ..., 0 wykonuj:
	tablica ← sortowaniePrzezZliczanie(tablica, r)
    r ← r * 10
    
dla i = 0, 1, ..., 499 wykonuj:
	jeżeli i mod 3 = 2:
    	średnia ← średnia + tablica[i]
        ile ← ile + 1
        
średnia ← średnia / ile
zaokrąglij średnia do liczby całkowitej
wpisz średnia do pliku "wynik.txt"

Do sortowania pozycyjnego możesz użyć dowolnego stabilnego algorytmu sortowania.

Odpowiedź do zadania

Odpowiedź do zadania dla danych z pliku kody.txt: 55 469

Słownik