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
- Găsiți punctul de mijloc pentru a împărți tabloul dat în două jumătăți:
mijloc m = (l + r) / 2
- Apelați mergeSortare pentru prima jumătate:
Apelați mergeSorting (ar, l, m)
- Apelați mergeSortare pentru a doua jumătate:
Call mergeSorting (ar, m + 1, r)
- 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 -
- Introducere în Algoritm
- Algoritmul în programare
- Întrebări la interviu Algoritm
- Factorial în Python | Tehnici
- Algoritmi de sortare rapidă în Java
- Top 6 Sortarea algoritmului în JavaScript