2

蓝桥杯——巧妙地递归 - lx-Meteor

 1 year ago
source link: https://www.cnblogs.com/lx-meteor/p/17024267.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一、切蛋糕思想

  • 对于递归，我们可以采用思想之一，切蛋糕思想。
  • 简而言之，就是将一个大问题，切成若干个小问题进行解决。
  • 递归三要素：找重复、找变化、找边界
  • 我们可以理解为，自己处理一小部分，剩下的部分交给别人处理（递归）
  • 分解为：直接量 + 小规模子问题

1.1 经典求阶乘

  • 求阶乘
    • jc(n)：求n的阶乘 jc(n-1)：求n-1的阶乘
    • 1.找重复： n*(n-1) ————子问题
    • 2.找变化：变化的量应该作为参数
    • 3.找边界：出口



public class 递归 {
    public static int jc(int n) {
        if(n == 1)
            return 1;
        return n * jc(n-1);
    }
}




1.2 打印i到j


  • 1.找重复：理解为我处理当前参数问题，剩下的部分交给这个函数处理（规模更小的子问题）
    • 

  • 2.找变化：变化的量应该作为参数
    • 

  • 3.找边界：出口
    • 







public static void print(int i, int j) {
        // 出口
        if(i > j) return;
        System.out.println(i);
        // 重复与变化
        print(i+1,j);
    }




1.3 数组求和


  • 当我们发现无法进行递归时，肯定是我们的参数不够
    • 







 public static int sum(int[] arr,int start) {
        if(start == arr.length)
            return 0;
        return arr[start] + sum(arr,start+1);
    }




1.4 翻转字符串


  • 使用递归对一个字符串进行翻转
    • 







public static String reverse(String str, int end) {
        if(end == 0)
            return ""+str.charAt(0);
        return str.charAt(end) + reverse(str,end-1);
    }




二、递归公式与等价转换思想


  • 和上面切蛋糕思想不同的是，这种问题我们无法进行切分，但是我们都可以转换成数学问题，当找到数学问题后进行等价转换即可。
    • 

  • 分解为：多个子规模小问题
    • 




2.1 经典斐波那契数列


  • F(n) = F(n-1) + F(n-2)
    • 







// 求斐波那契数列第n项的值
public static int fib(int n) {
        // 3. 找出口
        if(n == 1 || n == 2) return 1;
        // 1.找变化 | 2.找重复
        return fib(n-1) + fib(n-2);
    }




2.2 最大公约数


  • 经典的欧几里得算法也称之为辗转相除法
    • 

  • 通过最大公约数我们也可以判断两个数是否互质
    • 

  • F(m,n) = F(n,m%n)
    • 







public static int zzxc(int m, int n) {
        if(n == 0) return m;
        return zzxc(n,m%n);
    }




2.3 递归形式的插入排序


  • 同样是利用切分思想，我们对数组前k-1个元素进行排序
    • 

  • 最后处理最后一个单独的元素
    • 

  • 递归都是父问题转换成子问题
    • 







public static void insertArr(int[] arr, int k) {
        // 1.对数组前k-1个元素进行排序
        insertArr(arr, k - 1);



        // 2.将最后一个元素插入到排好序的数组中
        int temp = arr[k]; // 记录该数
        while(temp < arr[k-1]) { // 后一个数比前一个数小的情况，将大的数后移
            arr[k] = arr[k-1];  // 直到找到适合自己的位置为止
            k--;
        }
        arr[k] = temp;
    }




三、搞不清楚的汉诺塔


  • 1~N从A移动到B，C作为辅助
    • 




等价于：


  1. 

    1~N-1从A移动到C，B为辅助
    

    2. 

  2. 

    把N从A移动到B
    

    3. 

  3. 

    1~N-1从C移动到B，A为辅助
    

    4. 







	/**
     * 八、汉诺塔问题
     * 将N个盘子从source移动到target的路径打印
     * @param N 初始的N个从小到大的盘子，N是最大编号
     * @param from 原始柱子
     * @param help 辅助的柱子
     * @param to 目标柱子
     */
    public static void printHanoiTower(int N, String from, String to, String help) {



        printHanoiTower(N-1, from, help, to);
        System.out.println("move" + N + "from" + from + "to" + to);
        printHanoiTower(N-1, help, to, from);
    }




  • 对于蓝桥杯递归知识内容就总结这么多，若想深入学习等待后续更新。
    • 

  • 我将会继续更新关于蓝桥杯方向的学习知识，感兴趣的小伙伴可以关注一下。
    • 

  • 文章写得比较走心，用了很长时间，绝对不是copy过来的！
    • 

  • 尊重每一位学习知识的人，同时也尊重每一位分享知识的人。
    • 

  • 😎你的点赞与关注，是我努力前行的无限动力。🤩
    • 




__EOF__

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK