©2020-2024 ioDraw All rights reserved,
Privacy Policy
资源限制
时间限制：1.0s 内存限制：128.0MB
题目背景
XJJ最近迷上了一款小游戏——汉诺四塔，但是由于智商有限，步骤多了容易手滑，于是他请求小伙伴们来帮他，人家才不是cheat呢。
游戏规则
同汉诺塔相似，不过塔有4个，要求将盘子从塔1运到塔4。
输入格式
一个数n表示盘子数。
输出格式
第一行输出step表示你的操作步数。
接下来step行每行2个用空格隔开的数a,b表示将塔a最上面的盘子移到塔b。
你的输出只要保证能帮XJJ通关游戏即可，对步数没有太大要求，当然你操作100000步XJJ也会等不及的啦。
数据规模和约定
6<=n<=30；
judge
由于答案不唯一，将用以下方法判断答案是否正确：
·step必须是1到100000以内的整数，a、b必须是1到4的整数，a和b可以相等；
·输出必须有2*step+1个整数，每个步骤可以不换行；
·对于一次操作a,b，必须满足a塔有盘子，且当前状态下a塔最上面的盘子比b塔最上面的盘子(如果有)小，当然b塔没有盘子可以直接移动；
·step次操作完成后，所有的盘子从大到小放在第四个塔上；
· XJJ请教大神得知n=30时，1025步可以通关，瞬间XJJ放心了不少。
思路：动态递归求解方法个数，通过递归打印函数开始迭代
我们已经熟知，汉诺三塔，移动次数为2**n-1；对于此题，可以无视其中一个塔，但总步数为2**30-1，显然以经大于100000，因此要巧妙利用这个根塔，这里就不卖关子了，对于四塔问题，可以将n个盘子分为上下两部分，分别分为p,q个盘子（p+q=n），将p个盘子先移动到一个塔上，这时要注意：盘子是小的必须在大的上。那么刚才剩余的q个盘子只有三个塔作为其移动的载体，即转化为了三塔问题，将其移到最后一个塔上（即4塔），有2**p-1种方法（这个结论想必做这个题的人都知道吧，这里不再阐述），最后再将刚才已经移到一个塔上的p个盘子移到第4塔上，解决问题。
上述分析中，k的确定至关重要，如果p,q随意分的话，得到的总步数不一定是最少的，因此，在每一次迭代中都需要加入循环，遍历分的方法，使用min()函数，找到并提取k的值，由于用的是动态递归（递归的动态规划优化，没听过的可以自己阅读有关资料），则可以将k，和总步数num合并存储在字典memo中，最后编写打印函数，这里要注意承接关系，这里笔者特意在打印函数后加入参数p，q，旨在确定从那个塔移动到那个塔，方便函数内部的递归处理，防止出现混乱。
最后给出源码：读者可以进一步对代码优化
memo={} def f(n): if n in memo: return memo[n][1] if n==1: value=1
memo[n]=[0,value] return value a=[] for k in range(1,n):
a.append(2*f(n-k)+2**k-1) value=min(a) key=a.index(min(a))+1
memo[n]=[key,value] return value n=int(input());f(n)
print(memo[n][1]);s=[1,2,3,4] def print_4(n,p,q): global memo,s,s1 if n==1:
print(str(p)+' '+str(q)) return b=s.copy() b.remove(p);b.remove(q) a=memo[n][0]
#下面的盘数 #先把上面的盘子通过四柱移到2上 print_4(n-a,p,b[0]) s1=[p,q,b[1]] print_3(a,p,q)
print_4(n-a,b[0],q) return def print_3(n,p,q): #p为当前所在列 global s1 if n==1:
print(str(p)+' '+str(q)) return a=s1.copy() a.remove(p);a.remove(q)
print_3(n-1,p,a[0]) print_3(1,p,q) print_3(n-1,a[0],q) return print_4(n,1,4)
本题到这里结束，祝各位对递归、动规理解更上一个档次
下次再见！！！