Inleiding tot algoritmen
Een algoritme is een reeks stappen die beschrijven hoe een probleem kan worden opgelost. Elk computerprogramma dat eindigt met een resultaat, is in principe gebaseerd op een algoritme. Algoritmen zijn echter niet alleen beperkt voor gebruik in computerprogramma's, deze kunnen ook worden gebruikt om wiskundige problemen op te lossen en voor veel zaken in het dagelijks leven. Op basis van hoe ze werken, kunnen we algoritmen in meerdere typen verdelen. Laten we een paar van de belangrijkste bekijken.
Soorten algoritme
Er zijn veel soorten algoritmen, maar de fundamentele soorten algoritmen zijn:
1) Recursief algoritme
Dit is een van de meest interessante algoritmen omdat het zichzelf noemt met een kleinere waarde als ingangen die het krijgt na het oplossen van de huidige ingangen. In eenvoudiger woorden, het is een algoritme dat zichzelf herhaaldelijk oproept totdat het probleem is opgelost.
Problemen zoals de Tower of Hanoi of DFS van een grafiek kunnen eenvoudig worden opgelost met behulp van deze algoritmen.
Hier is bijvoorbeeld een code die een faculteit vindt met behulp van een recursie-algoritme:
Fact (y)
Als y 0 is
terug 1
return (y * Fact (y-1)) / * dit is waar de recursie plaatsvindt * /
2) Verdeel en heers algoritme
Dit is een andere effectieve manier om veel problemen op te lossen. Verdeel in algoritmen Verdeel en Verover het algoritme in twee delen, de eerste delen verdelen het aanwezige probleem in kleinere subproblemen van hetzelfde type. Vervolgens worden in het tweede deel deze kleinere problemen opgelost en vervolgens samengevoegd (gecombineerd) om de uiteindelijke oplossing van het probleem te produceren.
Sorteren samenvoegen en snel sorteren kan worden gedaan met verdeel en heers algoritmen. Hier is de pseudocode van het merge sort-algoritme om u een voorbeeld te geven:
MergeSorting (ar (), l, r)
Als r> l
- Zoek het middelpunt om de gegeven array in twee helften te verdelen:
middelste m = (l + r) / 2
- Oproep samenvoegen voor de eerste helft:
Oproep samenvoegen sorteren (ar, l, m)
- Oproep samenvoegen voor de tweede helft:
Oproep samenvoegen sorteren (ar, m + 1, r)
- Voeg de helften samen gesorteerd in stap 2 en 3:
Oproep samenvoegen (ar, l, m, r)
3) Dynamisch programmeeralgoritme
Deze algoritmen werken door de resultaten van de vorige run te onthouden en ze te gebruiken om nieuwe resultaten te vinden. Met andere woorden, het dynamische programmeeralgoritme lost complexe problemen op door het op te splitsen in meerdere eenvoudige subproblemen en vervolgens elk een keer op te lossen en vervolgens op te slaan voor toekomstig gebruik.
Fibonacci-reeks is een goed voorbeeld voor dynamische programmeeralgoritmen, je kunt het zien werken in de pseudocode:
Fibonacci (N) = 0 (voor n = 0)
= 0 (voor n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (voor n> 1)
4) Hebzuchtig algoritme
Deze algoritmen worden gebruikt voor het oplossen van optimalisatieproblemen. In dit algoritme vinden we een lokaal optimale oplossing (zonder rekening te houden met enig gevolg in de toekomst) en hopen we de optimale oplossing op mondiaal niveau te vinden.
De methode garandeert niet dat we een optimale oplossing kunnen vinden.
Het algoritme bestaat uit 5 componenten:
- De eerste is een kandidaatset waaruit we een oplossing proberen te vinden.
- Een selectiefunctie die helpt bij het kiezen van de best mogelijke kandidaat.
- Een haalbaarheidsfunctie die helpt bij het beslissen of de kandidaat kan worden gebruikt om een oplossing te vinden.
- Een objectieve functie die waarde toekent aan een mogelijke oplossing of aan een gedeeltelijke oplossing
- Oplossingsfunctie die aangeeft wanneer we een oplossing voor het probleem hebben gevonden.
Huffman Coding en het algoritme van Dijkstra zijn twee belangrijke voorbeelden waarin Greedy-algoritme wordt gebruikt.
In Huffman-codering doorloopt het algoritme een bericht en, afhankelijk van de frequentie van de tekens in dat bericht, kent het voor elk teken een codering met variabele lengte toe. Om Huffman-codering te doen, moeten we eerst een Huffman-boom bouwen van de invoertekens en vervolgens door de boom bladeren om codes aan de tekens toe te wijzen.
5) Brute Force-algoritme
Dit is een van de eenvoudigste algoritmen in het concept. Een brute force-algoritme itereert blindelings alle mogelijke oplossingen om een of meer dan één oplossing te zoeken die een functie kan oplossen. Beschouw brute kracht als het gebruiken van alle mogelijke combinaties van getallen om een kluis te openen.
Hier is een voorbeeld van sequentieel zoeken met brute kracht:
Algoritme S_Search (A (0..n), X)
A (n) ← X
i ← 0
Terwijl A (i) ≠ X doen
i ← i + 1
als ik <n terugkeer i
anders terug -1
6) Terugtracking-algoritme
Backtracking is een techniek om een oplossing voor een probleem te vinden in een incrementele aanpak. Het lost problemen recursief op en probeert een oplossing voor een probleem te vinden door een deel van het probleem tegelijk op te lossen. Als een van de oplossingen faalt, verwijderen we deze en gaan we terug om een andere oplossing te vinden.
Met andere woorden, een backtracking-algoritme lost een subprobleem op en als het het probleem niet oplost, maakt het de laatste stap ongedaan en begint het opnieuw met het vinden van de oplossing voor het probleem.
Het probleem van N Queens is een goed voorbeeld om het Backtracking-algoritme in actie te zien. Het N-koninginprobleem stelt dat er N-stukken koningin in een schaakbord zijn en dat we deze zo moeten rangschikken dat geen enkele koningin een andere koningin in het bord kan aanvallen als deze eenmaal georganiseerd is.
Laten we nu eens kijken naar het SolveNQ-algoritme en de functies Geldig controleren om het probleem op te lossen:
CheckValid (schaakbord, rij, kolom)
Begin
Als er links van de huidige kolom een koningin staat, retourneer dan false
Als de koningin diagonaal linksboven is, keer dan onwaar terug
Als de koningin diagonaal linksonder staat, keer dan onwaar terug
Keer terug waar
Einde
SolveNQ (bord, kolom)
Begin
Als alle kolommen vol zijn, wordt true geretourneerd
Voor elke rij aanwezig in het schaakbord
Doen
Indien, CheckValid (bord, x, kolom), dan
Zet de koningin op cel (x, kolom) op het bord
Als SolveNQ (bord, kolom + 1) = True, retourneer dan true.
Anders, verwijder de koningin uit de cel (x, kolom) van het bord
Gedaan
Return false
Einde
Conclusie - Soorten algoritmen
Algoritmen liggen achter de meeste van de indrukwekkende dingen die computers kunnen doen en deze vormen de kern van de meeste computertaken. Beter worden met algoritmen zal je niet alleen helpen om een succesvolle programmeur te zijn, maar je zult ook efficiënter worden.
Aanbevolen artikelen
Dit is een gids voor soorten algoritmen. Hier bespreken we de Top 6 belangrijke soorten algoritmen met hun functies. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -
- Inleiding tot algoritme
- Algoritme in programmeren
- Vragen tijdens solliciteren bij Algorithm
- Factorial in Python | technieken
- Snel sorteren algoritmen in Java
- Top 6 sorteeralgoritme in JavaScript