Introduzione agli algoritmi
Un algoritmo è una sequenza di passaggi che descrivono come risolvere un problema. Ogni programma per computer che termina con un risultato si basa sostanzialmente su un algoritmo. Gli algoritmi, tuttavia, non sono limitati all'utilizzo nei programmi per computer, ma possono anche essere utilizzati per risolvere problemi matematici e su molte questioni della vita quotidiana. In base al loro funzionamento, possiamo dividere gli algoritmi in più tipi. Diamo un'occhiata ad alcuni di quelli importanti.
Tipi di algoritmo
Esistono molti tipi di algoritmi, ma i tipi fondamentali di algoritmi sono:
1) Algoritmo ricorsivo
Questo è uno degli algoritmi più interessanti in quanto si chiama con un valore inferiore come input che ottiene dopo aver risolto gli input correnti. In parole più semplici, è un algoritmo che si chiama ripetutamente fino a quando il problema non viene risolto.
Problemi come la Torre di Hanoi o il DFS di un grafico possono essere facilmente risolti usando questi algoritmi.
Ad esempio, ecco un codice che trova un fattoriale usando un algoritmo di ricorsione:
Infatti (y)
Se y è 0
ritorno 1
return (y * Fact (y-1)) / * questo è dove si verifica la ricorsione * /
2) Dividi e conquista l'algoritmo
Questo è un altro modo efficace per risolvere molti problemi. Negli algoritmi Divide and Conquer, dividi l'algoritmo in due parti, le prime parti dividono il problema a portata di mano in sottoproblemi più piccoli dello stesso tipo. Quindi, nella seconda parte, questi piccoli problemi vengono risolti e quindi sommati (combinati) per produrre la soluzione finale del problema.
Unire l'ordinamento e l'ordinamento rapido può essere fatto con gli algoritmi di divisione e conquista. Ecco lo pseudocodice dell'algoritmo di ordinamento unione per darvi un esempio:
MergeSorting (ar (), l, r)
Se r> l
- Trova il punto medio per dividere l'array dato in due metà:
medio m = (l + r) / 2
- Chiama mergeSorting per la prima metà:
Call mergeSorting (ar, l, m)
- Chiama mergeSorting per la seconda metà:
Call mergeSorting (ar, m + 1, r)
- Unisci le metà ordinate nei passaggi 2 e 3:
Unisci chiamata (ar, l, m, r)
3) Algoritmo di programmazione dinamica
Questi algoritmi funzionano ricordando i risultati della corsa passata e utilizzandoli per trovare nuovi risultati. In altre parole, l'algoritmo di programmazione dinamica risolve problemi complessi suddividendolo in più sottoproblemi semplici e quindi risolve ciascuno di essi una volta e li memorizza per un uso futuro.
La sequenza di Fibonacci è un buon esempio per gli algoritmi di programmazione dinamica, puoi vederlo funzionare nello pseudo codice:
Fibonacci (N) = 0 (per n = 0)
= 0 (per n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (per n> 1)
4) Algoritmo goloso
Questi algoritmi vengono utilizzati per risolvere i problemi di ottimizzazione. In questo algoritmo, troviamo una soluzione localmente ottimale (senza alcuna considerazione per le conseguenze future) e speriamo di trovare la soluzione ottimale a livello globale.
Il metodo non garantisce che saremo in grado di trovare una soluzione ottimale.
L'algoritmo ha 5 componenti:
- Il primo è un set di candidati dal quale proviamo a trovare una soluzione.
- Una funzione di selezione che aiuta a scegliere il miglior candidato possibile.
- Una funzione di fattibilità che aiuta a decidere se il candidato può essere utilizzato per trovare una soluzione.
- Una funzione oggettiva che assegna valore a una possibile soluzione o a una soluzione parziale
- Funzione di soluzione che indica quando abbiamo trovato una soluzione al problema.
Huffman Coding e l'algoritmo di Dijkstra sono due esempi principali di utilizzo dell'algoritmo Greedy.
Nella codifica di Huffman, l'algoritmo passa attraverso un messaggio e, a seconda della frequenza dei caratteri in quel messaggio, ad ogni carattere assegna una codifica di lunghezza variabile. Per eseguire la codifica Huffman, dobbiamo prima costruire un albero Huffman dai caratteri di input e quindi attraversare l'albero per assegnare i codici ai personaggi.
5) Algoritmo della forza bruta
Questo è uno degli algoritmi più semplici del concetto. Un algoritmo di forza bruta itera ciecamente tutte le possibili soluzioni per cercare una o più di una soluzione che possa risolvere una funzione. Pensa alla forza bruta come all'uso di tutte le possibili combinazioni di numeri per aprire una cassaforte.
Ecco un esempio di ricerca sequenziale fatta usando la forza bruta:
Algoritmo S_Search (A (0..n), X)
A (n) ← X
i ← 0
Mentre A (i) ≠ X fa
i ← i + 1
se ritorno <i
altrimenti restituisce -1
6) Algoritmo di backtracking
Il backtracking è una tecnica per trovare una soluzione a un problema in un approccio incrementale. Risolve i problemi in modo ricorsivo e cerca di ottenere una soluzione a un problema risolvendo un pezzo del problema alla volta. Se una delle soluzioni fallisce, la rimuoviamo e torniamo indietro per trovare un'altra soluzione.
In altre parole, un algoritmo di backtracking risolve un sottoproblema e se non riesce a risolvere il problema, annulla l'ultimo passaggio e ricomincia a trovare la soluzione al problema.
Il problema N Queens è un buon esempio per vedere l'algoritmo di Backtracking in azione. Il problema N Queen afferma che ci sono N pezzi di Queens in una scacchiera e dobbiamo sistemarli in modo che nessuna regina possa attaccare qualsiasi altra regina nel board una volta organizzata.
Ora diamo un'occhiata all'algoritmo SolveNQ e alle funzioni Check Valid per risolvere il problema:
CheckValid (scacchiera, riga, colonna)
Inizio
Se è presente una regina a sinistra della colonna corrente, restituisce false
Se la regina è nella diagonale in alto a sinistra, restituisce false
Se la regina è in diagonale in basso a sinistra, restituisce false
Ritorna vero
Fine
SolveNQ (scheda, colonna)
Inizio
Se tutte le colonne sono piene, restituisce true
Per ogni riga presente nella scacchiera
Fare
Se, CheckValid (scheda, x, colonna), quindi
Imposta la regina nella cella (x, colonna) sul tabellone
Se SolveNQ (scheda, colonna + 1) = True, restituisce true.
Altrimenti, rimuovi la regina dalla cella (x, colonna) dalla scheda
Fatto
Restituisci falso
Fine
Conclusione - Tipi di algoritmi
Gli algoritmi sono alla base della maggior parte delle cose impressionanti che i computer possono fare e questi sono al centro della maggior parte delle attività di elaborazione. Essere migliori con gli algoritmi non solo ti aiuterà ad essere un programmatore di successo, ma diventerai anche più efficiente.
Articoli consigliati
Questa è stata una guida ai tipi di algoritmi. Qui discutiamo i primi 6 importanti tipi di algoritmi con le loro funzioni. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -
- Introduzione all'algoritmo
- Algoritmo in programmazione
- Algorithm Interview Questions
- Fattoriale in Python | tecniche
- Algoritmi di ordinamento rapido in Java
- I 6 migliori algoritmi di ordinamento in JavaScript