Introduktion til algoritmer
En algoritme er en sekvens af trin, der beskriver, hvordan et problem kan løses. Hvert computerprogram, der slutter med et resultat, er dybest set baseret på en algoritme. Algoritmer er imidlertid ikke kun begrænset til brug i computerprogrammer, disse kan også bruges til at løse matematiske problemer og til mange spørgsmål i det daglige liv. Baseret på hvordan de fungerer, kan vi opdele algoritmer i flere typer. Lad os se på nogle af de vigtige.
Typer af algoritme
Der er mange typer af algoritmer, men de grundlæggende typer af algoritmer er:
1) Rekursiv algoritme
Dette er en af de mest interessante algoritmer, da den kalder sig selv med en mindre værdi som input, som den får efter løsning af de aktuelle input. Med mere enklere ord er det en algoritme, der kalder sig gentagne gange, indtil problemet er løst.
Problemer som Tower of Hanoi eller DFS of a Graph kan let løses ved hjælp af disse algoritmer.
Her er f.eks. En kode, der finder en faktorial ved hjælp af en rekursionsalgoritme:
Faktisk (y)
Hvis y er 0
retur 1
return (y * Fact (y-1)) / * det er her rekursionen sker * /
2) Del og erobre algoritme
Dette er en anden effektiv måde at løse mange problemer på. I Divide and Conquer-algoritmer skal du opdele algoritmen i to dele, de første dele deler problemet til rådighed i mindre underproblemer af samme type. På den anden del løses disse mindre problemer og tilsættes derefter sammen (kombineres) for at producere den endelige løsning af problemet.
Flettesortering og hurtig sortering kan udføres med dividerings- og erobringsalgoritmer. Her er pseudokoden i algoritmen for sammenfletningssortering for at give dig et eksempel:
MergeSorting (ar (), l, r)
Hvis r> l
- Find midtpunktet for at opdele det givne array i to halvdele:
midterste m = (l + r) / 2
- Call mergeSortering for første halvår:
Call mergeSorting (ar, l, m)
- Call mergeSortering til anden halvdel:
Call mergeSorting (ar, m + 1, r)
- Flet halvdelene sorteret i trin 2 og 3:
Opkaldsfletning (ar, l, m, r)
3) Dynamisk programmeringsalgoritme
Disse algoritmer fungerer ved at huske resultaterne fra det forrige løb og bruge dem til at finde nye resultater. Med andre ord løser dynamisk programmeringsalgoritme komplekse problemer ved at opdele den i flere enkle underproblemer, og derefter løser den hver af dem én gang og gemmer dem derefter til fremtidig brug.
Fibonacci-sekvens er et godt eksempel på dynamiske programmeringsalgoritmer, du kan se den fungerer i pseudokoden:
Fibonacci (N) = 0 (for n = 0)
= 0 (for n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (for n> 1)
4) Grådig algoritme
Disse algoritmer bruges til at løse optimeringsproblemer. I denne algoritme finder vi en lokalt optimal løsning (uden hensyntagen til nogen konsekvens i fremtiden) og håber at finde den optimale løsning på verdensplan.
Metoden garanterer ikke, at vi kan finde en optimal løsning.
Algoritmen har 5 komponenter:
- Den første er et kandidatsæt, hvorfra vi forsøger at finde en løsning.
- En valgfunktion, der hjælper med at vælge den bedst mulige kandidat.
- En mulighedsfunktion, der hjælper med at beslutte, om kandidaten kan bruges til at finde en løsning.
- En objektiv funktion, der tildeler værdi til en mulig løsning eller til en delvis løsning
- Løsningsfunktion, der fortæller, hvornår vi har fundet en løsning på problemet.
Huffman Coding og Dijkstra's algoritme er to gode eksempler, hvor Grådig algoritme bruges.
Ved Huffman-kodning gennemgår algoritmen en meddelelse, og afhængigt af hyppigheden af tegnene i denne meddelelse tildeler den for hver karakter en kodning med variabel længde. For at udføre Huffman-kodning skal vi først opbygge et Huffman-træ fra input-tegnene og derefter gå gennem træet for at tildele koder til tegnene.
5) Brute Force-algoritme
Dette er en af de enkleste algoritmer i konceptet. En brute force-algoritme itererer blindt alle mulige løsninger for at søge efter en eller flere end en løsning, der muligvis løser en funktion. Tænk på brute force som at bruge alle mulige kombinationer af tal til at åbne et pengeskab.
Her er et eksempel på Sequential Search udført ved hjælp af brute force:
Algoritme S_Search (A (0..n), X)
A (n) ← X
i ← 0
Mens A (i) ≠ X gør
i ← i + 1
hvis jeg <returnerer jeg
ellers vende tilbage -1
6) Backtracking-algoritme
Backtracking er en teknik til at finde en løsning på et problem i en inkrementel tilgang. Det løser rekursivt problemer og forsøger at komme til en løsning på et problem ved at løse et stykke af problemet ad gangen. Hvis en af løsningen mislykkes, fjerner vi den og backtrack for at finde en anden løsning.
Med andre ord løser en backtracking-algoritme et underproblem, og hvis den ikke løser problemet, fortrydes det det sidste trin og begynder igen med at finde løsningen på problemet.
N Queens-problem er et godt eksempel på at se Backtracking-algoritmen i aktion. N Queen's Problem siger, at der er N stykker af Queens i et skakbræt, og vi er nødt til at arrangere dem, så ingen dronning kan angribe nogen anden dronning i bestyrelsen, når den først er organiseret.
Lad os nu se på SolveNQ-algoritmen og tjek gyldige funktioner for at løse problemet:
CheckValid (Skakbræt, række, kolonne)
Start
Hvis der er en dronning til venstre for den aktuelle søjle, skal du vende tilbage falsk
Hvis dronningen er i diagonal øverst til venstre, skal du vende tilbage falsk
Hvis dronningen er i diagonal nederst til venstre, skal du vende tilbage falsk
Returner sandt
Ende
SolveNQ (Board, Column)
Start
Hvis alle kolonner er fulde, returneres sand
For hver række til stede i skakbrættet
Do
Hvis, CheckValid (kort, x, kolonne), så
Sæt dronningen ved celle (x, kolonne) på brættet
Hvis SolveNQ (kort, kolonne + 1) = Sandt, skal du returnere sand.
Ellers fjernes dronningen fra cellen (x, kolonne) fra brættet
Færdig
Returner falsk
Ende
Konklusion - Algoritmer
Algoritmer ligger bag de fleste af de imponerende ting, computere kan gøre, og disse er kernen i de fleste computeropgaver. At være bedre med algoritmer vil ikke kun hjælpe dig med at være en succesrig programmerer, men du vil også blive mere effektiv.
Anbefalede artikler
Dette har været en guide til typer af algoritmer. Her diskuterer vi de 6 vigtigste typer af algoritmer med deres funktioner. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -
- Introduktion til algoritme
- Algoritme i programmering
- Spørgsmål til algoritmeintervju
- Factorial i Python | Teknikker
- Hurtig sorteringsalgoritmer i Java
- Top 6 sorteringsalgoritme i JavaScript