Bevezetés az algoritmusokba
Az algoritmus lépések sorozata, amely leírja, hogyan lehet egy problémát megoldani. Minden olyan számítógépes program, amely eredményekkel zárul, alapvetően algoritmuson alapul. Az algoritmusok azonban nem csupán a számítógépes programokban való felhasználásra korlátozódnak, hanem felhasználhatók matematikai problémák megoldására és a mindennapi élet számos kérdésére. Az algoritmusok működésük alapján több típusra oszthatók. Vessen egy pillantást néhány fontosra.
Az algoritmus típusai
Sokféle algoritmus létezik, de az algoritmusok alapvető típusai a következők:
1) rekurzív algoritmus
Ez az egyik legérdekesebb algoritmus, mivel kisebb értékűnek nevezi magát bemenetekként, amelyeket az aktuális bemenetek megoldása után kap. Egyszerűbben fogalmazva: ez egy olyan algoritmus, amely többször felhívja magát, amíg a probléma megoldódik.
Az olyan algoritmusok segítségével könnyen megoldhatók a problémák, mint a Hanoi-torony vagy a Grafikon DFS-je.
Például, itt van egy olyan kód, amely egy rekurziós algoritmus segítségével egy faktort talál:
Tény (y)
Ha y értéke 0
visszatérés 1
visszatérés (y * tény (y-1)) / * itt történik a rekurzió * /
2) Ossza meg és hódítsa meg az algoritmust
Ez egy másik hatékony módszer sok probléma megoldására. A Divide and Conquer algoritmusokban ossza meg az algoritmust két részre, az első rész osztja a kezdeti problémát azonos típusú kisebb alproblémákra. Ezután a második részben ezeket a kisebb problémákat megoldják, majd összevonják (kombinálják) a probléma végső megoldásának előállításához.
Az egyesítés és a gyors válogatás elválasztható és meghódító algoritmusok segítségével végezhető el. Itt található az egyesítés rendezési algoritmusának álnév-kódja, amely példát mutat Önnek:
MergeSorting (ar (), l, r)
Ha r> l
- Keresse meg a középpontot, és ossza meg az adott tömböt két felére:
középső m = (l + r) / 2
- Call mergeSorting az első félévre:
Hívás mergeSorting (ar, l, m)
- Hívási egyesítésSorting a második félidőben:
Hívás mergeSorting (ar, m + 1, r)
- Egyesítse a 2. és 3. lépésben rendezett feleket:
Összehívás (ar, l, m, r)
3) Dinamikus programozási algoritmus
Ezek az algoritmusok úgy működnek, hogy megjegyzik a korábbi futtatás eredményeit, és új eredmények megtalálására használják őket. Más szavakkal, a dinamikus programozási algoritmus komplex problémákat old meg, több egyszerű alproblémává osztva, majd egyszerre oldja meg mindegyiket, és tárolja későbbi felhasználás céljából.
A Fibonacci szekvencia jó példa a dinamikus programozási algoritmusokra, láthatja, hogy az álkódban működik:
Fibonacci (N) = 0 (n = 0 esetén)
= 0 (n = 1 esetén)
= Fibonacci (N-1) + Finacchi (N-2) (n> 1 esetén)
4) Kapzsi algoritmus
Ezek az algoritmusok az optimalizálási problémák megoldására szolgálnak. Ebben az algoritmusban lokálisan optimális megoldást találunk (a jövőbeli következmények figyelembe vétele nélkül), és reméljük, hogy globális szinten is megtalálja az optimális megoldást.
A módszer nem garantálja, hogy képesek leszünk optimális megoldást találni.
Az algoritmus 5 összetevőből áll:
- Az első olyan jelöltkészlet, amelyből megpróbálunk megoldást találni.
- Kiválasztási funkció, amely segít kiválasztani a lehető legjobb jelöltet.
- Egy megvalósíthatósági funkció, amely segít annak eldöntésében, hogy a jelölt felhasználható-e megoldás megtalálására.
- Objektív funkció, amely értéket tulajdonít egy lehetséges megoldáshoz vagy egy részleges megoldáshoz
- Megoldás funkció, amely azt jelzi, hogy mikor találtunk megoldást a problémára.
A Huffman Coding és Dijkstra algoritmusa két kiváló példa a Greedy algoritmus alkalmazására.
Huffman-kódolás esetén az algoritmus egy üzeneten megy keresztül, és az üzenetben szereplő karakterek gyakoriságától függően minden karakterhez változó hosszúságú kódolást rendel. A Huffman-kódoláshoz először ki kell építenünk egy Huffman-fát a bemeneti karakterekből, majd át kell mozgatni a fán, hogy kódokat rendeljünk a karakterekhez.
5) Brute Force algoritmus
Ez a koncepció egyik legegyszerűbb algoritmusa. A nyers erő algoritmus vakon megismétli az összes lehetséges megoldást, hogy egy vagy több olyan megoldást keressen, amely egy funkciót megoldhat. Gondolj a nyers erőre, ha az összes lehetséges számkombinációt használja a széf megnyitásához.
Íme egy példa a szekvenciális keresésre, amelyet brutális erő alkalmazásával végeztek:
S_Search algoritmus (A (0..n), X)
A (n) ← X
i ← 0
Amíg A (i) ≠ X nem
i ← i + 1
ha i <n visszatér i
egyéb visszatérés -1
6) Visszakeresési algoritmus
Az utókövetés olyan módszer, amellyel fokozatosan oldódik meg a probléma megoldása. Rekurzív módon oldja meg a problémákat, és megpróbál megoldást találni egy probléma egy részének egyszerre történő megoldásával. Ha az egyik megoldás kudarcot vall, akkor eltávolítjuk és visszalépünk egy másik megoldás megtalálására.
Más szavakkal: egy visszakeresési algoritmus megoldja az alproblémát, és ha nem sikerül megoldani a problémát, akkor visszavonja az utolsó lépést, és újra elkezdi a probléma megoldását.
N A Queens-probléma egy jó példa a visszakeresési algoritmus működésének megtekintésére. Az N királynő problémája kijelenti, hogy N a darab Queens van a sakktáblában, és ezeket el kell rendeznünk úgy, hogy egyetlen királynő sem támadhat meg a táblán lévő másik királynőt.
Most nézzük meg a SolveNQ algoritmust és az Érvényes ellenőrzés funkciókat a probléma megoldásához:
CheckValid (sakktábla, sor, oszlop)
Rajt
Ha van egy királynő az aktuális oszlop bal oldalán, akkor térjen vissza hamis értékre
Ha a királynő a bal felső átlóban van, akkor térjen vissza
Ha a királynő a bal alsó átlóban van, akkor térjen vissza
Visszatérés igaz
vég
SolveNQ (tábla, oszlop)
Rajt
Ha az összes oszlop megtelt, akkor térjen vissza igazra
A sakktábla minden egyes sorához
Do
Ha, CheckValid (tábla, x, oszlop), akkor
Állítsa a királynőt a táblára (x, oszlop)
Ha SolveNQ (tábla, + 1 oszlop) = True, akkor térjen vissza true értékre.
Egyébként vegye le a királynőt a cellából (x, oszlop) a tábláról
Kész
Vissza hamis
vég
Következtetés - Algoritmusok típusai
Az algoritmusok mögött rejlik azok a lenyűgöző dolgok, amelyeket a számítógépek megtehetnek, és ezek képezik a legtöbb számítási feladat alapját. Ha jobb az algoritmusok, akkor nemcsak az segít abban, hogy sikeres programozó legyen, de hatékonyabbá válj is.
Ajánlott cikkek
Ez egy útmutató az Algoritmusok típusaihoz. Itt tárgyaljuk a 6 legfontosabb algoritmustípust funkciójukkal. A további javasolt cikkeken keresztül további információkat is megtudhat -
- Bevezetés az algoritmusba
- Algoritmus a programozásban
- Algoritmus interjú kérdései
- Faktérium a Pythonban technikák
- Gyors rendezési algoritmusok a Java-ban
- A 6 legnépszerűbb rendezési algoritmus a JavaScript-ben