河內塔不使用堆疊的非遞迴版本

hanoi_no_stack_no_recursion.py

def is_even(n):
    return n % 2 == 0
    
def which_disk(n):
    c = n ^ (n + 1)
    i = 0
    while c != 0:
        c = c >> 1
        i = i + 1
    return i

def hanoi(n):
    number_of_moves = 2 ** n - 1
    dir = [1, 0] if is_even(n) else [0, 1]
    pin = [1] * number_of_moves
    
    for i in range(0, number_of_moves):
        disk = which_disk(i)
        p_idx, d_idx = disk - 1, disk & 1
        next = (pin[p_idx] + dir[d_idx]) % 3 + 1
        print(pin[p_idx], next)
        pin[p_idx] = next

hanoi(4)
    

ｎｉｃｅ