Úvod do algoritmov
Algoritmus je postupnosť krokov, ktoré popisujú, ako možno problém vyriešiť. Každý počítačový program, ktorý končí výsledkom, je v zásade založený na algoritme. Algoritmy sa však neobmedzujú iba na použitie v počítačových programoch, môžu sa však použiť aj na riešenie matematických problémov a na mnoho záležitostí každodenného života. Na základe toho, ako fungujú, môžeme rozdeliť algoritmy do viacerých typov. Pozrime sa na niektoré z tých dôležitých.
Druhy algoritmov
Existuje veľa typov algoritmov, ale základnými typmi algoritmov sú:
1) Rekurzívny algoritmus
Toto je jeden z najzaujímavejších algoritmov, pretože sa nazýva menšou hodnotou ako vstupy, ktoré získava po riešení aktuálnych vstupov. Jednoduchšie povedané, je to algoritmus, ktorý sa volá opakovane, kým sa problém nevyrieši.
Problémy, ako je Hanojská veža alebo DFS grafu, sa dajú pomocou týchto algoritmov ľahko vyriešiť.
Napríklad tu je kód, ktorý nájde faktoriál pomocou algoritmu rekurzie:
Fakt (y)
Ak y je 0
návrat 1
návrat (y * fakt (y-1)) / * tu dochádza k rekurzi * /
2) Algoritmus delenia a dobývania
Toto je ďalší efektívny spôsob riešenia mnohých problémov. V algoritmoch Rozdeliť a Dobiť rozdeľte algoritmus na dve časti, prvé časti rozdeľujú problém po ruke na menšie podpriečinky rovnakého typu. Potom sa v druhej časti tieto menšie problémy vyriešia a potom spoja (kombinujú), aby sa dosiahlo konečné riešenie problému.
Zlúčenie triedenia a rýchle triedenie je možné vykonať pomocou algoritmov rozdelenia a dobyvania. Tu je pseudokód algoritmu zlúčenia zoradenia, ktorý vám dá príklad:
MergeSorting (ar (), l, r)
Ak r> l
- Nájdite stredný bod na rozdelenie daného poľa na dve polovice:
stredná m = (l + r) / 2
- Zlučovanie hovorov pre prvú polovicu:
Hromadné spojenie hovoru (ar, l, m)
- Zlučovanie hovorov pre druhú polovicu:
Hromadné spojenie hovoru (ar, m + 1, r)
- Zlúčte polovice zoradené v krokoch 2 a 3:
Hromadné volanie (ar, l, m, r)
3) Algoritmus dynamického programovania
Tieto algoritmy fungujú tak, že si pamätajú výsledky minulého cyklu a používajú ich na nájdenie nových výsledkov. Inými slovami, dynamický programovací algoritmus rieši zložité problémy tým, že ich rozdeľuje do viacerých jednoduchých čiastkových problémov, potom ich každý vyrieši a potom ich uloží na ďalšie použitie.
Fibonacciho sekvencia je dobrým príkladom pre algoritmy dynamického programovania, môžete vidieť, že funguje v pseudokódu:
Fibonacci (N) = 0 (pre n = 0)
= 0 (pre n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (pre n> 1)
4) Greedyov algoritmus
Tieto algoritmy sa používajú na riešenie problémov s optimalizáciou. V tomto algoritme nachádzame lokálne optimálne riešenie (bez ohľadu na budúce dôsledky) a dúfame, že nájdeme optimálne riešenie na globálnej úrovni.
Táto metóda nezaručuje, že sa nám podarí nájsť optimálne riešenie.
Algoritmus má 5 komponentov:
- Prvým je súbor kandidátov, z ktorého sa snažíme nájsť riešenie.
- Funkcia výberu, ktorá pomáha vybrať najlepší možný kandidát.
- Funkcia uskutočniteľnosti, ktorá pomáha pri rozhodovaní, či sa kandidát môže použiť na nájdenie riešenia.
- Objektívna funkcia, ktorá priradí hodnotu možnému riešeniu alebo čiastočnému riešeniu
- Funkcia riešenia, ktorá hovorí, keď sme našli riešenie problému.
Huffman Coding a Dijkstraov algoritmus sú dva príklady, kde sa používa Greedyov algoritmus.
Pri Huffmanovom kódovaní algoritmus prechádza správou av závislosti od frekvencie znakov v tejto správe priradí každému znaku kódovanie s rôznou dĺžkou. Aby bolo možné vykonať Huffmanovo kódovanie, musíme najprv zo vstupných znakov zostaviť Huffmanov strom a potom prejsť stromom, aby sa týmto znakom priradili kódy.
5) Algoritmus hrubej sily
Toto je jeden z najjednoduchších algoritmov v koncepcii. Algoritmus hrubej sily slepo iteruje všetky možné riešenia na hľadanie jedného alebo viacerých riešení, ktoré môžu vyriešiť funkciu. Pomysli na hrubú silu ako na použitie všetkých možných kombinácií čísel na otvorenie trezoru.
Tu je príklad postupného vyhľadávania pomocou hrubej sily:
Algoritmus S_Search (A (0..n), X)
A (n) ← X
i ← 0
Zatiaľ čo A (i) ≠ X áno
i ← i + 1
ak i <n vrátim i
inak návrat -1
6) Algoritmus spätného sledovania
Spätné sledovanie je technika na nájdenie riešenia problému v inkrementálnom prístupe. Rieši rekurzívne problémy a pokúša sa vyriešiť problém vyriešením jedného problému naraz. Ak niektoré z riešení zlyhajú, odstránime ho a nájdeme ďalšie riešenie.
Inými slovami, algoritmus spätného sledovania rieši čiastkový problém a ak sa mu nepodarí problém vyriešiť, vráti späť posledný krok a začne znova hľadať riešenie problému.
Problém N Queens je dobrým príkladom toho, ako vidieť algoritmus spätného sledovania v akcii. Problém N Queen uvádza, že v šachovnici je N kusov kráľovien a musíme ich zariadiť tak, aby žiadna kráľovná nemohla zaútočiť na žiadnu inú kráľovnú v rade, keď bude usporiadaná.
Teraz sa pozrieme na algoritmus SolveNQ a funkcie Check Valid na vyriešenie problému:
CheckValid (šachovnica, riadok, stĺpec)
štart
Ak sa na ľavej strane aktuálneho stĺpca nachádza kráľovná, vráťte hodnotu false
Ak je kráľovná v ľavom hornom rohu, vráťte hodnotu false
Ak je kráľovná v ľavom dolnom rohu, vrátite hodnotu false
Návrat pravda
Koniec
SolveNQ (Board, Column)
štart
Ak sú všetky stĺpce plné, vrátite true
Pre každý rad nachádzajúci sa v šachovnici
do
Ak, CheckValid (doska, x, stĺpec), potom
Postavte kráľovnú do bunky (x, stĺpec) na doske
Ak je SolveNQ (doska, stĺpec + 1) = True, vráti true.
Inak vyberte kráľovnú z bunky (x, stĺpec) z hracej plochy
hotový
Návrat nepravdivý
Koniec
Záver - Druhy algoritmov
Algoritmy stoja za väčšinou pôsobivých vecí, ktoré môžu počítače urobiť, a tieto tvoria jadro väčšiny počítačových úloh. Lepší algoritmus vám pomôže nielen v tom, aby ste boli úspešným programátorom, ale tiež sa stanete efektívnejšími.
Odporúčané články
Toto bol sprievodca Typy algoritmov. Tu diskutujeme o 6 najdôležitejších typoch algoritmov s ich funkciami. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Úvod do algoritmu
- Algoritmus v programovaní
- Otázky týkajúce sa rozhovoru s algoritmom
- Factorial v Pythone | techniky
- Algoritmy rýchleho triedenia v Jave
- Top 6 triediaci algoritmus v JavaScripte