Druhy algoritmů Naučte se prvních 6 důležitých typů algoritmů

Obsah:

Anonim

Ú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

  1. Najděte středový bod a rozdělte dané pole na dvě poloviny:

střední m = (l + r) / 2

  1. Volání slučování pro první polovinu:

Volání hromadné korespondence (ar, l, m)

  1. Volání slučování pro druhou polovinu:

Sloučení hovorů (ar, m + 1, r)

  1. 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 -

  1. Úvod do algoritmu
  2. Algoritmus v programování
  3. Rozhovor s otázkami algoritmu
  4. Factorial v Pythonu | Techniky
  5. Algoritmy rychlého třídění v Javě
  6. Top 6 algoritmů třídění v JavaScriptu