陈斌老师《数据结构与算法Python版》第五周作业——四柱汉诺塔
陈斌老师《数据结构与算法Python版》第五周作业——四柱汉诺塔1 题目2 思路3 程序如下4 总结
1 题目
作者：FJ_qiao
题目内容：
如课上所说，汉诺塔问题源于印度一个古老传说。对于原始的汉诺塔游戏，可供玩家操作的空间一共只有三根柱子，导致按原传说的要求，需要超过1.8*10^19步才能解开。
透过新增柱子可以大幅度地减少需要的步数。此处要求在给出指定的盘数，柱子数量为4（即限制为4根柱子）且不改变原有传说的其他规则的限制下，找出完成迁移的最小步骤数。
输入格式:
一个非负整数M，M代表盘数，M<=1000。
输出格式：
一个非负整数，表示完成迁移的最小步骤数。
输入样例：
3
输出样例：
5
时间限制：500ms内存限制：32000kb
2 思路参考了一下别人的解法
首先三柱汉诺塔问题的最优解次数g(n) = 2^n -1（已经证明），设四柱汉诺塔问题 的最优解次数为f(n)。
接着将四柱汉诺塔问题分为三步来解，设有a,b,c,d四个柱子，a柱子上有n个盘子：
1.将a柱上的 x个盘子(1<= x < n)，移动到c柱上，这个过程可以使用b柱和d柱，所以这是一个四柱汉诺塔问题，最优次数为f(x)。
2.将a柱上剩下的n-x个盘子移动到d柱，因为剩下的盘子都比c柱上现有的盘子多，所以只能通过b柱来移动，这是一个三柱汉诺塔问题，最优次数为 2^(n-x) - 1。
3.最后将c柱上的x个盘子移动到d柱即可，可以通过a，b柱来移动，所以是一个四柱汉诺塔问题，和第一步相同最优次数为f(x)。
所以四柱汉诺塔问题需要的总次数f(n) = f(x) + 2^(n-x) - 1 + f(x) =2* f(x) + 2^(n-x) -1,最优次数与x的取值有关，易求得 f(1) = 1；f(2) = 3, 可以用循环遍历来找f(n)的最小值。
def hnt_4(num):
if num == 0:
return 0
f_list = [1, 3] #已知 f(1) = 1；f(2) = 3
for i in range(2, num): #从f(3) 开始找最优解
ans_list = []
for j in range(i): #f(n) 与 x 的取值有关，所以遍历x
ans_list.append(2*f_list[j]+2**(i-j)-1) #将每个结果加入到一个空列表
f_list.append(min(ans_list)) #将结果里的最小值加入到f_list，这就是每一个f(n) 对应的最小值，后面可以直接使用
return f_list[num-1]
print(hnt_4(int(input()))) #输入
4 总结
这是一个用递归方法的程序，思路同上
def hnt_4(num1):
ans = []
global ans_list
ans_list = [1, 3]
if num1-1 > len(ans_list):
hnt_4(num1 -1 )
else:
pass
for i in range(1, num1):
ans.append(2 * ans_list[i-1] + 2 ** (num1 - i) - 1)
ans_list.append(min(ans))
return ans_list
print(hnt_4(int(input())))
学习陈斌老师的数据结构与算法Python版课有感
作者：FJ_qiao
