问题

有A、B、C、D四根柱子，在A柱子上有n个圆盘从小到大放置。请设计一下时间复杂度低的算法，把A柱子上的圆盘移动到D柱子上，移动过程遵循汉诺塔移动规则。编程实现。

分析

相对于经典的三柱汉诺塔，这个问题多了一根柱子，移动多了一个选择。

设四柱移动的时候为f(x)，三柱移动的时候为g(x)。在n个圆盘中选取j个以f(j)的方式首先从a移动到b上，然后省下的n-j个以g(n-j)的方式从a移动到d,最后将b上的j个原盘以f(j)从b移动到d。

所以易得出：sum = 2*f(j) + g(n-j)

再来看看三柱的问题，三柱的时候先把a上的n-1移动到b上，然后把剩下的一个移动到c上，最后把b上的移动到c上。

可得式子：g(x) = 2*g(x-1) + 1

经过实际计算验证是成立的。

代码

# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 22:00:39 2020

@author: 021717139 clh
"""

def count(n):
    Three = {} #三根柱子移动的次数情况
    Four = {} #四根柱子移动的次数情况
    Cut = {} #切割的位置
    Three[1] = 1
    for i in range(2,n+1):
        Three[i] = 2*Three[i-1] + 1  #三根柱子移动的次数关系
    Four[1] = 1
    Four[2] = 3
    Cut[1] = 0
    Cut[2] = 0
    for i in range(3,n+1):
        min = Three[i] #设最小值的初值为Three[i]
        for j in range(1,i):
            sum = 2*Four[j] + Three[i - j] #先以Four[j]移动j个，再Three[i-j]移动一次，最后Four[j]一次
            if min > sum:
                min = sum
                m = j
            Four[i] = min
            Cut[i] = m
    return(Four[n],Cut)
        
def moveall(n,a,d,c,b,cut): #将a上的移到d上
    j = cut[n]
    if n > 0:
        moveall(j,a,b,d,c,cut) #将a上的j个移到b上
        movethree(n-j,a,d,c) #将a上的n-j个以三根的方式移到d上
        moveall(j,b,d,a,c,cut) #将b上的移到d上

def movethree(n,a,c,d): #将a上的移到c上
    if n > 0:
        movethree(n-1,a,d,c) #将n-1个从a先移到d上
        move(n,a,c) #移动最后一个到c
        movethree(n-1,d,c,a) #将n-1个从d移动到c上
          
def move(n,a,c):
    print(a + '>' + c)

        
if __name__ == '__main__':
    num = int(input('请输入一个大于0的正整数:'))
    count,cut = count(num)
    a = 'a'
    b = 'b'
    c = 'c'
    d = 'd'
    Cut = [0]
    for i in range(1,num+1):
        Cut.append(cut[i])
    moveall(num,a,d,c,b,Cut)
    print('移动次数为%d'%(count))