递归算法专题一＞汉诺塔问题

用户11305962

发布于 2024-11-21 16:47:09

4150

文章被收录于专栏：学习学习

题目：

方法一：不讲武德法，注意：面试不能用！！

代码：

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        //不讲伍德方法
        for(int x : A) C.add(x); 
    }

方法二：

1.为什么可以用递归？

先看汉诺塔如果解决：

从图中看出：

处理N（盘子数）为1时候，其他数量少的情况比如 N=2，都可以由 N=1 的方式得来，就好像套娃：这个N=3 问题可以分为，N=2来解决。

为什么可以用递归总结：

大问题-->相同类型子问题

子问题-->相同类型子问题;

大问题：把全部盘子借助B移动到C

子问题：把n-1个盘子，借助任何一个盘子移动到C(往复操作)

2.怎样用递归：

首先要从宏观方面考虑，这个递归函数可以为我解决问题，不用纠结。

其次就是设计递归函数：

步骤一设计函数头：

找出重复子问题：这里X,Y,Z分别对应，A,B,C三个柱子，n盘子个数

void dfs(x, y, z,int n)

步骤二：设计函数体： 只要关心某个子问题在做什么即可，就是图中的(1,2,3)。

dfs(x,z,y,n-1); //借助中间的z柱子，把x柱子上的n-1个盘子放到，y柱子上

z.add(x.remove(x.size()-1)); //把x柱子的第一个剩下的盘子，放到z柱子

dfs(y,x,z,n-1); //借助X柱子，把y柱子上的n-1个盘子，放到z柱子上

步骤三：

找递归出口: 这里就是，N==1时，把x柱子的第一个的盘子，直接放到z柱子

代码：

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    private void dfs(List<Integer> x, List<Integer> y, List<Integer> z,int n){
        //递归出口,只有一个盘子的时候，把x柱子上的盘子直接放到z柱子上
        if(n == 1) {
            z.add(x.remove(x.size()-1));
            return;
        }

        //任意一个子问题的具体步骤
        dfs(x,z,y,n-1);//借助中间的z柱子，把x柱子上的n-1个盘子放到，y柱子上
        z.add(x.remove(x.size()-1));//把x柱子的第一个剩下的盘子，放到z柱子
        dfs(y,x,z,n-1);//借助X柱子，把y柱子上的n-1个盘子，放到z柱子上
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除

设计