Archivio Tag: algoritmica

mag 23

Il problema delle 8 regine parte 2, un approccio iterativo

6952100115_de8c56ecd8_h

Questo post è comparso inizialmente nel blog di Fabrizio Mondo qualche anno fa. In seguito Fabrizio ha deciso di rendere il blog tematico e il post è rimasto disperso nel cyberspazio come“Un fiocco di neve che non cade in nessun posto.”(cit.). Adesso ho deciso di correggere qualcosa e ri-pubblicarlo. Il problema delle 8 regine parte …

Continua a leggere »

Share Button

feb 13

Implementazione dinamica di una funzione definita ricorsivamente

Aprile2010_html_748e8883

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 …

Continua a leggere »

Share Button

feb 09

Contare le coppie adiacenti in una sequenza in tempo nLog(n)

AlberoCoppie

Contare le coppie adiacenti in una sequenza in tempo nLog(n) (Appello Settembre 2010) il testo recita: Sia data una sequenza di interi a1 , a2 , . . . , an . Diciamo che la sequenza contiene una coppia di numeri consecutivi se esistono due interi ai e aj tali che ai = aj + …

Continua a leggere »

Share Button

feb 06

Determinare la lunghezza della più lunga sottostringa palindroma

Aprile2010_2_html_121ea231

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ù …

Continua a leggere »

Share Button

feb 04

Ricerca del minimo numero di caratteri da aggiungere a una stringa per renderla palindroma

Settembre2011_htm_m24a9b38b

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 …

Continua a leggere »

Share Button

feb 18

Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)

Esecuzione dell'algoritmo degli scambi semplici su un insieme di 4 elementi

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. …

Continua a leggere »

Share Button

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 …

Continua a leggere »

Share Button

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 …

Continua a leggere »

Share Button

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) …

Continua a leggere »

Share Button