Torre di Hanoi – Programmare con Python

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