Strefa wyzwań - I_R_W14_M23_Java Jak szybko znaleźć dane? Wyszukiwanie liniowe vs binarne

R9QE875QOLU54

Już wiesz

Jak działa metoda wyszukiwania liniowego.
Jak działa metoda iteracyjna oraz rekurencyjna algorytmu wyszukiwania binarnego.
Już wiesz jaka jest rola lidera oraz idola.

Teraz czas, aby sprawdzić wiedzę i umiejętności w praktyce.

R1Q8JOAR33HLL

Ćwiczenie 1

R1SPT49C3NOTV

Ćwiczenie 2

Ćwiczenie 3

Medianą nazywamy taki środkowy element uporządkowanego zbioru składającego się z nieparzystej liczby elementów. Jeśli liczba elementów jest parzysta, mediana jest równa średniej arytmetycznej dwóch środkowych liczb.

Zapisz za pomocą pseudokodu propozycję algorytmu obliczającego wartość mediany dla zbioru, który nie jest posortowany.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów zbioru
zbiór – zbiór n liczb całkowitych

Wynik:

mediana – mediana zbioru

R13Q5D1R39LZM

Propozycja rozwiązania:

funkcja sortuj(zbiór, n)
	dla i = 0, 1, ..., n - 1 wykonuj:
		najmniejszy ← i
		dla j = i + 1, i + 2, ..., n - 1 wykonuj:
			jeżeli zbiór[j] < zbiór[najmniejszy]:
				najmniejszy ← j
		zamień zbiór[i] z zbiór[najmniejszy]
	zwróć zbiór

funkcja znajdz_mediane(zbiór, n):
	posortowany_zbior ← sortuj(zbior)

	jeżeli n mod 2 != 0:
        mediana ← posortowany_zbior[n div 2]
    w przeciwnym wypadku:
        mediana ← (posortowany_zbior[n div 2 - 1] + posortowany_zbior[n div 2]) / 2
    
    wypisz "Mediana: " + mediana

Ważne!

W rozwiązaniu wykorzystujemy operatory div oraz mod. Operator div oznacza dzielenie całkowitoliczbowe, a operator mod – obliczanie wartości modulo (reszty z dzielenia). Sortowanie można wykonać inną metodą.

Ćwiczenie 4

Dominantą nazywamy wartość, która najczęściej występuje w zbiorze danych.

Zapisz za pomocą pseudokodu propozycję algorytmu obliczającego wartość dominanty zbioru, który jest posortowany.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów zbioru
zbiór – zbiór n liczb całkowitych

Wynik:

dominanta – dominanta zbioru

RAH4FVKMQCJJ6

funkcja znajdź_dominantę(zbiór, n):
    aktualna_wartość ← zbiór[0]
    maksymalna_wartość ← zbiór[0]
    ile_wystąpień_aktualnej ← 1
    maksymalnie_wystąpień ← 1
    
    i ← 1

    dopóki i < n:
    	wartość ← zbiór[i]
        jeżeli wartość = aktualna_wartość:
            ile_wystąpień_aktualnej ← ile_wystąpień_aktualnej + 1
    	w przeciwnym wypadku:
            aktualna_wartość ← wartość
            ile_wystąpień_aktualnej ← 1

        jeżeli ile_wystąpień_aktualnej > maksymalnie_wystąpień:
            maksymalnie_wystąpień ← ile_wystąpień_aktualnej
            maksymalna_wartość ← aktualna_wartość

    jeżeli maksymalnie_wystąpień > 1:
        wypisz "Dominanta: " + maksymalna_wartość
    w przeciwnym wypadku:
        wypisz "Brak dominanty"

Ćwiczenie 5

Zapoznaj się z algorytmem wyszukiwania liniowego przeszukującego zbiór n-elementowy zaczynającego od prawej strony (oznacza to, iż wyszukiwanie zaczyna się od elementu o indeksie o jeden mniejszym niż liczba elementów całego zbioru, a kończy na elemencie o indeksie równym 0). Uzupełnij miejsca, w których kod został skasowany i na jego miejscu postawiono symbol X.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów zbioru
zbiór – n-elementowy zbiór liczb całkowitych
szukana – liczba całkowita

Wynik:

informacja, czy i na jakiej pozycji została odnaleziona liczba szukana

funkcja wyszukiwanie_liniowe_od_prawej(zbiór, szukana, n):
    znaleziono ← fałsz
    X
    dopóki znaleziono != prawda X wykonuj:
        jeżeli X szukana
            wypisz X
            znaleziono ← prawda
            zakończ działanie algorytmu
        i ← X
    X        
    	X

R1OM474OK84DF

Kim jest idol

I_R_W14_M23_Java Jak szybko znaleźć dane? Wyszukiwanie liniowe vs binarne