Vrste algoritama - Naučite prvih 6 važnih vrsta algoritama

Sadržaj:

Anonim

Uvod u algoritme

Algoritam je niz koraka koji opisuju kako se problem može riješiti. Svaki računalni program koji završava rezultatom u osnovi se temelji na algoritmu. Algoritmi, međutim, nisu ograničeni samo za upotrebu u računalnim programima, već se mogu koristiti i za rješavanje matematičkih problema i u mnogim stvarima svakodnevnog života. Na temelju njihova funkcioniranja možemo podijeliti algoritme u više tipova. Pogledajmo neke od važnih.

Vrste algoritma

Postoji mnogo vrsta algoritama, ali temeljne vrste algoritama su:

1) rekurzivni algoritam

Ovo je jedan od najzanimljivijih algoritama jer se naziva manjom vrijednošću kao ulazima koji dobiva nakon rješavanja za trenutne ulaze. Jednostavnije rečeno, to je algoritam koji se poziva više puta dok se problem ne riješi.

Problemi poput Hanojske kule ili DFS-a grafikona mogu se lako riješiti korištenjem ovih algoritama.

Na primjer, ovdje je kôd koji nalazi faktororijum koristeći algoritam rekurzije:

Činjenica (y)

Ako je y 0

povratak 1

povratak (y * činjenica (y-1)) / * tu se događa rekurzija * /

2) Razdvojite i osvojite algoritam

Ovo je još jedan učinkovit način rješavanja mnogih problema. U algoritmima Divide and Conquer algoritam podijelite na dva dijela, prvi dio problema je podijeljen na manje podprobleme istog tipa. Zatim se u drugom dijelu ti manji problemi rješavaju, a zatim sabiraju (kombiniraju) kako bi se dobilo konačno rješenje problema.

Spajanje i brzo razvrstavanje mogu se izvršiti pomoću algoritama za podjelu i osvajanje. Ovdje je pseudokod algoritma sortiranja sortiranja koji vam daje primjer:

MergeSorting (ar (), l, r)

Ako je r> l

  1. Pronađite sredinu da biste podijelili zadani niz na dvije polovice:

srednja m = (l + r) / 2

  1. Nazovite spajanjeSorting za prvo polugodište:

Nazovite spajanjeSorting (ar, l, m)

  1. Nazovite spajanjeSorting za drugu polovicu:

Nazovite spajanjeSorting (ar, m + 1, r)

  1. Spajanje polovice raspoređenih u koracima 2 i 3:

Spajanje poziva (ar, l, m, r)

3) Algoritam dinamičkog programiranja

Ovi algoritmi funkcioniraju tako što pamte rezultate proteklog pokretanja i koriste ih za pronalaženje novih rezultata. Drugim riječima, algoritam dinamičkog programiranja rješava složene probleme razbijajući ga u više jednostavnih potproblema, a zatim svaki od njih jednom rješava, a zatim ih pohranjuje za buduću upotrebu.

Sekvence Fibonaccije je dobar primjer algoritama za dinamičko programiranje, možete vidjeti kako radi u pseudo kodu:

Fibonaccije (N) = 0 (za n = 0)

= 0 (za n = 1)

= Fibonaccije (N-1) + Finacchi (N-2) (za n> 1)

4) pohlepni algoritam

Ovi se algoritmi koriste za rješavanje problema optimizacije. U ovom algoritmu pronalazimo lokalno optimalno rješenje (bez ikakvih budućih posljedica) i nadamo se da ćemo pronaći optimalno rješenje na globalnoj razini.

Metoda ne garantira da ćemo uspjeti pronaći optimalno rješenje.

Algoritam ima 5 komponenti:

  • Prvi je skup kandidata iz kojeg pokušavamo pronaći rješenje.
  • Funkcija odabira koja pomaže izabrati najboljeg mogućeg kandidata.
  • Funkcija izvedivosti koja pomaže u odlučivanju može li se kandidat koristiti za pronalaženje rješenja.
  • Objektivna funkcija koja dodjeljuje vrijednost mogućem rješenju ili djelomičnom rješenju
  • Rješenje funkcija koja govori kad smo pronašli rješenje problema.

Huffman Coding i Dijkstra algoritam su dva glavna primjera gdje se koristi pohlepni algoritam.

U Huffmanovom kodiranju algoritam prolazi kroz poruku i ovisno o učestalosti znakova u toj poruci za svaki znak dodjeljuje kodiranje promjenjive duljine. Da bismo uradili Huffmanovo kodiranje, prvo moramo napraviti Huffmanovo stablo od ulaznih znakova, a zatim ga proći kroz stablo kako bismo dodijelili kodove znakovima.

5) Algoritam brutalne sile

Ovo je jedan od najjednostavnijih algoritama u konceptu. Algoritam brutalne sile slijepo ponavlja sva moguća rješenja za pretraživanje jednog ili više rješenja koja mogu riješiti funkciju. Smatrajte grubu silu upotrebom svih mogućih kombinacija brojeva da biste otvorili sef.

Evo primjera Sekvencijalne pretrage koja se vrši upotrebom brutalne sile:

Algoritam S_pretraživanje (A (0..n), X)

A (n) ← X

i ← 0

Dok A (i) ≠ X

i ← i + 1

ako se vratim <n

vrati se -1

6) Algoritam povratnog hoda

Povratak unazad tehnika je pronalaska rješenja problema u inkrementalnom pristupu. Probleme rješava rekurzivno i pokušava doći do rješenja problema rješavajući po jedan dio problema. Ako jedno od rješenja ne uspije, uklanjamo ga i uklanjamo drugo kako bismo pronašli drugo rješenje.

Drugim riječima, algoritam povratnog praćenja rješava potproblem i ako ne uspije riješiti problem, poništava posljednji korak i započinje ponovno pronaći rješenje problema.

N Queens problem je dobar primjer za provjeru algoritama za vraćanje unatrag u akciji. Problem N Queen kaže da u šahovskoj ploči ima N komada kraljice i moramo ih organizirati tako da nijedna kraljica ne može napasti nijednu drugu kraljicu u odboru jednom organiziranu.

Sada pogledajmo algoritam SolveNQ i provjeri valjane funkcije za rješavanje problema:

CheckValid (Šahovska ploča, red, stupac)

Početak

Ako je kraljica na lijevoj strani tekućeg stupca, vratite se lažno

Ako je kraljica na gornjoj lijevoj dijagonali, vratite se lažno

Ako je kraljica na donjoj lijevoj dijagonali, vratite se lažno

Povratak istinit

Kraj

SolveNQ (ploča, stupac)

Početak

Ako su svi stupci puni, vratite se istinito

Za svaki red prisutan u šahovskoj ploči

Čini

Ako je, CheckValid (ploča, x, stupac), tada

Postavite kraljicu u ćeliju (x, stupac) na ploči

Ako je SolveNQ (ploča, stupac + 1) = Istina, vratite istinu.

Inače, uklonite kraljicu iz ćelije (x, stupac) s ploče

Sastavljeno

Vratite lažno

Kraj

Zaključak - Vrste algoritama

Algoritmi stoje iza većine dojmljivih stvari koje računala mogu raditi i to su u srži većine računalnih zadataka. Ako budete bolji s algoritmima, ne samo da će vam pomoći da budete uspješan programer, već ćete i postati učinkovitiji.

Preporučeni članci

Ovo je vodič za Vrste algoritama. Ovdje ćemo raspravljati o prvih 6 važnih vrsta algoritama sa njihovim funkcijama. Možete i proći naše druge predložene članke da biste saznali više -

  1. Uvod u algoritam
  2. Algoritam u programiranju
  3. Pitanja o intervjuu za algoritam
  4. Čimbenik u Pythonu | Tehnike
  5. Brzo sortiranje algoritama na Javi
  6. Top 6 algoritma za razvrstavanje u JavaScript