【数据结构与算法之递归算法】案例

秒速五厘米 2024-03-25 19:16 95阅读 0赞

#### 【数据结构与算法之递归算法】案例 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之递归算法】案例
         *   *   *  1 数组的全排列
                 *  2 梵塔问题(汉诺塔问题)

###### 1 数组的全排列 ######

编写一个程序，将数组中的元素进行全排列，并输出每一种排列方式。

【举个栗子】数组元素\{1,3,5\}

6 种排列方式：\{1,3,5\}、\{1,5,3\}、\{3,1,5\}、\{3,5,1\}、\{5,1,3\}、\{5,3,1\}

解决数组全排列问题最经典的方法就是使用递归算法，因为数组的全排列问题具有非常明显的递归特性。

设数组  R = r 1 , r 2 , . . . , r n R = \{r\_1,r\_2,...,r\_n\} R=r1,r2,...,rn 包含n 个元素，定义符号  R i = R − \{ r i \} R\_i = R - \\\{r\_i\\\} Ri=R−\{ ri\} ， R i R\_i Ri 表示原数组R 去掉元素  r i r\_i ri 后的新数组。

数组R 的全排列Perm® 可定义如下：

*  当n = 1时，Perm® = ®，其中r为数组R 中的唯一元素
 *  当n > 1时，Perm® 由排列 ( r 1 ) P e r m ( R 1 ) , ( r 2 ) P e r m ( R 2 ) , . . . , ( r n ) P e r m ( R n ) (r\_1)Perm(R\_1),(r\_2)Perm(R\_2),...,(r\_n)Perm(R\_n) (r1)Perm(R1),(r2)Perm(R2),...,(rn)Perm(Rn) 构成

Java 实现描述：

import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: FullPermutation
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 16:33
     */
    
    public class FullPermutation {
        
    
    
        public static void Perm(int[] array, Stack<Integer> stack) {
        
            if (array.length == 1) {
        
                //当前数组array的长度为1，此时将该元素入栈并输出
                stack.push(array[0]);
                System.out.println(stack);
                stack.pop();
            } else {
        
                for (int i = 0; i < array.length; i++) {
        
                    //创建一个临时数组tmp，其长度为array.length - 1
                    //该数组用来存放Ri的内容
                    int[] tmp = new int[array.length - 1];
                    //将第i个元素ri保存在栈stack中
                    stack.push(array[i]);
                    //将剩下的元素Ri保存到临时数组tmp中
                    System.arraycopy(array, 0, tmp, 0, i);
                    System.arraycopy(array, i + 1, tmp, i, array.length - 1 - i);
                    //递归调用Perm将Ri继续进行全排列
                    Perm(tmp, stack);
                    //将第i个元素ri移出栈顶
                    stack.pop();
                }
            }
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        1, 3, 5};
            Stack<Integer> stack = new Stack<Integer>();
            Perm(array, stack);
        }
    }

运行结果

![在这里插入图片描述][53273dc6115d4a3d82e019270614fa8f.png_pic_center]

进行全排列的过程：

开始时，array = \[1,3,5\]，stack = \[\]

![在这里插入图片描述][f477c1cce4a34912850f38abfdb1bf79.png_pic_center]

array.length ≠ 1，走了else

![在这里插入图片描述][ea5ee8264a4941a387ac9a4f21e22d55.png_pic_center]

![在这里插入图片描述][2deaba7d652044818ee1bc4e19ff1224.png_pic_center]

![在这里插入图片描述][4e8a89abed884ba89aee87ae89110ced.png_pic_center]

这里笔者就不截完了，自己debug，能够很清晰的看到整个递归的运行过程。

###### 2 梵塔问题(汉诺塔问题) ######

圣庙有一个黄铜板，黄铜板上有3根细针，其中的一根针上放了半径由大到小的64 个圆盘。

![在这里插入图片描述][5c38cc1dcbb04d48b5721a499d125458.png_pic_center]

现在需要将这些圆盘从一根针A 移到指定的针 C 上，每次只能移动一个，可以用B 辅助，但是不管在什么情况下，任何针上的圆盘都必须保证大圆盘在下，小圆盘在上。

编写程序解决这个问题。

其实问题想清楚也不难：

*  问题1：将A上的第1-63个盘子借助C移到B上
 *  问题2：将B上的1-63个盘子借助A移到C上

Java代码实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: HanotaProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 19:04
     */
    
    public class HanotaProblem {
        
    
        public static void movePlate(int n, char x, char y, char z) {
        
            if (n == 1) {
        
                System.out.println(x + "===>>>" + z);
            } else {
        
                movePlate(n - 1, x, z, y);
                System.out.println(x + "===>>>" + z);
                movePlate(n - 1, y, x, z);
            }
        }
    
        public static void main(String[] args) {
        
    
            int n = 3; // 盘子数量
            movePlate(n, 'A', 'B', 'C');
    
        }
    
    }

运行结果

![在这里插入图片描述][ac91280b2c244af588b0bca3228d6e89.png_pic_center]

图解：

共三个盘子，初始状态：

![在这里插入图片描述][82e9190189d24b4cb9d5c2017b93b796.png_pic_center]

① A===>>>C

![在这里插入图片描述][49fdbdb40ea94d4b9ae727439b894431.png_pic_center]

② A===>>>B

![在这里插入图片描述][4c0f1bec0dbb48f991804a13a5888a34.png_pic_center]

③ C===>>>B

![在这里插入图片描述][8b099e73f5a045bda1ff37943234a559.png_pic_center]

④ A===>>>C

![在这里插入图片描述][1dc5bb0cc8f8471d8e1da9c2d7035fc0.png_pic_center]

⑤ B===>>>A

![在这里插入图片描述][d9197ec7c0da4adc9e8f9734b540991b.png_pic_center]

⑥ B===>>>C

![在这里插入图片描述][d28ec3198e214943bcedad870ef538f3.png_pic_center]

⑦ A===>>>C

![在这里插入图片描述][740c53558f6e411b9f65520bbf674178.png_pic_center]

OK。

[53273dc6115d4a3d82e019270614fa8f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3c5dc653027444c2b4eff78e710f2758.png
[f477c1cce4a34912850f38abfdb1bf79.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/73c4a38e6c004354a948b3770486d9fd.png
[ea5ee8264a4941a387ac9a4f21e22d55.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2d2e91bac19846c4857ee5fcf9e4d1ab.png
[2deaba7d652044818ee1bc4e19ff1224.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/19accf4b2d0542ac9b9e54f3f52fe71e.png
[4e8a89abed884ba89aee87ae89110ced.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7d67eba2473249b78ee673d82f687e3a.png
[5c38cc1dcbb04d48b5721a499d125458.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/551adc2a8f5c4d03b25180af8c308832.png
[ac91280b2c244af588b0bca3228d6e89.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/15eed7285fc542888a605c2c1a97af05.png
[82e9190189d24b4cb9d5c2017b93b796.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e1f9cf5796064844bc54eeb7e7bc74f8.png
[49fdbdb40ea94d4b9ae727439b894431.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/042a90a64d3943119035c1534ca7b21e.png
[4c0f1bec0dbb48f991804a13a5888a34.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a467a490a78d40edb0436b3801894b63.png
[8b099e73f5a045bda1ff37943234a559.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7d95c6da5bd44740b06e216549c98f1d.png
[1dc5bb0cc8f8471d8e1da9c2d7035fc0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/027024c44b9141b78c26617112906165.png
[d9197ec7c0da4adc9e8f9734b540991b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f58c916061f34ddb8c96c95af2ed8408.png
[d28ec3198e214943bcedad870ef538f3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a88a7e443f654a63bfc427bd5df8665f.png
[740c53558f6e411b9f65520bbf674178.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/70c1cdfd82964f49b2c9388fd3481758.png