Tipuri de algoritmi - Aflați Top 6 Tipuri importante de algoritmi

Cuprins:

Anonim

Introducere în algoritmi

Un algoritm este o succesiune de pași care descriu modul în care o problemă poate fi rezolvată. Fiecare program de computer care se încheie cu un rezultat se bazează practic pe un algoritm. Algoritmii, însă, nu se limitează doar la utilizarea programelor de calculator, acestea pot fi folosite și pentru rezolvarea problemelor matematice și a multor probleme din viața de zi cu zi. Pe baza funcționării lor, putem împărți algoritmii în mai multe tipuri. Să aruncăm o privire la unele dintre cele importante.

Tipuri de algoritm

Există multe tipuri de algoritmi, dar tipurile fundamentale de algoritmi sunt:

1) Algoritm recurent

Acesta este unul dintre cei mai interesanți algoritmi, deoarece se numește cu o valoare mai mică ca intrări pe care le primește după rezolvarea intrărilor curente. Cu alte cuvinte mai simple, este un algoritm care se numește în mod repetat până la rezolvarea problemei.

Probleme precum Turnul Hanoiului sau DFS ale unui grafic pot fi rezolvate cu ușurință folosind acești algoritmi.

De exemplu, aici este un cod care găsește un factorial folosind un algoritm de recursiune:

Fapt (y)

Dacă y este 0

întoarcerea 1

return (y * Fact (y-1)) / * aici se întâmplă recursiunea * /

2) Împărțiți și cuceriți algoritmul

Acesta este un alt mod eficient de rezolvare a multor probleme. În algoritmii Divide și Conquer, împărțiți algoritmul în două părți, primele părți împart problema pe mână în subprobleme mai mici de același tip. Apoi, în a doua parte, aceste probleme mai mici sunt rezolvate și apoi adăugate împreună (combinate) pentru a produce soluția finală a problemei.

Sortarea și sortarea rapidă se pot face cu algoritmi de împărțire și cucerire. Iată pseudocodul algoritmului de sortare a îmbinărilor pentru a vă oferi un exemplu:

MergeSorting (ar (), l, r)

Dacă r> l

  1. Găsiți punctul de mijloc pentru a împărți tabloul dat în două jumătăți:

mijloc m = (l + r) / 2

  1. Apelați mergeSortare pentru prima jumătate:

Apelați mergeSorting (ar, l, m)

  1. Apelați mergeSortare pentru a doua jumătate:

Call mergeSorting (ar, m + 1, r)

  1. Combinați jumătățile sortate în etapele 2 și 3:

Fuziune apel (ar, l, m, r)

3) Algoritmul de programare dinamică

Acești algoritmi funcționează prin amintirea rezultatelor derulării anterioare și folosirea lor pentru a găsi rezultate noi. Cu alte cuvinte, algoritmul de programare dinamic rezolvă problemele complexe, împărțindu-l în mai multe subprobleme simple și apoi le rezolvă pe fiecare dintre ele și apoi le stochează pentru utilizare viitoare.

Secvența Fibonacci este un exemplu bun pentru algoritmii de programare dinamică, îl puteți vedea funcționând în pseudo-cod:

Fibonacci (N) = 0 (pentru n = 0)

= 0 (pentru n = 1)

= Fibonacci (N-1) + Finacchi (N-2) (pentru n> 1)

4) Algoritmul lacom

Acești algoritmi sunt folosiți pentru rezolvarea problemelor de optimizare. În acest algoritm, găsim o soluție optimă local (fără a se ține cont de nicio consecință în viitor) și sperăm să găsim soluția optimă la nivel global.

Metoda nu garantează că vom putea găsi o soluție optimă.

Algoritmul are 5 componente:

  • Primul este un set de candidați din care încercăm să găsim o soluție.
  • O funcție de selecție care ajută la alegerea celui mai bun candidat posibil.
  • O funcție de fezabilitate care ajută la luarea deciziei dacă candidatul poate fi folosit pentru a găsi o soluție.
  • Funcție obiectivă care atribuie valoare unei soluții posibile sau unei soluții parțiale
  • Funcție de soluție care spune când am găsit o soluție la problemă.

Huffman Coding și algoritmul lui Dijkstra sunt două exemple principale în care este folosit algoritmul Greedy.

În codificarea Huffman, algoritmul parcurge un mesaj și în funcție de frecvența caracterelor din mesajul respectiv, pentru fiecare personaj, acesta atribuie o codificare de lungime variabilă. Pentru a face codarea Huffman, mai întâi trebuie să construim un arbore Huffman din caracterele de intrare și apoi să traversăm arborele pentru a atribui coduri caracterelor.

5) Algoritmul forței brute

Acesta este unul dintre cei mai simpli algoritmi din concept. Un algoritm de forță brută itera orbește toate soluțiile posibile pentru a căuta una sau mai multe soluții care pot rezolva o funcție. Gândiți-vă la forța brută ca folosind toate combinațiile posibile de numere pentru a deschide un seif.

Iată un exemplu de Căutare secvențială efectuată cu ajutorul forței brute:

Algoritmul S_Search (A (0..n), X)

A (n) ← X

i ← 0

În timp ce A (i) ≠ X face

i ← i + 1

dacă i <n retur i

altfel se întoarce -1

6) Algoritmul de backtracking

Backtracking este o tehnică pentru a găsi o soluție la o problemă într-o abordare incrementală. Rezolvă problemele recursiv și încearcă să ajungă la o soluție la o problemă prin rezolvarea unei bucăți a problemei simultan. Dacă una dintre soluții nu reușește, o eliminăm și facem backtrack pentru a găsi o altă soluție.

Cu alte cuvinte, un algoritm de backtracking rezolvă un subproblem și dacă nu reușește să rezolve problema, anulează ultimul pas și începe din nou să găsească soluția problemei.

Problema N Queens este un exemplu bun pentru a vedea algoritmul Backtracking în acțiune. Problema N Regina afirmă că există N bucăți de regine într-o tablă de șah și trebuie să le aranjăm astfel încât nicio regină să nu poată ataca nici o altă regină în tabla o dată organizată.

Acum să aruncăm o privire la algoritmul SolveNQ și funcțiile Check Valid pentru a rezolva problema:

CheckValid (tablă de șah, rând, coloană)

start

Dacă există o regină din stânga coloanei curente, atunci întoarceți fals

Dacă regina se află în diagonala din stânga sus, atunci întoarceți fals

Dacă regina se află în diagonala din stânga-jos, atunci întoarceți-vă fals

Întoarce-te adevărat

Sfârșit

SolveNQ (tablă, coloană)

start

Dacă toate coloanele sunt pline, atunci returnează true

Pentru fiecare rând prezent în tabloul de șah

Do

Dacă, CheckValid (placă, x, coloană), atunci

Setați regina la celula (x, coloana) de pe tablă

Dacă SolveNQ (placă, coloană + 1) = True, atunci returnează true.

În rest, scoateți regina din celulă (x, coloană) de pe bord

Terminat

Returnare falsă

Sfârșit

Concluzie - Tipuri de algoritmi

Algoritmii se află în spatele celor mai multe lucruri impresionante pe care le pot face calculatoarele, iar acestea sunt nucleul majorității sarcinilor de calcul. A fi mai bun cu algoritmi nu numai că te va ajuta să fii un programator de succes, dar vei deveni și mai eficient.

Articole recomandate

Acesta a fost un ghid pentru Tipuri de Algoritmi. Aici discutăm Top 6 Tipuri importante de algoritmi cu funcțiile lor. Puteți parcurge și alte articole sugerate pentru a afla mai multe -

  1. Introducere în Algoritm
  2. Algoritmul în programare
  3. Întrebări la interviu Algoritm
  4. Factorial în Python | Tehnici
  5. Algoritmi de sortare rapidă în Java
  6. Top 6 Sortarea algoritmului în JavaScript