Introduksjon til algoritmer
En algoritme er en sekvens med trinn som beskriver hvordan et problem kan løses. Hvert dataprogram som ender med et resultat, er i utgangspunktet basert på en algoritme. Algoritmer er imidlertid ikke bare begrenset til bruk i dataprogrammer, disse kan også brukes til å løse matematiske problemer og i mange saker i det daglige liv. Basert på hvordan de fungerer, kan vi dele algoritmer i flere typer. La oss ta en titt på noen av de viktige.
Typer av algoritme
Det er mange typer algoritmer, men de grunnleggende typer algoritmer er:
1) Rekursiv algoritme
Dette er en av de mest interessante algoritmene som den kaller seg med en mindre verdi som innganger som den får etter å ha løst for gjeldende innganger. Med enklere ord er det en algoritme som kaller seg gjentatte ganger til problemet er løst.
Problemer som Tower of Hanoi eller DFS of a Graph kan enkelt løses ved å bruke disse algoritmene.
Her er for eksempel en kode som finner en faktorial ved hjelp av en rekursjonsalgoritme:
Fakta (y)
Hvis y er 0
retur 1
return (y * Fact (y-1)) / * det er her rekursjonen skjer * /
2) Del og erobre algoritme
Dette er en annen effektiv måte å løse mange problemer på. I Divide and Conquer-algoritmer, del algoritmen i to deler, de første delene deler problemet for hånden i mindre underproblemer av samme type. Så på den andre delen, blir disse mindre problemene løst og deretter lagt sammen (kombinert) for å produsere den endelige løsningen av problemet.
Flettesortering og rask sortering kan gjøres med delings- og erobringsalgoritmer. Her er pseudokoden til algoritmen for sammenslåingssortering for å gi deg et eksempel:
MergeSorting (ar (), l, r)
Hvis r> l
- Finn midtpunktet for å dele det gitte arrayet i to halvdeler:
midten m = (l + r) / 2
- Call mergeSortering for første halvår:
Call mergeSorting (ar, l, m)
- Call mergeSortering for andre omgang:
Call mergeSorting (ar, m + 1, r)
- Slå sammen halvdelene sortert i trinn 2 og 3:
Samtalesammenslåing (ar, l, m, r)
3) Dynamisk programmeringsalgoritme
Disse algoritmene fungerer ved å huske resultatene fra forrige løp og bruke dem til å finne nye resultater. Med andre ord løser dynamisk programmeringsalgoritme komplekse problemer ved å dele den inn i flere enkle delproblemer, og deretter løser den hver av dem en gang for deretter å lagre dem for fremtidig bruk.
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 algoritmene brukes til å løse optimaliseringsproblemer. I denne algoritmen finner vi en lokalt optimal løsning (uten å ta hensyn til noen konsekvens i fremtiden) og håper å finne den optimale løsningen på globalt nivå.
Metoden garanterer ikke at vi vil kunne finne en optimal løsning.
Algoritmen har 5 komponenter:
- Den første er et kandidatsett som vi prøver å finne en løsning fra.
- En valgfunksjon som hjelper til å velge den best mulige kandidaten.
- En mulighetsfunksjon som hjelper til med å avgjøre om kandidaten kan brukes til å finne en løsning.
- En objektiv funksjon som tildeler verdi til en mulig løsning eller til en delvis løsning
- Løsningsfunksjon som forteller når vi har funnet en løsning på problemet.
Huffman Coding og Dijkstra's algoritme er to hovedeksempler der Greedy algoritm brukes.
I Huffman-koding går algoritmen gjennom en melding, og avhengig av frekvensen til tegnene i den meldingen, tilordner den en koding med variabel lengde. For å gjøre Huffman-koding, må vi først bygge et Huffman-tre fra inputtegnene og deretter gå gjennom treet for å tilordne koder til tegnene.
5) Brute Force Algoritme
Dette er en av de enkleste algoritmene i konseptet. En brute force-algoritme itererer blindt alle mulige løsninger for å søke i en eller flere enn en løsning som kan løse en funksjon. Tenk på brute force som å bruke alle mulige kombinasjoner av tall for å åpne en safe.
Her er et eksempel på Sequential Search gjort ved å bruke brute force:
Algoritme S_Search (A (0..n), X)
A (n) ← X
i ← 0
Mens A (i) ≠ X gjør
i ← i + 1
hvis jeg kommer tilbake
annet tilbake -1
6) Backtracking algoritme
Backtracking er en teknikk for å finne en løsning på et problem i en inkrementell tilnærming. Den løser problemer rekursivt og prøver å komme til en løsning på et problem ved å løse en del av problemet om gangen. Hvis en av løsningene mislykkes, fjerner vi den og baksporet for å finne en annen løsning.
Med andre ord løser en backtracking-algoritme et underproblem, og hvis den ikke klarer å løse problemet, angre det siste trinn og begynner igjen å finne løsningen på problemet.
N Queens-problem er ett godt eksempel for å se Backtracking-algoritmen i aksjon. N Queen's Problem uttaler at det er N stykker av Queens i et sjakkbrett, og vi må ordne dem slik at ingen dronning kan angripe noen annen dronning i styret når den er organisert.
La oss nå se på SolveNQ-algoritmen og Sjekk gyldige funksjoner for å løse problemet:
CheckValid (sjakkbrett, rad, kolonne)
Start
Hvis det er en dronning til venstre for den gjeldende kolonnen, så returner usann
Hvis dronningen er i diagonalen øverst til venstre, så returner usann
Hvis dronningen er i diagonalen nederst til venstre, så returner usann
Returner sant
Slutt
SolveNQ (Board, Column)
Start
Hvis alle kolonnene er fulle, returner du true
For hver rad til stede i sjakkbrettet
Gjøre
Hvis, CheckValid (tavle, x, kolonne), da
Sett dronningen til celle (x, kolonne) på tavlen
Hvis SolveNQ (brett, kolonne + 1) = True, så returner true.
Ellers, fjern dronningen fra cellen (x, kolonne) fra brettet
Ferdig
Returner falsk
Slutt
Konklusjon - Algoritmer
Algoritmer ligger bak det meste av det imponerende datamaskiner kan gjøre, og disse er kjernen i de fleste dataoppgaver. Å være bedre med algoritmer vil ikke bare hjelpe deg i å være en vellykket programmerer, men du vil også bli mer effektiv.
Anbefalte artikler
Dette har vært en guide til algoritmetyper. Her diskuterer vi de 6 viktigste viktige algoritmetyper med deres funksjoner. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -
- Introduksjon til algoritme
- Algoritme i programmering
- Spørsmål om algoritmeintervju
- Factorial i Python | teknikker
- Rask sorteringsalgoritmer i Java
- Topp 6 sorteringsalgoritme i JavaScript