Implementazione dinamica di una funzione definita ricorsivamente (Appello Aprile 2010) Sia data la funzione F così definita : Si richiede di implementare in linguaggio C: Una funzione Fr che calcoli F (n, k); Una funzione Frd che calcoli F (n, k) in O(n2 ); Implementazione ricorsiva La fuzione viene implementata applicando semplicemente la formula di …
Archivio Tag: iterativo
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 04
Ricerca del minimo numero di caratteri da aggiungere a una stringa per renderla palindroma
Ricerca del minimo numero di caratteri da aggiungere a una stringa per renderla palindroma ( Compito del 28 Settembre 2011) Il testo recita: Una stringa e palindroma se non cambia leggendola da destra a sinistra e viceversa. Ad esempio anna e osso sono due palindromi. Risolvere il seguente problema: data una stringa S = {a …
feb 20
Algoritmi sulle permutazioni, articolo in PDF
Ho tratto un articolo dai vari post sugli algoritmi per la generazione di permutazioni. Gli argomenti trattati sono: 1 Algoritmo iterativo per generare permutazioni in ordine lessicografico 2 Algoritmo ricorsivo per generare permutazioni 3 Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter) 4 Determinare una specifica permutazione dall’insieme delle permutazioni 4.1 I Factoradic 4.2 Interpretazione …
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) …