Ma objętość 5 stron. Notatka przedstawia sposób wyznaczania mediany z punktu widzenia informatyka, czyli wyjaśnienie co to jest mediana z punktu widzenia informatyka, rozpisanie problemu na operacje wyjścia i wejścia oraz na końcu cały napisany program. Polecam dla tych którzy chcą zobaczyć istotę programowania, chcą nauczyć się jak rozbijać problem na części.
ZADANIE 1: WYZNACZANIE MEDIANY
Problem:
Dla zbioru Z znaleźć element, od którego w tym zbiorze jest tyle samo elementów większych lub równych co mniejszych lub równych. Element zbioru o powyższej własności nosi nazwę mediany. Jeśli zbiór Z jest posortowany rosnąco, to:
Przy nieparzystej liczbie elementów n > 1 mediana jest elementem środkowym Z[n/2] Na przykład dla zbioru Z = {2,4,5,9,11} medianą jest element 5 - poprzedzają go dwa elementy 2 i 4 oraz wyprzedzają dwa elementy 9 i 11.
Przy parzystej liczbie elementów n > 1 mediana jest średnią arytmetyczną dwóch środkowych elementów Z[n/2-1] i Z[n/2].Na przykład dla zbioru Z = {2,5,6,7,9,12} mediana jest równa (6 + 7) / 2 = 6,5. Od tej wartości jest dokładnie tyle samo elementów mniejszych (2,5,6) co większych (7,9,12).
ROZWIĄZANIE:
Posortować zbiór rosnąco. Zwrócić element na pozycji n/2. Do znalezienia mediany wykorzystam Sortowanie Szybkie.
Algorytm ten sortuje w czasie liniowo logarytmicznym - O(n log n). Zaletą tego sposobu jest to, iż wiele współczesnych języków programowania posiada w swoich bibliotekach funkcję sortującą qsort(), która wykorzystuje ten właśnie algorytm. Wadą z kolei jest to, iż do otrzymania wartości jednego elementu musimy sortować cały zbiór danych.
W podanym poniżej algorytmie sortowania szybkiego wykorzystujemy funkcję Dziel_na_partycję(Z,ip,ik). Funkcja ta dzieli partycję zbioru Z określoną dwoma indeksami ip oraz ik na dwie mniejsze partycje. Zwraca indeks podziałowy iv. Pierwsza partycja zawiera elementy od ip do iv - 1, a druga od iv do ik. Elementy w partycji pierwszej są niewiększe od elementów w partycji drugiej.
ALGORYTM SZYBKIEGO SORTOWANIA I ZNAJDOWANIA MEDIANY:
Wejście:
n - liczba elementów w zbiorze Z
Z[] - tablica (n+1) elementowa odwzorowująca zbiór Z, w który sortujemy. Na pozycji Z[n] należy umieścić wartownika o wartości większej od każdego elementu zbioru.
Wyjście:
Mediana zbioru Z.
Zmienne pomocnicze:
iv - zawiera pozycję elementu zwrotnego, Iv należy do C
v - wartość elementu zwrotnego
i, j - indeksy w tablicy Z[]; i, j należy do C
ip - indeks początku partycji, ip należy do C
ik - indeks końca partycji, ik należy do C
PROGRAM
Program wypełnia tablicę 99 elementową Z[ ] liczbami pseudolosowymi z zakresu od 0 do 999, wyświetla ją, sortuje szybko, wyświetla posortowaną i zwraca medianę. Na wydruku zbioru posortowanego mediana znajduje się w środku trzeciego wiersza.
// Wyszukiwanie mediany
program prg;
const N = 99;
// Funkcja dzieli podany zbiór Z na dwie partycje:
// ZL - elementy mniejsze od elementu zwrotnego
... zobacz całą notatkę
Komentarze użytkowników (0)