Passa ai contenuti principali

Torre di Hanoi

Questo problema è sempre molto usato all'¢inizio di un corso d'informatica perchè mette in risalto l'utilità dello studio della complessità di un algoritmo, introduce il metodo ricorsivo per la risoluzione di un problema e in più è anche un bel esercizio mentale.. se ne vuoi sapere di più continua a leggere

Il problema delle Torri di Hanoi è stato posto dal matematico francese Edouard Lucas nel 1883 e deriva da una antica leggenda indiana che recita così: «nel grande tempio di Brahma a Benares, su di un piatto di ottone, sotto la cupola che segna il centro del mondo, si trovano 64 dischi d'oro puro che i monaci spostano uno alla volta infilandoli in un ago di diamanti, seguendo l'immutabile legge di Brahma: nessun disco può essere posato su un altro più piccolo. All'inizio del mondo tutti i 64 dischi erano infilati in un ago e formavano la Torre di Brahma. Il processo di spostamento dei dischi da un ago all'altro è tuttora in corso. Quando l'ultimo disco sarà finalmente piazzato a formare di nuovo la Torre di Brahma in un ago diverso, allora arriverà la fine del mondo e tutto si trasformerà in polvere».
Le regole del gioco sono quindi due e molto semplici:

1) si può spostare solo il disco situato sulla sommità di una torre
2) un disco più grande non può essere posato sopra un disco più piccolo.


Chiamiamo i tre paletti A,B,C e i dischi 1,2,..,n in cui l'etichetta i è anche la dimensione del disco: quindi il disco 1 ha dimensione 1 e in generale disco 1 T(n) = 2T(n-1) +1
Vediamo ora di dimostrare per induzione l'affermazione fatta.
Caso base: n=1 .Abbiamo quindi un solo disco che possiamo spostare tranquillamente T(1)=1
Ipotesi Induttiva: l'affermazione è valida per n-1 dischi
Passo n+1. Per ipotesi induttiva possiamo spostare la pila da A a B e con un passo possiamo spostare il disco n in C. Ora ancora attraverso l'ipotesi induttiva spostiamo la pila n-1 dischi in C risolvendo il problema. Abbiamo quindi per quanto detto
T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1
Abbiamo dimostrato l'affermazione e inoltre abbiamo introdotto un metodo risolutivo che possiamo riscrivere in questo pseudocodice.

hanoi(num_dischi, disco_A, disco_B, disco_C)
if(num_dischi == 1) //caso base
muovi_disco(A,C)
else {
hanoi(num_dischi-1,A,C,B) //sposto in B gli n-1 dischi usando C come appoggio
muovi_disco(A,C) //sposto il disco più grande in C
hanoi(num_dischi-1,B,A,C) //sposto in C gli n-1 dischi usando A come appoggio
}

Risolviamo ora la funzione ricorsiva in maniera esplicita attraverso la tecnica dell'unfolding
T(n) = 2T(n-1)+1 = 2T(2T(n-2)+1)+1 = 2^2*T(n-2)+2+1 = 2^k*T(n-k) + 2^k -1
La somma è una serie geometrica particolare e ricordando che T(1)=1
T(n) = 2^k*2T(n-k) +2^k -1 = 2^(n-1)*2T(1) +2^(n-1) -1 = 2^n -1

Per farci un'idea del tempo che ci vuole per risolvere effettivamente il problema consideriamo che con 64 dischi ci vogliono circa 10^18 operazioni. Se disponiamo di una cpu che fa 1 milione di operazioni al secondo (nel nostro caso spostamenti) ci vogliono 3170 anni. Se invece come i monaci spostano un disco al secondo ci impiegheranno 585 miliardi di anni. La nascita del pianeta Terra risale a circa 4.5 miliardi di anni fa e l'età dell'universo, dal Big Bang a oggi, è stimata sui 15 miliardi di anni: possiamo quindi stare tranquilli ancora per un bel pò.

Post popolari in questo blog

Se excel non aggiorna le formule

Oggi in ufficio è capitata una richiesta particolare. In un documento excel dopo aver eseguito un copia-incolla di una formula non si aggiornavano i risultati nelle celle interessate. Dopo attimi di perplessità dal fondo dell'ufficio il capo ci illumina con una funzione ai più sconosciuta e che ha risolto il problema: il tasto F9. Scusate la mia ignoranza in excel ma questo blog è pensato proprio per appuntare esperienze di vita informatica. Tutto sta nel fatto che i "calcolatori d'un tempo" non disponevano di una adeguata potenza di calcolo e nelle operazioni di copia-incolla si verificavano lunghe attese per l'aggiornamento. La soluzione adottata da MS è stata quella di inserire un'opzione per impedire l'aggiornamento automatico e forzarlo con una combinazione di tasti... il tasto F9!
Combinazioni utili per il calcolo delle formule F9 = calcola le formule modificate dall'ultimo calcolo in tutte le cartelle e fogli di lavoro aperte. MAIUSC + F9 = c…

Dove si trova il mio ISP?

Il link di oggi è My IP Address Lookup. Questo servizio spagnolo mostra dove si trova fisicamente il vostro ISP. Quando vi collegate ad internet in realtà prima fate una richiesta (il vostro modem o router) ad una macchina del vostro ISP e poi vi viene assegnato un indirizzo IP. Se volete sapere dove si trova la macchina che vi permette di accedere alla rete visitate pure
http://www.ip-adress.com/

Potrete inoltre conoscere il vostro IP e il provider che ve lo offre

RaspberryPi: Abilitare l'audio analogico

Introduzione
Il mio raspi è collegato ad una vecchia TV CRT che ho convertito in una smartTV. RaspberryPi infatti è un ottimo prodotto per configurare un media center con connessione ad internet ed altre amenità. Se usate una vecchia TV come nel mio cavo potrebbe interessarvi come abilitare l'uscita analogica per l'audio, il jack da 3,5 mm per intenderci. Per fare ciò dobbiamo assicurarci di avere i moduli giusti del kernel caricati e configurare il raspi ad utilizzare la giusta uscita audio, infatti di default utilizza la porta HDMI.

Controllo della presenza del modulo snd_bcm2835
1 Per controllare che il modulo giusto sia presente da linea di comando eseguire

sudo lsmod | grep snd_bcm2835

2 Se non vedete alcun output vuol dire che il modulo non è ancora caricato altrimenti potete passare al prossimo paragrafo.
3 Proviamo a caricare  il modulo con il seguente comando da terminale

sudo modprobe snd_bcm2835

Se l'output del comando è una cosa del genere

FATAL: Module snd_bcm2835…