Prezentacja multimedialna

Polecenie 1

Zapisz w wybranej przez siebie notacji (za pomocą pseudokodu, listy kroków lub w wybranym języku programowania) algorytm, który dla cząstek o składowych prędkości zawartych w tablicach VX[] oraz VY[] wyliczy medianę prędkości.

Dla uproszczenia zapisu możesz skorzystać z funkcji Prędkość(), wprowadzonej wcześniej.

Specyfikacja problemu:

Dane:

n – zmienna przechowująca liczbę cząsteczek; liczba naturalna dodatnia
VX[1..n] – tablica przechowująca składowe wektorowe względem osi x; tablica liczb całkowitych
VY[1..n] – tablica przechowująca składowe wektorowe względem osi y; tablica liczb całkowitych

Wynik:

mediana prędkości analizowanych cząsteczek

RwSHGTFVIxz1q

Polecenie 2

Porównaj swoje rozwiązanie z przedstawionym w prezentacji.

RbMB1n2aAAlth1

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Dla zainteresowanych

Pseudokod funkcji QuickSelect – złożoność obliczeniowa jest wprost proporcjonalna do długości tablicy.

Linia 1. funkcja zamien otwórz nawias okrągły tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek i przecinek j zamknij nawias okrągły dwukropek. Linia 2. tym ← tab otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 3. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy ← tab otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 4. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy ← tym. Linia 6. funkcja podzial otwórz nawias okrągły tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek l przecinek p zamknij nawias okrągły dwukropek. Linia 7. kratka funkcja dzieli tablicę tab otwórz nawias kwadratowy l kropka kropka p zamknij nawias kwadratowy na elementy mniejsze. Linia 8. kratka bądź równe i większe od elementu podziału przecinek. Linia 9. kratka którym jest ostatni element tablicy. Linia 10. element podkreślnik podzialu ← tab otwórz nawias kwadratowy p zamknij nawias kwadratowy. Linia 12. mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks ← l. Linia 13. dla i ← l przecinek l plus 1 przecinek kropka kropka kropka przecinek p minus 1 wykonuj dwukropek. Linia 14. jeżeli tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny element podkreślnik podzialu dwukropek. Linia 15. zamien otwórz nawias okrągły tab przecinek mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks przecinek i zamknij nawias okrągły. Linia 16. mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks ← mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks plus 1. Linia 18. kratka wstaw element podziału na właściwe miejsce. Linia 19. kratka teraz mamy pewność że jest on na dobrym miejscu w tablicy. Linia 20. kratka tzn kropka w posortowanej tablicy byłby na tym samym indeksie co teraz. Linia 21. zamien otwórz nawias okrągły tab przecinek mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks przecinek p zamknij nawias okrągły. Linia 22. zwróć mniejsze podkreślnik lub podkreślnik rowne podkreślnik indeks. Linia 24. funkcja QuickSelect otwórz nawias okrągły tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek szukany podkreślnik indeks zamknij nawias okrągły dwukropek. Linia 25. l ← 1. Linia 26. p ← długosc otwórz nawias okrągły tab zamknij nawias okrągły. Linia 28. wykonuj dwukropek. Linia 29. podzial podkreślnik indeks znak równości podzial otwórz nawias okrągły tab przecinek l przecinek p zamknij nawias okrągły. Linia 30. jeżeli podzial podkreślnik indeks otwórz nawias ostrokątny szukany podkreślnik indeks dwukropek. Linia 31. l ← podzial podkreślnik indeks plus 1. Linia 32. w przeciwnym razie dwukropek. Linia 33. jeżeli podzial podkreślnik indeks zamknij nawias ostrokątny szukany podkreślnik indeks dwukropek. Linia 34. p ← podzial podkreślnik indeks minus 1. Linia 35. dopóki podzial podkreślnik indeks ≠ szukany podkreślnik indeks. Linia 37. zwróć tab otwórz nawias kwadratowy szukany podkreślnik indeks zamknij nawias kwadratowy.

funkcja zamien(tab[], i, j):
	tym ← tab[i]
    tab[i] ← tab[j]
    tab[j] ← tym
    
funkcja podzial(tab[], l, p):
	# funkcja dzieli tablicę tab[l..p] na elementy mniejsze
    # bądź równe i większe od elementu podziału,
    # którym jest ostatni element tablicy
    element_podzialu ← tab[p]
    
    mniejsze_lub_rowne_indeks ← l
    dla i ← l, l+1, ..., p-1 wykonuj:
    	jeżeli tab[i] < element_podzialu:
        	zamien(tab, mniejsze_lub_rowne_indeks, i)
            mniejsze_lub_rowne_indeks ← mniejsze_lub_rowne_indeks + 1
    
    # wstaw element podziału na właściwe miejsce
    # teraz mamy pewność że jest on na dobrym miejscu w tablicy
    # tzn. w posortowanej tablicy byłby na tym samym indeksie co teraz
    zamien(tab, mniejsze_lub_rowne_indeks, p)
    zwróć mniejsze_lub_rowne_indeks

funkcja QuickSelect(tab[], szukany_indeks):
	l ← 1
    p ← długosc(tab)
    
    wykonuj:
    	podzial_indeks = podzial(tab, l, p)
        jeżeli podzial_indeks < szukany_indeks:
        	l ← podzial_indeks + 1
        w przeciwnym razie:
        	jeżeli podzial_indeks > szukany_indeks:
            	p ← podzial_indeks - 1
    dopóki podzial_indeks ≠ szukany_indeks
    
    zwróć tab[szukany_indeks]

Polecenie 3

Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.

Przeczytaj

Sprawdź się