Con le assegnazioni
- n = numero di dischi
- sorgente = la torre sorgente, dove si trovano i dischi inizialmente
- temp = la torre temporanea, di appoggio
- destinazione = la torre destinazione, dove i dischi devono essere spostati
def hanoi(n, sorgente, temp, destinazione):
if n == 1:
print(sorgente, ">>", destinazione)
else:
hanoi(n-1, sorgente, destinazione, temp )
hanoi(1 , sorgente, temp , destinazione)
hanoi(n-1, temp , sorgente , destinazione)
n=int(input("Quanti dischi? "))
hanoi(n, 1, 2, 3)
Al variare del numero di dischi (1, 2, …, 10, …) come cambia il tempo di esecuzione della funzione?
Contare 1
Conta il numero di spostamenti
conta=0
def hanoi(n, sorgente, temp, destinazione):
global conta
if(n == 1):
conta += 1
# print(...)
else:
hanoi(n-1, sorgente, destinazione, temp )
hanoi(1 , sorgente, temp , destinazione)
hanoi(n-1, temp , sorgente , destinazione)
n=int(input("Quanti dischi? "))
hanoi(n,1,2,3)
print(conta)
Contare 2
Utilizza la funzione time.time() per avere il numero di secondi necessari per l’esecuzione del codice.
Elimina la print() per risparmiare tempo (a mali estremi estremi rimedi…)
import time
def hanoi(n, sorgente, temp, destinazione):
if(n == 1):
pass # non fare niente...
# print(...)
else:
hanoi(n-1, sorgente, destinazione, temp )
hanoi(1 , sorgente, temp , destinazione)
hanoi(n-1, temp , sorgente , destinazione)
n=25
START=time.time() # Orario prima di cominciare
hanoi(n,1,2,3)
STOP=time.time() # Orario dopo aver finito
print(STOP-START) # Tempo trascorso in secondi
Per n > 25 i tempi diventano comunque insostenibili (secondi -> minuti -> ore …)