Il problema delle 8 regine parte 2, un approccio iterativo In questo articolo ci proponiamo di riscrivere l’algoritmo descritto nel precedente in modo da renderlo completamente iterativo, questo problema è un caso particolare di un problema ricorrente nell’ottimizzazione del software, si tratta di rendere iterativo un algoritmo “intrinsecamente” ricorsivo. Quando un problema è definibile per …
Archivio Tag: algoritmi numerici
feb 06
Determinare la lunghezza della più lunga sottostringa palindroma
Determinare la lunghezza della più lunga sottostringa palindroma ( Appello Aprile 2010) Il testo recita: Data una stringa S = a1 a2 . . . an di n caratteri, si propone il problema di determinare la lunghezza della più lunga palindroma sottostringa di S. Suggerimento: per la risoluzione: Sia l[i, j] la lunghezza della più …
feb 18
Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)
L’algoritmo degli scambi semplici è l’algoritmo più efficiente per generare permutazioni, le permutazioni vengono generate con un singolo scambio, quindi costituiscono un codice Gray. L’algoritmo è stato ideato nel diciassettesimo secolo in Inghilterra da parte di alcuni suonatori di campane che avevano sviluppato il buffo passatempo di suonare le campane secondo tutte le permutazioni possibili. …
set 24
Ricavare il numero di una permutazione (ranking)
questo articolo è la continuazione del articolo sulla determinazione di una specifica permutazione e affronta il problema inverso: determinare la posizione di una specifica permutazione nell’insieme delle permutazioni ordinate lessicograficamente. Ancora qualcosa sull’interpretazione dei codici di Lehmer I singoli termini del codice di Lehmer si possono anche interpretare come il numero di elementi che si …
set 19
Determinare una specifica permutazione dall’insieme delle permutazioni
questo articolo è la continuazione del articolo precedente sulle permutazioni. Potrebbe essere necessario determinare una singola permutazione dall’insieme delle permutazioni ordinate e inutile determinarle tutte. Come si affronta questo problema? ogni informatico sano di mente scarterebbe nel giro di un paio di secondi la possibilità di generare tutte le permutazioni fino a quella cercata (ma …
giu 30
Un semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi
L’algoritmo seguente è probabilmente il più semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi, l’algoritmo analizza semplicemente la permutazione attuale per ricavarne la prossima basandosi sul fatto che le permutazioni devono seguire un ordinamento lessicografico (nel caso numerico qui analizzato ogni permutazione deve essere la minima permutazione maggiore di quella corrente) …