递归与分治策略-第一节:递归和典型递归问题(代码片段)

快乐江湖 快乐江湖     2022-12-04     573

关键词:

文章目录

一:LeetCode中有关递归和分治的题目

递归题目链接

分治题目链接

二:递归与分治概述

递归与分治:任何可以用计算机求解的问题所需要的计算时间都和其规模有关,如果问题的规模越小,解题所需的计算时间往往也越短,从而也比较容易处理,例如

  • 对于 n n n个元素的排序问题:当 n = 1 n=1 n=1时不需要任何计算;当 n = 2 n=2 n=2时,只需要做一次比较即可排好序;当 n = 3 n=3 n=3时则两次。而当 n n n较大时,这个问题就不好处理了

所以要想直接解决一个较大的问题,有时是相当有困难的。所以分治法的设计思想是:将一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,也即分而治之。如果原问题可以分割为 k k k个子问题, 1 < k ≤ n 1<k\\leq n 1<kn,且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题于原问题类型一致而其规模不断缩小,最终使子问题缩小到容易求出其解,由此自然引出递归算法。分治与递归像一对孪生兄弟,经常同时应用在算法设计中,并由此产生许多高效算法

三:递归基本概念

递归:递归算法是指直接或间接调用自身的算法;递归函数是指用函数自身给出定义的函数。在计算机算法设计与分析中,递归技术非常有用。使用递归技术往往可以使函数的定义和算法的描述简洁且易于理解,而且有些数据结构(例如二叉树)由于其本身具有递归特性,所以也特别使用递归的形式来求解

构造递归算法的基本步骤为

  • 确定递归边界
  • 描述递归关系
  • 构造递归函数

四:典型递归问题分析

(1)阶乘

阶乘 n ! = n × ( n − 1 ) × . . . × 1 n!=n×(n-1)×...×1 n!=n×(n1)×...×1,可递归定义如下

  • 第一个式子是递归边界,如果没有边界就有可能会引发无穷递归
  • 第二个式子是用较小自变量的函数来表示较大自变量的函数值,相当于问题规模减小

这个问题很简单,递归定义式很容易给出,所以编写代码如下

public class Factorial 

    public static int factorial_recurse(int n )
        if(n == 1)return 1;
        return n * factorial_recurse(n-1);
    

    public static void main(String[] args) 
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt())
            int n = scanner.nextInt();
            System.out.println(n+"!等于:" + factorial_recurse(n));
        
    

当然,递归解法也有其对应的非递归解法

public class Factorial 
    public static int factorial_none_recurse(int n)
        int ret = 1;
        for(int i = 1; i <= n; i++)
            ret *= i;
        
        return ret;
    

    public static void main(String[] args) 
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt())
            int n = scanner.nextInt();
            System.out.println(n+"!等于:" + factorial_none_recurse(n));
        
    

(2)Fibonacci数列

Fibonacci数列 :无穷数列【1 1 2 3 5 8 13 21 34 55…】称为Fibonacci数列,在Fibonacci数列中从第三个数字开始,每一个数字都是前两个数字之和,这是一个典型的递归问题,其递归定义式如下

很明显这个问题需要两个递归边界

问题还是比较简单,所以编写代码如下

public class Fibonacci 
    public static int fibonacci_recurse(int n)
        if(n <= 1)return 1;
        return fibonacci_recurse(n-1) + fibonacci_recurse(n-2);
    

    public static void main(String[] args) 
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt())
            int n = scanner.nextInt();
            System.out.println("第" + n+"个fibonacci数为:" + fibonacci_recurse(n));
        
    

fibonacci数列的纯递归写法有很多的重复子问题,所以其时间复杂度极高。所以对于其递归写法,我们可以进行一定优化,引入一个“备忘录”去解决这一部分重复子问题

public class Fibonacci 
    public static int fibonacci_recurse(int n)
        if(n <= 1)return 1;
        return fibonacci_recurse(n-1) + fibonacci_recurse(n-2);
    

    public static int fibonacci_recurse_optimize(int[] memo, int n)
        if(n <= 1)return 1;
        if(memo[n] != 0)return memo[n];//如果备忘录有这个元素那就不用递归了
        memo[n] = fibonacci_recurse(n-1) + fibonacci_recurse(n-2);//保存下来
        return memo[n];
    

    public static void main(String[] args) 
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt())
            int n = scanner.nextInt();
            int[] memo = new int[n+1];//备忘录,元素如果为0表示没有被记录
            long recurse_start_time = System.nanoTime();
            System.out.println("(递归)第" + n+"个fibonacci数为:" + fibonacci_recurse_optimize(memo, n));
            long recurse_end_time = System.nanoTime();
            long none_recurse_start_time = System.nanoTime();
            System.out.println("(非递归)第" + n+"个fibonacci数为:" + fibonacci_recurse_optimize(memo, n));
            long none_recurse_end_time = System.nanoTime();
            System.out.println("递归用时:" + (recurse_end_time - recurse_start_time));
            System.out.println("非递归用时:" + (none_recurse_end_time - none_recurse_start_time));
            System.out.println("----------------------------------------------------");
        
        scanner.close();
    

(3)排列问题

排列问题:设计一个递归算法生成 n n n个元素的全排列

采用递归解法,可以将规模为 n n n的全排列问题转换为规模为 n − 1 n-1 n1的全排列问题。所以他可以看作是固定 [ 0 , k ] [0, k] [0,k]位,对 [ k + 1 , n ] [k+1, n] [k+1,n]位进行全排列,当 k + 1 = n k+1=n k+1=n时,递归结束

如下为决策树,每一个子决策树都是一个全排列问题,


代码如下

public class Permutations

    public static void swap(int[] test, int k, int i)
        int temp = test[k];
        test[k] = test[i];
        test[i] = temp;

    

    public static void perm(int[] list, int k, int m)
        //只有一个元素,递归结束,这一种排列情况可以输出了
        if(k == m)
            for(int i = 0; i <= m; i++)
                System.out.print(list[i]);
            
            System.out.println();
        
        //否则开始递归
        else
            for(int i = k; i <= m; i++)
                swap(list, k, i);
                perm(list, k+1, m);
                swap(list, k, i);
            
        
    

    public static void main(String[] args) 
        int[] test = new int[]2, 3, 5, 7;
        perm(test, 0, 3);
    

(4)整数划分

整数划分:将正整数 n n n表示成一系列整数之和,即 n = n 1 + n 2 + . . . + n k n=n_1+n_2+...+n_k n=n1+n2+...+nk

在这里,正整数 n n n的这种表示称为正整数 n n n的划分。正整数 n n n的不同划分个数称为正整数 n n n的划分数,记为 p ( n ) p(n) p(n),例如6有如下11种不同的划分方法,所以 p ( 6 ) = 11 p(6)=11 p(6)=11

6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1

在正整数 n n n的所有划分中,用 q ( n , m ) q(n,m) q(n,m)表示最大加数 n 1 n_1 n1不大于 m m m的划分个数,正整数 n n n的划分数 p ( n ) = q ( n , n ) p(n)=q(n,n) p(n)=q(n,n)

  • n ≥ 1 n\\geq1 n1时, q ( n , 1 ) = 1 q(n,1)=1 q(n,1)=1,因为当最大加数最大为1时,任何正整数只有一种划分形式,也即全1
  • 由于最大加数不可能大于 n n n,所以当 m ≥ n m \\geq n mn时, q ( n , m ) = q ( n , n ) q(n,m)=q(n,n) q(n,m)=q(n,n), q ( 1 , m ) = 1 q(1,m)=1 q(1,m)=1
  • 正整数 n n n的划分由 n 1 = n n_1=n n1=查看详情

    分治策略(代码片段)

    递归与分治策略递归的概念一个直接或间接地调用自身的算法成为递归算法。在计算机算法设计与分析中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据如二叉树等,由于本身固有的递归特性,特别适... 查看详情

    动态规划-第一节2:动态规划之使用“斐波那契数列”问题说明重叠子问题如何解决(代码片段)

    ...文参考labuladong公众号总结链接文章目录(1)暴力递归(2)带有表的递归解法(3)动态规划解法(4)补充:关于斐波那契数列的极致解法(时间和空间均最优)Fibonacci数列:无穷数... 查看详情

    递归迭代和分治:递归的典型例子(代码片段)

    ​本期我们一起看几个典型的递归的例子。递归就是每次调用的时候方法是自己,但是参数变了,就是下面这个样子:1.斐波那契数列斐波那契数列的是这样一个数列:1、1、2、3、5、8、13、21、34….,即第一... 查看详情

    数据结构第一节递归

    ...经过抽象和封装之后,实现分支转向的一种重要机制;而递归这是函数和过程调用的一种特殊形式,即允许函数进行自我调用。  递归的价值在于,许多应用问题都可简洁而准确地描述为递归形式。  递归也是一种基本而典... 查看详情

    递归分治策略

      在前面的随笔中其实谈到了一些递归分治的算法,也以为自己写上去了,今天在看到没有写。下面就来补上。  递归分治是算法中比较重要的思想。在之前也聊到了递归和递推的区别。递归这里就不再详细讲述了。下面讲... 查看详情

    分治策略(求解递归式的方法)

    ...1/3的划分。解决:对于子问题的解决,很明显,采用的是递归求解的方式,如果子问题足够小了,就停止递归,直接求解。合并:将子问题的解合并成原问题的解。  这里引出了一个如何求解子问题的问题,显然是采用递归调... 查看详情

    第二章-递归与分治策略

    第一题:问题名称:整数划分问题。问题描述:正整数n可以表示为一系列正整数之和:n=n1+n2+...+nk(k>=1, n1>=n2>=nk ),则称这种表示为正整数n的划分,不同的这种表示的个数称为正整数n的划分数,记为p(n)。在所有划... 查看详情

    递归与分治策略(代码片段)

    递归算法精讲🥇前言:🥈递归的概念🥉基本概念:🥉算法实例:🥈分治法的基本思想🥇前言:对于计算机科学来说,算法的概念至关重要。例如,在一个大型软件系统的开发中&#x... 查看详情

    递归与分治思想:八皇后问题(在此用递归)(回溯算法的典型题)(代码片段)

    1做法:第一步随便放一个棋子,然后找安全位置放第二个棋子,然后放好后再找安全地放第三个x棋子,以此类推2详细解释:https://www.bilibili.com/video/av76265320?from=search&seid=105952691972837702233#include<stdio.h>45intcount=0;6intnotdanger(i... 查看详情

    递归的逻辑——递归与分治(代码片段)

      递归和分治天生就是一对好朋友。所谓分治,顾名思义,就是分而治之,是一种相当古老的方法。  在遥远的周朝,人们受生产力水平所限,无法管理庞大的土地和众多的人民,因此采用了封邦建国的封建制度,把土地一... 查看详情

    递归迭代和分治:分治与二分查找(代码片段)

    1.分治的基本思想在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以... 查看详情

    分治策略 最大子数组问题

     递归式 递归式与分治方法是紧密相关的,因为使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个等式或不等式,它通过更小的输入上的函数值来描述一个函数。例如,在2.3.2节,我们用递归式描述... 查看详情

    递归迭代和分治法(代码片段)

    一、递归算法:直接或间接地调用自身的算法。1、使用递归要注意的有两点:递归就是在过程或函数里面调用自身;在使用递归时,必须有一个明确的递归结束条件,称为递归出口.2、递归分为两个阶段:递推:把复杂的问题的求解推到... 查看详情

    算法设计与分析总结

    ...可读性、健壮性和高效性和低存储量需求等特征。第二章递归与分治策略递归的概念:直接或者间接的调用自身的算法。递归函数:用函数自身给出定义的函数。构成递归式的两个基本条件:递归的边界条件和递归的定义(递归... 查看详情

    递归与分治法

    ...些子问题(互相独立且)结构与原来问题的结构相同,再递归地求解这些子问题。问题分解成子问题;(divide)当达到某个阈值n0时,给出直接求解的方法;(conquer)最后把各个子问题的解合并起来,得到原来问题的解;(merge... 查看详情

    数据结构与算法(12)—分治策略(代码片段)

    ...每一个小规模问题,并将结果汇总得到原问题的解。PS:递归问题则体现了分治策略。优化问题和贪心策略  1.优化问题例子:找零兑换问题让自动售货机每次找零给顾客最少数量硬币。贪心策略解决:我们每次都试图解决问... 查看详情

    五类常见算法小记(递归与分治,动态规划,贪心,回溯,分支界限法)

    近日复习了一些算法知识,小记于此递归与分治法直接或间接地调用自身的算法称为递归算法。递归是算法设计与分析中经常使用的一种技术,描写叙述简单且易于理解。分治法的设计思想是将一个规模为n难以解决的问题分解... 查看详情