首页 > 代码库 > 汉诺塔问题推广【排列组合】

汉诺塔问题推广【排列组合】

已知的汉诺塔问题是这样的:

有三根木棒,第一根木棒上有若干根环,现在要把第一根木棒上的环移动到第三根上去,移动的规则是大的环不能在小的环上面。

现在将其改变一下:

木棒的移动过程中每次只能在相邻的木棒间移动。

问有多少种方法。

其实类似于这样的问题我们可以这样来考虑:

总和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;



汉诺塔问题推广【排列组合】