Algorytmy bez tajemnic
Struktury dynamiczne
Struktury dynamiczne to zbiory danych, których rozmiar może się zmieniać w trakcie działania programu. Pozwalają one na dynamiczne dodawanie, usuwanie oraz modyfikowanie elementów. Do najczęściej używanych należą: stos, kolejka i lista.
- Stos (LIFO - Last In, First Out)
Stos to struktura danych, w której elementy są dodawane na szczyt i zdejmowane ze szczytu (ostatni dodany element wychodzi pierwszy).
Algorytm DodajNaStos(element)
Umieść element na szczycie stosu
Algorytm UsunZeStosu()
Jeśli stos nie jest pusty to:
Zwróć i usuń element ze szczytu stosu
Algorytm PodgladSzczytu()
Jeśli stos nie jest pusty to:
Zwróć element ze szczytu stosu
Algorytm CzyStosPusty()
Zwróć PRAWDA, jeśli stos jest pusty, w przeciwnym razie FAŁSZ
- Kolejka (FIFO - First In, First Out)
Kolejka to struktura danych, w której elementy są dodawane na końcu i usuwane z początku, co sprawia, że pierwszy dodany element jest pierwszym usuniętym.
Algorytm DodajDoKolejki(element)
Dodaj element na koniec kolejki
Algorytm UsunZKolejki()
Jeśli kolejka nie jest pusta to:
Zwróć i usuń element z początku kolejki
Algorytm PodgladPoczatku()
Jeśli kolejka nie jest pusta to:
Zwróć element z początku kolejki
Algorytm CzyKolejkaPusta()
Zwróć PRAWDA, jeśli kolejka jest pusta, w przeciwnym razie FAŁSZ
Sortowanie: metoda dziel i zwyciężaj
Metoda dziel i zwyciężaj to technika algorytmiczna, w której problem dzielony jest na mniejsze podproblemy, rozwiązywane rekurencyjnie, a następnie łączone w jedno rozwiązanie. Przykłady to sortowanie przez scalanie i szybkie sortowanie.
- Sortowanie przez scalanie (Merge Sort)
Sortowanie przez scalanie dzieli listę na pół, sortuje każdą część osobno, a następnie scala je w jedną posortowaną listę.
Algorytm SortowaniePrzezScalanie(T)
Jeśli długość T > 1 to:
Środek = długość(T) // 2
Lewa = pierwsza połowa T
Prawa = druga połowa T
SortowaniePrzezScalanie(Lewa)
SortowaniePrzezScalanie(Prawa)
Scal(Lewa, Prawa, T)
Algorytm Scal(Lewa, Prawa, T)
i = j = k = 0
Dopóki i < długość(Lewa) oraz j < długość(Prawa) wykonuj:
Jeśli Lewa[i] <= Prawa[j] to:
T[k] = Lewa[i]
i = i + 1
Inaczej:
T[k] = Prawa[j]
j = j + 1
k = k + 1
Dopóki i < długość(Lewa):
T[k] = Lewa[i]
i = i + 1
k = k + 1
Dopóki j < długość(Prawa):
T[k] = Prawa[j]
j = j + 1
k = k + 1
- Szybkie sortowanie (Quick Sort)
Szybkie sortowanie wybiera element pivot, dzieli listę na elementy mniejsze i większe od pivot, a następnie rekurencyjnie sortuje obie części.
Algorytm SzybkieSortowanie(T, początek, koniec)
Jeśli początek < koniec to:
IndeksPivota = Podziel(T, początek, koniec)
SzybkieSortowanie(T, początek, IndeksPivota - 1)
SzybkieSortowanie(T, IndeksPivota + 1, koniec)
Algorytm Podziel(T, początek, koniec)
Pivot = T[koniec]
i = początek - 1
Dla j = początek do koniec - 1 wykonuj:
Jeśli T[j] <= Pivot to:
i = i + 1
Zamień(T[i], T[j])
Zamień(T[i + 1], T[koniec])
Zwróć i + 1
Wyszukiwanie elementów
Wyszukiwanie elementów to proces znajdowania konkretnej wartości w zbiorze danych. Możemy je realizować na różne sposoby, np. poprzez przeszukiwanie liniowe lub przez połowienie, które są dostosowane do różnych typów danych i zbiorów.
- Wyszukiwanie liniowe (Linear Search)
Liniowe przeszukiwanie polega na przeglądaniu każdego elementu listy po kolei, aż znajdziemy poszukiwany element.
Algorytm WyszukiwanieLiniowe(T, szukany)
Dla i = 0 do długość(T) - 1 wykonuj:
Jeśli T[i] = szukany to:
Zwróć i
Zwróć -1 (gdy element nie został znaleziony)
- Wyszukiwanie przez połowienie (Binary Search)
Wyszukiwanie przez połowienie wymaga posortowanej listy. Polega na dzieleniu listy na pół i porównywaniu wartości środkowej z poszukiwaną, aż znajdziemy odpowiedni element.
Algorytm WyszukiwaniePrzezPolowienie(T, szukany, początek, koniec)
Dopóki początek <= koniec wykonuj:
Środek = (początek + koniec) // 2
Jeśli T[Środek] = szukany to:
Zwróć Środek
Jeśli T[Środek] < szukany to:
początek = Środek + 1
Inaczej:
koniec = Środek - 1
Zwróć -1 (gdy element nie został znaleziony)
- Sortowanie przez wstawianie (Insertion Sort)
Sortowanie przez wstawianie to algorytm, w którym każdy element jest wstawiany w odpowiednie miejsce w posortowanej części listy, aż cała lista zostanie uporządkowana.
Algorytm SortowaniePrzezWstawianie(T)
Dla i = 1 do długość(T) - 1 wykonuj:
klucz = T[i]
j = i - 1
Dopóki j >= 0 i T[j] > klucz wykonuj:
T[j + 1] = T[j]
j = j - 1
T[j + 1] = klucz
Zadanka
Zadanie 1: Modyfikacja listy liczb
Algorytm ModyfikujListe(T)
Dla i = 0 do długość(T) - 1 wykonuj:
Jeśli T[i] % 2 = 0 to:
T[i] = T[i] + 1
Inaczej:
T[i] = T[i] - 1
Zwróć T
- Co będzie wynikiem działania algorytmu dla listy: T = [2, 5, 8, 7]?
- Wyjaśnij, jakie zmiany wprowadza ten algorytm w liście.
Zadanie 2.
Funkcja D(T, n)
Dla i = 0 do n - 1 wykonuj:
Dla j = i + 1 do n wykonuj:
jeśli T[i] > T[j] to:
Zamień T[i] i T[j]
Zwróć T
- Co zwróci funkcja D dla listy T = [4, 9, 2, 6, 5] i n = 5?
Zadanie 3.
Funkcja F(T, n)
wynik = 0
Dla i = 1 do n - 1 wykonuj:
jeśli T[i] < T[i - 1] to:
wynik = wynik + (T[i - 1] - T[i])
Zwróć wynik
- Co zwróci funkcja F, jeśli T = [5, 3, 7, 2, 8, 1], a n = 6?
- Opisz, co robi funkcja.
Zadanie 4.
Funkcja L(T, n)
wynik = 0
Dla i = 0 do n - 1 wykonuj:
Dla j = 0 do n - 1 wykonuj:
jeśli i != j to:
wynik = wynik + abs(T[i] - T[j])
Zwróć wynik
- Co zwróci funkcja L dla listy T = [1, 2, 3], n = 3?
- Zmodyfikuj funkcję tak, aby ignorowała porównania dla par, gdzie T[i] i T[j] są równe.