Wprowadzenie do algorytmów
Algorytm to sekwencja kroków opisująca sposób rozwiązania problemu. Każdy program komputerowy, który kończy się wynikiem, jest w zasadzie oparty na algorytmie. Algorytmy nie ograniczają się jednak wyłącznie do stosowania w programach komputerowych, mogą być również wykorzystywane do rozwiązywania problemów matematycznych i wielu codziennych spraw. Na podstawie tego, jak działają, możemy podzielić algorytmy na wiele typów. Rzućmy okiem na niektóre z najważniejszych.
Rodzaje algorytmów
Istnieje wiele rodzajów algorytmów, ale podstawowe typy algorytmów to:
1) Algorytm rekurencyjny
Jest to jeden z najciekawszych algorytmów, ponieważ nazywa się on mniejszą wartością jako dane wejściowe, które otrzymuje po rozwiązaniu dla danych wejściowych prądu. Mówiąc prościej, jest to algorytm, który wywołuje się wielokrotnie, dopóki problem nie zostanie rozwiązany.
Problemy takie jak Wieża Hanoi lub DFS wykresu można łatwo rozwiązać za pomocą tych algorytmów.
Na przykład, oto kod, który znajduje silnię za pomocą algorytmu rekurencji:
Fakt (y)
Jeśli y wynosi 0
zwrot 1
return (y * Fakt (y-1)) / * w tym miejscu następuje rekurencja * /
2) Algorytm Dziel i rządź
To kolejny skuteczny sposób rozwiązania wielu problemów. W algorytmach Dziel i rządź podziel algorytm na dwie części, pierwsze części dzielą problem na mniejsze podproblemy tego samego typu. Następnie, w drugiej części, te mniejsze problemy zostały rozwiązane, a następnie dodane razem (połączone), aby uzyskać ostateczne rozwiązanie problemu.
Sortowanie i szybkie sortowanie można wykonywać za pomocą algorytmów dzielenia i zdobywania. Oto pseudokod algorytmu sortowania scalającego, który daje przykład:
MergeSorting (ar (), l, r)
Jeśli r> l
- Znajdź punkt środkowy, aby podzielić daną tablicę na dwie połowy:
środkowy m = (l + r) / 2
- Scalanie połączeńSortowanie w pierwszej połowie:
Scalanie połączeń Sortowanie (ar, l, m)
- Scalanie połączeńSortowanie w drugiej połowie:
Scalanie połączeń Sortowanie (ar, m + 1, r)
- Scal połówki posortowane w kroku 2 i 3:
Scalanie połączeń (ar, l, m, r)
3) Algorytm programowania dynamicznego
Algorytmy te działają poprzez zapamiętywanie wyników z poprzedniego przebiegu i wykorzystywanie ich do znajdowania nowych wyników. Innymi słowy, algorytm programowania dynamicznego rozwiązuje złożone problemy, dzieląc go na wiele prostych podproblemów, a następnie rozwiązuje każdy z nich raz, a następnie przechowuje je do wykorzystania w przyszłości.
Sekwencja Fibonacciego jest dobrym przykładem algorytmów programowania dynamicznego, możesz zobaczyć, jak działa w pseudokodzie:
Fibonacciego (N) = 0 (dla n = 0)
= 0 (dla n = 1)
= Fibonacciego (N-1) + Finacchi (N-2) (dla n> 1)
4) Chciwy algorytm
Algorytmy te są wykorzystywane do rozwiązywania problemów związanych z optymalizacją. W tym algorytmie znajdujemy optymalne lokalnie rozwiązanie (bez względu na konsekwencje w przyszłości) i mamy nadzieję znaleźć optymalne rozwiązanie na poziomie globalnym.
Ta metoda nie gwarantuje, że będziemy w stanie znaleźć optymalne rozwiązanie.
Algorytm składa się z 5 elementów:
- Pierwszy to zestaw kandydatów, z którego staramy się znaleźć rozwiązanie.
- Funkcja wyboru, która pomaga wybrać najlepszego możliwego kandydata.
- Funkcja wykonalności, która pomaga zdecydować, czy kandydat może zostać wykorzystany do znalezienia rozwiązania.
- Funkcja celu, która przypisuje wartość możliwemu rozwiązaniu lub rozwiązaniu częściowemu
- Funkcja rozwiązania, która informuje, kiedy znaleźliśmy rozwiązanie problemu.
Kodowanie Huffmana i algorytm Dijkstry to dwa główne przykłady, w których stosuje się algorytm Chciwy.
W kodowaniu Huffmana algorytm przechodzi przez komunikat i w zależności od częstotliwości znaków w tym komunikacie do każdego znaku przypisuje kodowanie o zmiennej długości. Aby wykonać kodowanie Huffmana, najpierw musimy zbudować drzewo Huffmana ze znaków wejściowych, a następnie przejść przez drzewo, aby przypisać kody do znaków.
5) Algorytm siły brutalnej
Jest to jeden z najprostszych algorytmów w koncepcji. Algorytm brutalnej siły ślepo iteruje wszystkie możliwe rozwiązania, aby wyszukać jedno lub więcej rozwiązań, które mogą rozwiązać funkcję. Pomyśl o brutalnej sile, jak o użyciu wszystkich możliwych kombinacji liczb, aby otworzyć sejf.
Oto przykład wyszukiwania sekwencyjnego wykonanego przy użyciu brutalnej siły:
Algorytm S_Search (A (0..n), X)
A (n) ← X
i ← 0
Podczas gdy A (i) ≠ X tak
i ← i + 1
jeśli i <n zwrócę i
w przeciwnym razie zwróci -1
6) Algorytm cofania
Cofanie jest techniką znajdowania rozwiązania problemu w podejściu przyrostowym. Rozwiązuje problemy rekurencyjnie i próbuje znaleźć rozwiązanie problemu, rozwiązując jeden kawałek problemu na raz. Jeśli jedno z rozwiązań zawiedzie, usuwamy je i cofamy się, aby znaleźć inne rozwiązanie.
Innymi słowy, algorytm cofania rozwiązuje podproblem, a jeśli nie rozwiąże problemu, cofa ostatni krok i zaczyna od nowa, aby znaleźć rozwiązanie problemu.
Problem N Królowych jest dobrym przykładem, aby zobaczyć działanie algorytmu Cofania. Problem N Królowej mówi, że na szachownicy znajduje się N pionów Królowych i musimy je tak ułożyć, aby żadna królowa nie mogła zaatakować żadnej innej królowej na planszy po zorganizowaniu.
Teraz spójrzmy na algorytm SolveNQ i funkcje Sprawdź poprawne, aby rozwiązać problem:
CheckValid (szachownica, rząd, kolumna)
Początek
Jeśli po lewej stronie bieżącej kolumny znajduje się Królowa, zwróć wartość false
Jeśli królowa znajduje się w lewym górnym rogu, zwróć false
Jeśli królowa ma lewą dolną przekątną, zwróć wartość false
Zwróć prawdę
Koniec
SolveNQ (tablica, kolumna)
Początek
Jeśli wszystkie kolumny są pełne, zwróć wartość true
Dla każdego rzędu obecnego na szachownicy
Robić
Jeśli CheckValid (tablica, x, kolumna), to
Ustaw królową w komórce (x, kolumna) na planszy
Jeśli SolveNQ (tablica, kolumna + 1) = True, to zwróć true.
W przeciwnym razie usuń królową z komórki (x, kolumna) z planszy
Gotowy
Zwróć false
Koniec
Wniosek - rodzaje algorytmów
Algorytmy stoją za większością imponujących rzeczy, które mogą zrobić komputery, i są one podstawą większości zadań komputerowych. Lepsza znajomość algorytmów nie tylko pomoże ci odnieść sukces jako programista, ale także staniesz się bardziej wydajny.
Polecane artykuły
To był przewodnik po typach algorytmów. Tutaj omawiamy 6 najważniejszych typów algorytmów wraz z ich funkcjami. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Wprowadzenie do algorytmu
- Algorytm w programowaniu
- Pytania do wywiadu algorytmicznego
- Silnia w Pythonie | Techniki
- Algorytmy szybkiego sortowania w Javie
- Top 6 algorytm sortowania w JavaScript