Úvod do algoritmů
Algoritmus je posloupnost kroků, které popisují, jak lze problém vyřešit. Každý počítačový program, který končí výsledkem, je v zásadě založen na algoritmu. Algoritmy však nejsou omezeny pouze na použití v počítačových programech, lze je také použít k řešení matematických problémů a v mnoha záležitostech každodenního života. Na základě toho, jak fungují, můžeme algoritmy rozdělit do několika typů. Pojďme se podívat na některé z těch důležitých.
Typy algoritmů
Existuje mnoho typů algoritmů, ale základní typy algoritmů jsou:
1) Rekurzivní algoritmus
Toto je jeden z nejzajímavějších algoritmů, protože se nazývá menší hodnotou jako vstupy, které získává po vyřešení aktuálních vstupů. Zjednodušeně řečeno, je to algoritmus, který se volá opakovaně, dokud se problém nevyřeší.
Problémy, jako je například Hanojská věž nebo DFS grafu, lze pomocí těchto algoritmů snadno vyřešit.
Zde je například kód, který najde faktoriál pomocí algoritmu rekurze:
Skutečnost (y)
Pokud y je 0
návrat 1
návrat (y * fakt (y-1)) / * tady dochází k rekurzi * /
2) Algoritmus dělení a dobytí
To je další účinný způsob řešení mnoha problémů. V algoritmech Rozdělit a Dobýt rozdělte algoritmus na dvě části, přičemž první část rozdělí problém po ruce na menší dílčí úlohy stejného typu. Poté jsou na druhé straně tyto menší problémy vyřešeny a poté spojeny (kombinovány), aby se vytvořilo konečné řešení problému.
Sloučení třídění a rychlé třídění lze provést pomocí algoritmů dělení a dobytí. Zde je pseudokód algoritmu slučovacího třídění, který vám dá příklad:
MergeSorting (ar (), l, r)
Pokud r> l
- Najděte středový bod a rozdělte dané pole na dvě poloviny:
střední m = (l + r) / 2
- Volání slučování pro první polovinu:
Volání hromadné korespondence (ar, l, m)
- Volání slučování pro druhou polovinu:
Sloučení hovorů (ar, m + 1, r)
- Sloučit poloviny seřazené v kroku 2 a 3:
Sloučení hovoru (ar, l, m, r)
3) Dynamický programovací algoritmus
Tyto algoritmy fungují tak, že si pamatují výsledky minulého běhu a používají je k nalezení nových výsledků. Jinými slovy, dynamický programovací algoritmus řeší složité problémy tak, že jej rozdělí na několik jednoduchých dílčích problémů a poté každý z nich vyřeší jednou a poté je uloží pro budoucí použití.
Fibonacciho sekvence je dobrým příkladem pro algoritmy dynamického programování, můžete vidět, že funguje v pseudokódu:
Fibonacci (N) = 0 (pro n = 0)
= 0 (pro n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (pro n> 1)
4) Greedy Algorithm
Tyto algoritmy se používají k řešení problémů s optimalizací. V tomto algoritmu najdeme lokálně optimální řešení (bez ohledu na budoucí důsledky) a doufáme, že najdeme optimální řešení na globální úrovni.
Tato metoda nezaručuje, že budeme schopni najít optimální řešení.
Algoritmus má 5 složek:
- Prvním z nich je soubor kandidátů, ze kterého se snažíme najít řešení.
- Funkce výběru, která pomáhá vybrat nejlepší možný kandidát.
- Funkce proveditelnosti, která pomáhá při rozhodování, zda lze kandidáta použít k nalezení řešení.
- Objektivní funkce, která přiřadí hodnotu možnému řešení nebo částečnému řešení
- Funkce řešení, která informuje, kdy jsme našli řešení problému.
Huffman Coding a Dijkstraův algoritmus jsou dva příklady, kde se používá Greedyho algoritmus.
V Huffmanově kódování prochází algoritmus zprávou a v závislosti na frekvenci znaků v této zprávě přiřazuje každému znaku kódování s proměnnou délkou. Chcete-li provést Huffmanovo kódování, musíme nejprve sestavit Huffmanův strom ze vstupních znaků a poté procházet stromem, aby se těmto znakům přiřadily kódy.
5) Algoritmus hrubé síly
Toto je jeden z nejjednodušších algoritmů v konceptu. Algoritmus hrubé síly naslepo iteruje všechna možná řešení pro hledání jednoho nebo více než jednoho řešení, které může vyřešit funkci. Přemýšlejte o hrubé síle jako o využití všech možných kombinací čísel k otevření trezoru.
Zde je příklad sekvenčního vyhledávání prováděného pomocí hrubé síly:
Algoritmus S_Search (A (0..n), X)
A (n) ← X
i ← 0
Zatímco A (i) ≠ X ano
i ← i + 1
pokud i <n vrátím i
jinak návrat -1
6) Algoritmus zpětného sledování
Zpětné sledování je technika k nalezení řešení problému v inkrementálním přístupu. Řeší problémy rekurzivně a pokouší se dostat k řešení problému řešením jednoho problému současně. Pokud se některému z řešení nezdaří, odebereme jej a zpětně nalezneme jiné řešení.
Jinými slovy, algoritmus zpětného sledování řeší dílčí problém a pokud se mu nepodaří problém vyřešit, zruší poslední krok a začne znovu hledat řešení problému.
Problém N Queens je dobrým příkladem, jak vidět algoritmus zpětného sledování v akci. Problém N Queen uvádí, že v šachovnici je N kusů královen a musíme je uspořádat tak, aby žádná královna nemohla zaútočit na jakoukoli jinou královnu v šachovnici, jakmile bude jednou uspořádána.
Nyní se podívejme na algoritmus SolveNQ a funkce Check Valid k vyřešení problému:
CheckValid (šachovnice, řádek, sloupec)
Start
Pokud je na levé straně aktuálního sloupce Queen, vraťte false
Pokud je královna na levém horním úhlopříčku, vraťte false
Pokud je královna na levém dolním úhlopříčku, vraťte false
Návrat pravda
Konec
SolveNQ (Board, Column)
Start
Pokud jsou všechny sloupce plné, vraťte true
Pro každou řadu na šachovnici
Dělat
Pokud, CheckValid (deska, x, sloupec), pak
Postavte královnu do buňky (x, sloupec) na desce
Pokud SolveNQ (deska, sloupec + 1) = True, pak vraťte true.
Jinak odstraňte královnu z buňky (x, sloupec) z desky
Hotovo
Návrat nepravdivý
Konec
Závěr - typy algoritmů
Algoritmy jsou za většinou působivých věcí, které mohou počítače dělat, a tyto jsou jádrem většiny počítačových úloh. Lepší algoritmy vám pomohou nejen v tom, že jste úspěšným programátorem, ale také se stanete efektivnější.
Doporučené články
Toto byl průvodce Typy algoritmů. Zde diskutujeme o Top 6 důležitých typech algoritmů s jejich funkcemi. Další informace naleznete také v dalších navrhovaných článcích -
- Úvod do algoritmu
- Algoritmus v programování
- Rozhovor s otázkami algoritmu
- Factorial v Pythonu | Techniky
- Algoritmy rychlého třídění v Javě
- Top 6 algoritmů třídění v JavaScriptu