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…

Riflessioni sull'ordinamento

Gli algoritmi di ordinamento sono da sempre i più gettonati e interessanti dal punto di vista didattico (si veda la complessità computazionale) e funzionale (quasi tutti i programmi hanno almeno una funzione di ricerca). Proprio di questi giorni sono alcuni articoli di Programmazione.it dedicati a questo tema (link).Coding Horror in questo articolo presenta una provocazione molto interessante al di là delle opinioni personali:

The default sort functions in almost every programming language are poorly
suited for human consumption.
L'articolo pone l'attenzione sulla differenza tra l'ordinamento alfanumerico e quello ASCII solitamente usato nei metodi nativi dei linguaggi. Il discorso si ampia se poi pensiamo banalmente alla differenza tra Windows e GNU/Linux che è case sensitive.
Spesso i sistemi operativi e i linguaggi di programmazione realizzano ordinamenti rispettando l'ordine della tabella di codifica ASCII e non l'ordinamento naturale della lingua. I commenti a se…

Timeline dei Linguaggi di programmazione

O'Reilly ha reso disponibile per tutti gli appassionati un interessante poster in formato pdf in cui vengono riassunti 50 anni di storia dei linguaggi di programmazione.Il poster mostra una timeline colorata nella quale sono evidenziate le principali derivazioni tra i vari linguaggi... da vedere
http://www.oreilly.com/news/graphics/prog_lang_poster.pdf



fonte programmazione.it