递推法证明汉诺塔问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了递推法证明汉诺塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、递推公式

首先给出汉诺塔递推法的公式：f(n)=f(n-1)*2+1
同时我们知道，如果只有一个盘片要移动的话只需移动一次，即f(1)=1为初始条件。
综上递推公式为：汉诺塔公式推导,java,c/c++,经验分享,算法,动态规划

2、证明

假设，现有A，B，C三个柱子可用于存放盘子，并设将n个盘片从A柱移往C柱要使用f(n)次移动。
基于上述假设，我们可以知道要想将n个盘片从A柱移往C柱，等价于先将前n-1个盘有序的叠放在B柱这个辅助柱上，此时移动的次数为移动前n-1个盘的次数，即f(n-1)；接着将A柱上最大的一个盘移到C柱，移动次数为一次，即1；最后在将辅助柱B上的n-1个盘片通过A柱来做辅助柱移动到C柱，此时移动次数为f(n-1)。
综上所述将A柱上的n个盘片通过B柱作为辅助柱移动到C柱上的所有次数为f(n)=2*f(n-1)+1。

3、代码

package com.example.algorithms;

/**
 * 采用动态规划算法解决汉诺塔问题
 * @author LuoXianchao
 * @since 2023/3/2 10:59
 */
public class Test07 {
    public static void main(String[] args) {
        int n = 10;//n表示有几个盘片
        //开辟一块空间，这里用n+1个空间，索引为0的没用到，索引为i表示dp存储i片盘的移动次数
        int[] dp = new int[n + 1];
        dp[1] = 1;//设初值
        //i小于n的解全部算出来，最终得到n的解
        for (int i = 2; i <= n; i++;) { //设2为开始求解的问题
            dp[i] = 2 * dp[i - 1] + 1;//递推公式 
        }
        //输出结果
        for (int index = 1; index < dp.length; index++) {
            System.out.println(index + "片盘移动的次数为：" + dp[index]);
        }
    }
}