首页 > 代码库 > 汉诺塔问题推广【排列组合】
汉诺塔问题推广【排列组合】
已知的汉诺塔问题是这样的:
有三根木棒,第一根木棒上有若干根环,现在要把第一根木棒上的环移动到第三根上去,移动的规则是大的环不能在小的环上面。
现在将其改变一下:
木棒的移动过程中每次只能在相邻的木棒间移动。
问有多少种方法。
其实类似于这样的问题我们可以这样来考虑:
总和F(n)
第一步:将第一个棒上的(n-1)个环移动到第三个棒上。--->F(n-1)
第二步:将第一个棒上的最大的那个环移动到第二个棒上。--->1
第三步:将第三个棒上的(n-1)个环移动到第一个棒上。 --->F(n-1)
第四步:将第二个棒上的那个最大的环移动到第三个帮上。--->1
第五步:将第一个棒上的(n-1)个环移动到第三个棒上。 --->F(n-1)
F(n)=3*F(n-1)+2; F(1)=2;
故F(n)=3^n-1;
现在来个一个n层高的汉诺塔涂颜色,有蓝,红,黄三种颜色,每两层不能是连续的蓝色。
问一共有多少种方法。
dp[n][0]表示第n层涂蓝色有多少种方法。
dp[n][1]表示第n层不涂蓝色有多少种方法。
若第n-1层是蓝色,则第n层一定不能是蓝色。 dp[n][0] = dp[n-1][1]
若第n-1层不是蓝色(红色或者黄色),则第n层可以是任何颜色。dp[n][1] = 2 * ( dp[n-1][1] + dp[n-1][0] )
dp[1][1]=2, dp[1][0]=1;
汉诺塔问题推广【排列组合】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。