【韩顺平Java笔记】第7章：面向对象编程(基础部分)【214-226】

🕗 发布于 2024-10-05 07:43 java 笔记 开发语言

文章目录

214. 递归解决什么问题
215. 递归执行机制1
216. 递归执行机制2
217 递归执行机制3
217.1 阶乘
218. 递归执行机制4
219. 斐波那契数列
220. 猴子吃桃
221. 222. 223. 224. 老鼠出迷宫1,2,3,4
- 224.1 什么是回溯
225. 汉诺塔
226. 八皇后

214. 递归解决什么问题

简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂问题,同时可以让代码变得简洁
递归能解决的问题：

215. 递归执行机制1

public class TestUse {
    public static void main(String[] args) {
        T t1 = new T();
        t1.test(4);
    }
}
class T{
    //分析
    public void test(int n){
        if(n > 2){
            test(n-1);
        }
        System.out.println("n=" + n);
    }
}

运行结果：
n=2
n=3
n=4
函数调用栈过程：

【注】每一个栈都会完整的执行方法，在哪里调用就在哪里返回。

216. 递归执行机制2

将上一节课的代码的if条件假如else如下

public void test(int n){
        if(n > 2){
            test(n-1);
        }
        else{
            System.out.println("n=" + n);
        }
    }

就变成结果只有
n=2
其函数调用栈相当于下图：

217 递归执行机制3

217.1 阶乘

public class TestUse {
    public static void main(String[] args) {
        T t1 = new T();
        int res = t1.factorial(5);
        System.out.println("5 的阶乘 res =" + res);
    }
}
class T{
    //分析
    public void test(int n){
        if(n > 2){
            test(n-1);
        }
        else{
            System.out.println("n=" + n);
        }
    }
    //factorial
    public int factorial(int n){
        if(n == 1){
            return 1;
        }else{
            return factorial(n-1)*n;
        }
    }
}

运行结果：
5 的阶乘 res =120

218. 递归执行机制4

219. 斐波那契数列

请使用递归的方式求出斐波那契数1,1,2,3,5,8,13…给你一个整数 $n$ ，求出它的值是多少

public class TestUse {
    public static void main(String[] args) {
        T t1 = new T();
        int n = 7;
        int res = t1.fib(n);
        if(res != -1) {
        System.out.println("当 n="+ n +" 对应的斐波那契数=" + res);
        }
    }
}
class T{
    //Fib数列
    public int fib(int n){
        //n小于等于0，提示数据不合法退出
        if(n <= 0){
            System.out.println("数据不合法！");
            return -1;
        }
        //第1项和第2项都是1，
        //第3项开始
        //fib(n) = fib(n-1) + fib(n-2)
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib(n-1) + fib(n-2);
        }
    }
}

运行结果：
当 n=7 对应的斐波那契数=13

220. 猴子吃桃

猴子吃桃子问题：有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个，以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时（即还没吃），发现只有1个桃子了。问题：最初共多少个桃子？（我以前写过一个循环的版本，现在用递归写，看来有些数据要写死了，比如第10天就得固定下来）

public class TestUse {
    public static void main(String[] args) {
        T t1 = new T();
        //桃子问题
        int day = 1;
        int peachNum = t1.func(day);
        if(peachNum != -1) {
        System.out.println("第 " + day + "天有" + peachNum + "个桃子");
        }
    }
}
class T{
    //求解猴子吃桃问题
    //设func(day)表示day天吃桃子前的桃子数量
    //day当天吃掉了func(day) / 2 + 1
    //day当天还剩下func(day) - (func(day) / 2 + 1)=func(day) / 2 - 1
    //则func(day) = (当天剩下的 + 1)*2
    //day = 10，剩下1个桃子，func(10) = (1 + 1) * 2
    //dat = 9，剩下4个桃子，func(9) = (4 + 1) * 2
    //day = 8，剩下10个桃子，func(8) = (10 + 1) * 2
    //得出公式，func(day) = (当天剩下的（即下一天的桃子总数func(day + 1)) + 1)*2
    public int func(int day){
        //第10天的时候，跳出递归，返回1（剩下1个桃子）
        if(day == 10){
            return 1;
        }else if(day >= 1 && day <= 9){
            //在其他天数返回刚才推理的公式
            return (func(day + 1) + 1) * 2;
        }else{
            System.out.println("day 在 1-10");
            return -1;
        }
    }
}

运行结果：
第 1天有1534个桃子

221. 222. 223. 224. 老鼠出迷宫1,2,3,4

public class TestUse {
    public static void main(String[] args) {
        //设置二维数组表示迷宫
        //8x7二维数组
        int[][] map = new int[8][7];
        //0表示可以走，1表示障碍物
        //将最上面一行和最下面一行，全部设置为1
        for(int i = 0; i < 7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //最左侧和最右侧列都设置为1
        for(int j = 0; j < 8;j++){
            map[j][0] = 1;
            map[j][6] = 1;//一共7列，最后一列下标为7-1 == 6
        }
        //第4行第2，3列元素也是障碍物
        map[3][1] = 1;
        map[3][2] = 1;
        //输出当前地图
        System.out.println("当前地图情况：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
        //使用findWay给老鼠找路
        T t1 = new T();
        t1.findWay(map, 1, 1);
        System.out.println("老鼠找路情况：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
class T{
    //使用递归回溯的思想来解决老鼠出迷宫
    //findWay方法就是专门来找迷宫的路径
    //如果找到返回true，否则返回false
    //map就是二维数组，即表示迷宫
    //初始位置在下标(1,1)，老鼠到达(6,5)代表出迷宫
    //i,j就是老鼠现在的位置，初始化为(1,1)
    //因为我们是递归的找路，所以我先规定 map数组的各个值得含义
    //0可以走 1表示障碍物 2表示可以走（老鼠走过的路径） 3曾经走过但是死路
    //map[6][5] = 2，即到终点，能走通
    //先确定老鼠找路得策略，下->右->上->左
    public boolean findWay(int[][] map, int i, int j){
        if(map[6][5] == 2){
            return true;//找到
        }else{
            //当前这个位置0，说明可以走
            if(map[i][j] == 0){
                //我们假定可以走通
                map[i][j] = 2;
                //使用策略，来确定该位置是否真的可以走通
                //先尝试向下走
                if(findWay(map, i + 1, j)){
                    return true;
                }
                //走不通，再尝试向右走
                else if(findWay(map, i, j+1)){
                    return true;
                }
                //走不通，再尝试向上走
                else if(findWay(map, i - 1, j)){
                    return true;
                }
                //走不通，再尝试向左走
                else if(findWay(map, i, j - 1)){
                    return true;
                }
                //四个方向都走不通，说明假定能走通是错的
                else{
                    map[i][j] = 3;
                    return false;
                }
            }else{//map[i][j] = 1, 2, 3
                return false;//
            }
        }
    }
}

运行结果：
当前地图情况：
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
老鼠找路情况：
1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1

修改策略：上右下左

public class TestUse {
    public static void main(String[] args) {
        //设置二维数组表示迷宫
        //8x7二维数组
        int[][] map = new int[8][7];
        //0表示可以走，1表示障碍物
        //将最上面一行和最下面一行，全部设置为1
        for(int i = 0; i < 7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //最左侧和最右侧列都设置为1
        for(int j = 0; j < 8;j++){
            map[j][0] = 1;
            map[j][6] = 1;//一共7列，最后一列下标为7-1 == 6
        }
        //第4行第2，3列元素也是障碍物
        map[3][1] = 1;
        map[3][2] = 1;
        //输出当前地图
        System.out.println("当前地图情况：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
        //使用findWay给老鼠找路
        T t1 = new T();
        t1.findWay2(map, 1, 1);
        System.out.println("老鼠找路情况：");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
class T{
    //使用递归回溯的思想来解决老鼠出迷宫
    //findWay方法就是专门来找迷宫的路径
    //如果找到返回true，否则返回false
    //map就是二维数组，即表示迷宫
    //初始位置在下标(1,1)，老鼠到达(6,5)代表出迷宫
    //i,j就是老鼠现在的位置，初始化为(1,1)
    //因为我们是递归的找路，所以我先规定 map数组的各个值得含义
    //0可以走 1表示障碍物 2表示可以走（老鼠走过的路径） 3曾经走过但是死路
    //map[6][5] = 2，即到终点，能走通
    //先确定老鼠找路得策略，下->右->上->左
    public boolean findWay(int[][] map, int i, int j){
        if(map[6][5] == 2){
            return true;//找到
        }else{
            //当前这个位置0，说明可以走
            if(map[i][j] == 0){
                //我们假定可以走通
                map[i][j] = 2;
                //使用策略，来确定该位置是否真的可以走通
                //先尝试向下走
                if(findWay(map, i + 1, j)){
                    return true;
                }
                //走不通，再尝试向右走
                else if(findWay(map, i, j+1)){
                    return true;
                }
                //走不通，再尝试向上走
                else if(findWay(map, i - 1, j)){
                    return true;
                }
                //走不通，再尝试向左走
                else if(findWay(map, i, j - 1)){
                    return true;
                }
                //四个方向都走不通，说明假定能走通是错的
                else{
                    map[i][j] = 3;
                    return false;
                }
            }else{//map[i][j] = 1, 2, 3
                return false;//
            }
        }
    }
    //修改策略，看看路径是否有变化
    //下->右->上->左  ==> 上->右->下->左
    public boolean findWay2(int[][] map, int i, int j){
        if(map[6][5] == 2){
            return true;//找到
        }else{
            //当前这个位置0，说明可以走
            if(map[i][j] == 0){
                //我们假定可以走通
                map[i][j] = 2;
                //使用策略，来确定该位置是否真的可以走通
                //先尝试向上走
                if(findWay2(map, i - 1, j)){
                    return true;
                }
                //走不通，再尝试向右走
                else if(findWay2(map, i, j+1)){
                    return true;
                }
                //走不通，再尝试向下走
                else if(findWay2(map, i + 1, j)){
                    return true;
                }
                //走不通，再尝试向左走
                else if(findWay2(map, i, j - 1)){
                    return true;
                }
                //四个方向都走不通，说明假定能走通是错的
                else{
                    map[i][j] = 3;
                    return false;
                }
            }else{//map[i][j] = 1, 2, 3
                return false;//
            }
        }
    }
}

运行结果：
当前地图情况：
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
老鼠找路情况：
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 0 0 0 0 2 1
1 1 1 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 1 1 1 1 1 1

224.1 什么是回溯

在下标(2,2)处设置障碍物，小球先向下走，可以走通，到达下标(1,2)，然后测试发现上下左右都走不通（上走不通是因为之前走过1,1下标点），于是它回到上一个栈，然后根据刚才走的情况，判断向右走

后面能用数据结构算法求出最短路径

225. 汉诺塔

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟移动一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭

思路
如果A塔只有一个盘子，直接从A塔移动到C塔
如果A塔有很多盘子，把最后一个盘子上面的所有盘子视为一个盘子，将A塔上面这个盘子堆移动到B塔，然后将A塔最下面的盘子移动到C塔，最后将B塔这一堆移动到C塔，递归思想只考虑这个中间过程和跳出递归的过程。

public class TestUse {
    public static void main(String[] args) {
        T t = new T();
        t.move(5, 'A', 'B', 'C');
    }
}
class T{
    //n是盘子数,a,b,c是三个塔，C是此次调用move要移动到的位置，A是此次调用时，某个要移动的盘子所在的位置，确定A C后，B也就能确定了
    public void move(int n, char a, char b, char c){
        //n<1，提示数据不合法
        if(n < 1){
            System.err.println("数据不合法！");
        }
        //如果只有一个盘，直接从A移动到C
        if(n == 1){
            System.out.println(a + "->" + c);
        }else{
            //有多个盘子，先将上面n-1个盘子视为一个整体，移动到B，借助C，move的参数c是要移动的位置
            move(n-1, a, c, b);
            //把下面这个盘移动到C
            System.out.println(a + "->" + c);
            //再把B塔的所有盘移动到C，借助A
            //c = c, a = b,剩下 a
            move(n-1, b, a, c);
        }
    }
}

运行结果：
A->C
A->B
C->B
A->C
B->A
B->C
A->C
A->B
C->B
C->A
B->A
C->B
A->C
A->B
C->B
A->C
B->A
B->C
A->C
B->A
C->B
C->A
B->A
B->C
A->C
A->B
C->B
A->C
B->A
B->C
A->C

226. 八皇后

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

public class TestUse {
    public static void main(String[] args) {
        int arr[] = new int[8];
        T t = new T();
        t.eightQueen(arr, 0);
    }
}
class T{
    public int solNum = 0;//记录解法个数的成员
    //八皇后，n表示所在行数，如果n为棋盘行数，则说明已经放好了
    //即跳出递归的条件
    //max是棋盘行数
    public void eightQueen(int[] arr, int n){
        if(n == arr.length){
            //放好后打印八皇后
            solNum++;
            System.out.println("解法" + solNum + "：");
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    //如果arr[i]==j，打印，对应的是下标i行j列有皇后
                    if(arr[i] == j){
                        System.out.print("o\t");
                    }
                    else
                    {
                        System.out.print("#\t");
                    }
                }
                System.out.println();
            }
            return;
        }
        //依次在第n行放入皇后判断是否冲突，i代表当前行的列下标
        for (int i = 0; i < arr.length; i++) {
            //假定可以放
            arr[n] = i;
            //判断是否可以放，如果可以则继续放
            if(judge(arr, n)){
                eightQueen(arr, n+1);
            }
        }
    }
    //判断当前位置是否可行的方法
    public boolean judge(int[] arr, int n){
            //判断当前位置是否有冲突
        for(int j = 0; j < n; j++){
            //n+1是当前第n+1个皇后arr[n]
            //如果当前皇后和前n+1-1=n个皇后在同一列或者同一对角线上，就发生冲突，则返回false
            if(arr[j] == arr[n] || Math.abs(n - j) == Math.abs(arr[n] - arr[j])){
                return false;
            }
        }
        //全部走一遍，前n个没问题，就说明可以放置
        return true;
    }
}

运行结果
……太长了，直接看最后
解法92：
# # # # # # # o
# # # o # # # #
o # # # # # # #
# # o # # # # #
# # # # # o # #
# o # # # # # #
# # # # # # o #
# # # # o # # #

一共是92种解法，确实难想到，我也是查了好多资料，本科算法课忘得差不多了。

原文地址：https://blog.csdn.net/qq_30204431/article/details/142702197

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：深入探究：在双链表的前面进行插入操作的顺序
下一篇：PHP session_unregister()和session_unset()的区别

面试速通宝典——11
面试速通宝典——11
阅读更多2024-10-05
震动传感器介绍及实战
讲解了震动传感器的工作方式，并且简单应用了震动传感器。
阅读更多2024-10-05
sql乐观锁的实现方式
在数据库管理中，乐观锁（Optimistic Locking）是一种用于处理并发更新的机制。它假设在大多数情况下，并发更新的冲突不会频繁发生，因此在更新数据时不会立即锁定数据行，而是在更新时进行检查。
阅读更多2024-10-05
用Python和OpenCV实现人脸识别：构建智能识别系统
本文介绍了如何使用Python和OpenCV实现人脸检测与识别，涵盖了从基础的人脸检测到LBPH人脸识别模型的训练与应用。通过详细的代码示例，读者可以学习如何加载Haar级联分类器检测人脸，并使用LB
阅读更多2024-10-05
【Matlab元胞自动机】《高速公路人工—自动驾驶混行交通流临界特征研究》
基于matlab的元胞自动机交通流仿真，研究场景是高速公路双向3车道（可以更改场景），车型，车速可自由设置，渗透率可自由调整。完整项目资源，欢迎交流。
阅读更多2024-10-05
【高等数学&学习记录】函数的极限
一、知识点（一）知识结构#mermaid-svg-Dz0Ns0FflWSBWY50 {font-family:"trebuchet ms",verdana,arial,sans-s
阅读更多2024-10-05
JQuery基本介绍和使用方法
jQuery是⼀个快速、简洁且功能丰富的JavaScript框架, 于2006年发布. 它封装JavaScript常⽤的功能代码, 提供了简洁⽽强⼤的选择器和DOM操作⽅法. 使⽤JQuery可以轻松
阅读更多2024-10-05
（PyTorch）深度学习框架-介绍篇
PyTorch的诞生是深度学习发展的需求以及开发团队不断努力的结果，它的出现为深度学习的研究和应用提供了一个强大而灵活的工具。
阅读更多2024-10-05
G. Gears （2022 ICPC Southeastern Europe Regional Contest. ）
2022 ICPC Southeastern Europe Regional Contest. G. Gears
阅读更多2024-10-05
信息学奥赛一本通 2087：【22CSPJ普及组】解密(decode) | 洛谷 P8814 [CSP-J 2022] 解密
使用枚举算法，求方程组的解，在输入数据较小时可以得到解。必须是完全平方数，开方后是一个正整数。因此是一个二元方程组求解的问题。由于p、q都是正整数，那么首先。已知一元二次方程两根分别为。显然p、q是一
阅读更多2024-10-05