Uvod v algoritme
Algoritem je zaporedje korakov, ki opisujejo, kako lahko težavo rešimo. Vsak računalniški program, ki se konča z rezultatom, v osnovi temelji na algoritmu. Algoritmi pa niso omejeni samo na uporabo v računalniških programih, ampak jih lahko uporabimo tudi za reševanje matematičnih problemov in za številne zadeve vsakodnevnega življenja. Glede na njihovo delovanje lahko algoritme razdelimo na več vrst. Oglejmo si nekaj pomembnih.
Vrste algoritma
Obstaja več vrst algoritmov, vendar so temeljne vrste algoritmov:
1) rekurzivni algoritem
To je eden najzanimivejših algoritmov, saj se sam imenuje z manjšo vrednostjo kot vhodi, ki jih dobi po reševanju trenutnih vhodov. Z enostavnejšimi besedami gre za algoritem, ki se večkrat pokliče, dokler se težava ne reši.
Težave, kot sta Hanojski stolp ali DFS grafikona, je mogoče enostavno rešiti z uporabo teh algoritmov.
Tu je na primer koda, ki poišče faktografsko uporabo z algoritmom rekurzije:
Dejstvo (y)
Če je y 0
vrnitev 1
return (y * Dejstvo (y-1)) / * tu se zgodi rekurzija * /
2) Algoritem razdelite in osvojite
To je še en učinkovit način reševanja številnih težav. V algoritmih Divide and Conquer algoritem razdelite na dva dela, prvi deli pa problem razdelijo na manjše podprobleme iste vrste. Nato se v drugem delu te manjše težave rešijo in nato seštevajo (združijo), da nastane končna rešitev problema.
Združevanje in hitro razvrščanje je mogoče izvesti z algoritmi delitve in osvajanja. Tukaj je psevdokod algoritma razvrščanja združevanja, ki vam daje primer:
MergeSorting (ar (), l, r)
Če je r> l
- Poiščite sredino, ki bo dano matriko razdelila na dve polovici:
srednja m = (l + r) / 2
- Pokliči mergeSorting za prvo polovico:
Pokliči mergeSorting (ar, l, m)
- Pokliči mergeSorting za drugo polovico:
Pokliči mergeSorting (ar, m + 1, r)
- Združite polovice, razvrščene v korakih 2 in 3:
Spajanje klicev (ar, l, m, r)
3) Algoritem dinamičnega programiranja
Ti algoritmi delujejo tako, da si zapomnijo rezultate pretekle vožnje in jih uporabijo za iskanje novih rezultatov. Z drugimi besedami, algoritem dinamičnega programiranja reši zapletene težave tako, da ga razbije na več preprostih podproblemov in nato vsakega od njih enkrat reši in nato shrani za nadaljnjo uporabo.
Fibonaccijevo zaporedje je dober primer za algoritme dinamičnega programiranja, lahko ga vidite v psevdo kodi:
Fibonaccije (N) = 0 (za n = 0)
= 0 (za n = 1)
= Fibonaccije (N-1) + Finacči (N-2) (za n> 1)
4) pohlepni algoritem
Ti algoritmi se uporabljajo za reševanje težav z optimizacijo. V tem algoritmu najdemo lokalno optimalno rešitev (ne glede na kakršne koli posledice v prihodnosti) in upamo, da bomo našli optimalno rešitev na svetovni ravni.
Metoda ne zagotavlja, da bomo lahko našli optimalno rešitev.
Algoritem ima 5 komponent:
- Prva je skupina kandidatov, iz katere skušamo najti rešitev.
- Izbirna funkcija, ki pomaga izbrati najboljšega možnega kandidata.
- Funkcionalna funkcija, ki pomaga pri odločitvi, ali bo kandidata mogoče najti rešitev.
- Objektivna funkcija, ki pripisuje vrednost možni rešitvi ali delni rešitvi
- Rešitvena funkcija, ki pove, kdaj smo našli rešitev problema.
Huffmanovo kodiranje in Dijkstra algoritem sta glavna primera, kjer se uporablja algoritem pohlep.
Pri Huffmanovem kodiranju algoritem preide sporočilo in glede na frekvenco znakov v tem sporočilu vsakemu znaku dodeli kodiranje spremenljive dolžine. Če želimo narediti Huffmanovo kodiranje, moramo najprej zgraditi Huffmanovo drevo iz vhodnih znakov in nato preiti skozi drevo, da bomo znakom dodelili kodo.
5) Algoritem Brute Force
To je eden najpreprostejših algoritmov v konceptu. Algoritem brutalne sile slepo ponavlja vse možne rešitve za iskanje ene ali več rešitev, ki lahko rešijo funkcijo. Za odpiranje sefa pomislite na brutalno silo kot uporabo vseh možnih kombinacij številk.
Tu je primer zaporednega iskanja, opravljenega z uporabo brutalne sile:
Algoritem S_preiskava (A (0..n), X)
A (n) ← X
i ← 0
Medtem ko A (i) ≠ X
i ← i + 1
če se vrnem <n i
drugače vrni -1
6) Algoritem za nazaj
Backtracking je tehnika iskanja posameznega problema s postopnim postopkom. Probleme rekurira rekurzivno in poskuša priti do rešitve problema tako, da naenkrat reši en kos problema. Če ena od rešitev ne uspe, jo odstranimo in poiščemo drugo rešitev.
Z drugimi besedami, algoritem za sledenje reši podproblemo in če težave ne reši, razveljavi zadnji korak in začne znova iskati rešitev problema.
Težava N Queens je en dober primer za prikaz algoritma Backtracking v akciji. Problem N Queen pravi, da je v šahovski deski N koščkov kraljev in jih moramo razporediti tako, da nobena kraljica ne more napadati nobene kraljice v deski, ki je enkrat organizirana.
Zdaj si oglejmo algoritem SolveNQ in preverimo veljavne funkcije za rešitev težave:
CheckValid (šahovnica, vrstica, stolpec)
Začni
Če je na levi strani trenutnega stolpca kraljica, vrnite false
Če je kraljica na zgornji levi diagonali, vrnite napačno
Če je kraljica v spodnji levi diagonali, vrnite napačno
Vrnitev resnična
Konec
SolveNQ (tabla, stolpec)
Začni
Če so vsi stolpci polni, vrnite true
Za vsako vrstico v šahovnici
Naredi
Če, CheckValid (tabla, x, stolpec), potem
Kraljico nastavite na celico (x, stolpec) na tabli
Če je SolveNQ (tabla, stolpec + 1) = True, vrnite true.
Drugače, kraljico odstranite iz celice (x, stolpec) z plošče
Končano
Vrnite napačno
Konec
Zaključek - Vrste algoritmov
Algoritmi stojijo za večino impresivnih stvari, ki jih računalniki zmorejo, in ti so v središču večine računalniških nalog. Če boste boljši z algoritmi, vam ne bo le pomagalo, da boste uspešni programer, ampak boste postali tudi bolj učinkoviti.
Priporočeni članki
To je vodnik za Vrste algoritmov. Tukaj razpravljamo o prvih 6 pomembnih vrstah algoritmov z njihovimi funkcijami. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -
- Uvod v algoritem
- Algoritem v programiranju
- Vprašanja o intervjuju z algoritmom
- Factorial v Pythonu | Tehnike
- Hitro razvrščanje algoritmov na Javi
- Najboljših 6 algoritmov za razvrščanje v JavaScript