爱游戏-五种常见算法策略之一——递归和分而治之策略

以下是（爱游戏）小编为您整理的最新体育资讯内容,希望对您有所帮助：

递归和分治策略

递归和分而治之策略是五种常见的算法策略之一。 分而治之策略的思想就是分而治之，即先将一个大规模问题分解为几个较小规模的问题，然后再解决这些小问题。 然后将获得的解决方案合并以获得最终解决方案。 在许多情况下，分而治之和递归一起使用可以创造奇迹（1+1>2）。 在本文中，我们将从递归开始，然后逐渐过渡到分而治之。 主要的解释方式是通过9个例子来说明问题。 题目按照由易到难、由易到深的顺序排列，让你对递归和分而治之有一个粗略的了解。 当然，最重要的是要进行大量的练习才能掌握它。

0.0，序列（简单）

递归

我们第一次接触递归通常是在看到C语言中的一道题——序列的时候。 乍一看可能有点不可思议，但该函数实际上可以调用自身！ ！ 但确实如此，它确实存在，而且递归也为我们一些算法的设计提供了很大的便利。 一般来说，递归函数并不难理解，甚至可以通过数学归纳法来证明，但一直令人困惑。 最大的批评是调试时间。 有时调试更复杂的递归函数会让人们发疯。

这里我们将从易到难开始，用一些例子来解释递归函数。 使用数字序列来制作这个示例来介绍递归函数。

第一个数是1，第二个数也是1，从第三个数开始，后面的每个数都等于前两个数之和。 需求：输入一个n，输出第n个斐波那契数。

我们先梳理一下思路，分以下三步来看：

第一步，函数输入 n 并输出（即返回）第 n 个斐波那契数：

public static int fibonacci(int n){
        
}

第二步明确递归终止条件：

public static int fibonacci(int n){
    if(n == 1) return 1;
    else if (n == 2) return 1;
}

第三步，求函数的递归关系：

public static int fibonacci(int n){
    if(n == 1) return 1;
    else if(n == 2) return 1;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}

这样，我们就写完了斐波那契数列的递归函数。 当然，这只是我们的开胃菜。 让我们继续一个入门级问题，计算阶乘。

阶乘

输入一个数字并输出其阶乘。 我们也用这三个步骤往下走。

第一步，函数输入 n 并返回 n 的阶乘。

public static int factorial(int n){     
}

第二步明确递归终止条件：

public static int factorial(int n){                     //0的阶乘等于1
        if(n == 0)  return 1;
}

第三步，求函数的递归关系

public static int factorial(int n){                     //0的阶乘等于1
        if(n == 0)  return 1;
        else return factorial(n - 1) * n;
}

完成前两项之后，你一定会觉得这不是很简单。 别着急，我们要由易到难，由易到深，这样一步步科学的学习。 下面的例子是青蛙跳跃问题。 该问题用作递归和动态规划问题的示例。 这里我们将使用递归来解决，稍后我们将使用动态规划策略来解决这个问题。

小青蛙跳步

青蛙一次最多可以跳 1 或 2 步。 找出青蛙有多少种方式可以跳到 n 级台阶。

还有三步。 第一步是明确函数的输入和返回。

public static int Jump_Floor1(int n){
    
}

第二步明确递归终止条件

如果n=1，小青蛙一次只能跳上第一级台阶，所以有一种跳法。 如果n=2，小青蛙可以一次跳一步两次，或者直接一次跳两步，所以是两步跳的一种方法。

public static int Jump_Floor1(int n){
        if(n <= 2){
            return n;
        }
}

第三步求函数的递归条件

这里我们不能简单地(n-1)就结束了。 有两种情况： 1、第一次跳到1级，还有n-1级要跳。 2.第一次跳到2级时，还有n-1级要跳。 需要跳跃n-2级

public static int Jump_Floor1(int n){
    if(n <= 2){
        return n;
    }else{  //这里涉及到两种跳法，1、第一次跳1级就还有n-1级要跳，2、第一次跳2级就还有n-2级要跳
    return Jump_Floor1(n-1)+Jump_Floor1(n-2);
    }
}

下面的示例问题是一个排列问题，即找到一组数字的完整排列。

全排列问题

在全排列问题中，我们需要使用交换函数swap来交换两个数字的位置。 其定义如下：k数组的元素是要排列的元素，k和m是要交换的两个元素的下标。

private static void swap(int a[], int k, int m){       //交换k和m下标的元素的值
        int temp = a[k];
        a[k] = a[m];
        a[m] = temp;
}

接下来继续回到递归函数

第一步是明确函数的输入和返回。 这里我们需要输入一个要排列的元素数组，数组第一个元素的下标，最后一个元素的下标。

public static void perm(int a[], int k, int m){
}

第二步是明确递归终止条件，即只剩下一个元素时。

public static void perm(int a[], int k, int m){
    if(k == m) {     //只有一个元素
        for (int i = 0; i <= m; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

第三步求递归条件

public static void perm(int a[], int k, int m){
    if(k == m) {     //只有一个元素
        for (int i = 0; i <= m; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }else{          //还有多个元素，递归产生排列
        for (int i = k; i <= m; i++) {
            swap(a,k,i);                //排列到这个元素就要将其放在第一个位置
            perm(a,k+1,m);
            swap(a,k,i);                //从此出口出去后还需要将刚刚调换的位置换回来
        }
    }
}

下面是递归的最后一个例子，整数除法问题。

整数除法

为了解释这个问题，什么是整数除法？

算法思想：我们用q(n,m)来表示n除以不大于m的数的方式数。

第一步明确函数输入和返回

public static int equationCount(int n, int m){
}

第二步明确递归终止条件

public static int equationCount(int n, int m){
        if (n < 1 || m < 1)
            return 0;
        if(n == 1 || m == 1)
            return 1;
}

第三步，求递归关系

public static int equationCount(int n, int m){
        if (n < 1 || m < 1)
            return 0;
        if(n == 1 || m == 1)
            return 1;
        if(n < m)
            return equationCount(n,n);
        if(n == m)
            return equationCount(n,m-1)+1;
        return equationCount(n-m,m)+equationCount(n,m-1);   //n > m的情况
}

分而治之的策略

分而治之策略的基本思想是将一个规模为n的问题分解为k个规模更小的子问题，这些子问题彼此独立且与原问题相同。 递归地求解这些子问题，然后合并子问题的解，得到原问题的解。 描述这一点最合适的方式就是我们在上一篇文章中介绍的归并排序方法。 我们将在本文中再次介绍。 。

我们总结分而治之策略解决问题的步骤如下：将大问题分解为子问题，分别求解子问题，然后将子问题的解合并到大问题的解中。问题。

我们来看第一个典型例子——归并排序

归并排序

这里我们主要关注归并排序体现其分而治之策略的算法逻辑，而不会太深入地探究这种排序算法是如何执行的。 关于归并排序的详细说明，请参考我的另一篇博文——数据结构——八种主要排序算法。

归并排序的思想是，首先将数组分成小数组，直到每个小数组只包含一个元素。 然后在这个小数组中，这个元素自然是有序的，然后将它们合并（通过merge函数实现），按照从小到大的顺序，一层一层的，就是把小问题的解合并成大问题的解。

这是将大问题分解为小问题的过程

/**
 * 只要数组的大小不为1，就一直分割，直到不能分割为止（即数组长度为1），
 * 不能分割后按照出入栈顺序，会将分割的小数组分别排序后归并起来
 * @param data      待排序数组
 * @param start     起始位置
 * @param end       终止位置
 */
public static void merge_sort(int data[], int start, int end){
    int mid = (start+end)/2;
    if(start < end){
        merge_sort(data,start,mid);
        merge_sort(data,mid+1,end);
        merge(data,start,mid,end);
    }
}

下面是合并小问题的解决方案，以及合并过程

/**
 * 这个函数是将数组合并在一起的，其实并没有将数组真的分开，只是用start和end指示不同的元素，来达到分割的目的
 * @param  p        指示子数组1的元素
 * @param  q        指示子数组2的元素
 * @param  r        指示合并后数组的元素
 * @param start     start到mid是需要合并的子数组1
 * @param mid
 * @param end       mid+1到end是需要合并的子数组2
 */
private static void merge(int data[], int start, int mid, int end){
    int p = start, q = mid+1, r = 0;
    int newdata[] = new int[end-start+1];
    while(p <= mid && q <= end){
        if(data[p] >= data[q]){                 //从大到小排序
            newdata[r++] = data[p++];
        }else{
            newdata[r++] = data[q++];
        }
    }
    //此时，两个子数组中会有一个中元素还未被全部归并到新数组中，作如下处理
    while(p <= mid){
        newdata[r++] = data[p++];
    }
    while(q <= end){
        newdata[r++] = data[q++];
    }
    //再将有序的数组中的值赋给原数组，其实也可以直接返回这个新数组
    for (int i = start; i <= end; i++) {
        data[i] = newdata[i-start];
    }
}

二分查找

然后还有一个分而治之策略的经典例子——二分查找。 顾名思义，就是找到一个元素在有序（从小到大）数组中的位置。 首先，将数组从中间变成两个小数组。 然后与中间值进行比较。 如果相等则直接返回。 如果不相等，则有两种情况。 如果中间元素小于要查找的值，则从数组的后半部分开始继续二分查找。 否则，从数组的前半部分开始二分查找。

public static int Binary_Search(int []data, int x, int n){   //data为待搜索数组(有序)，x为待搜索元素，n为数组大小
    int left = 0, right = n - 1;            //指示左右的两个指示器
    while(left <= right){                   //left可以等于right，因为有可能刚好两个指示器同时指示到了待查找元素上
        int mid = (left+right)/2;
        if(data[mid] > x)
            right = mid-1;
        else if(data[mid] < x)
            left = mid+1;
        else    return mid;
    }
    return -1;           //表示查找失败
}

棋盘覆盖

让我们逐渐增加难度。 下一个问题称为棋盘覆盖。 我们先简单介绍一下这个问题。

在由 2^k × 2^k (k≥0) 个方格组成的棋盘中，恰好有一个方格与其他方格不同。 这个正方形称为特殊正方形。 显然，棋盘上特殊方格有 4^k 种可能的位置，因此有 4^k 种不同的棋盘。 图 4.10(a) 显示了当 k=3 时的 64 个棋盘之一。 国际象棋覆盖问题需要如图4.10(b)所示的四个不同形状的L型多米诺骨牌来覆盖给定棋盘上除特殊方格之外的所有方格，并且任何两个L型多米诺骨牌不得重叠。 。

图4.10(a)

图4.10(b)

这里为了说明方便，我们用k=2时的情况来说明这个问题。 设初始情况为

第一次分成四个小块，分成四个子板，以黄线为分界线

然后分别填写

填完后就可以分割了

重复上面的填充操作，将所有的方格都填满

当k较大时，可以参考这位老大的博客关于棋盘覆盖问题。 接下来我们就用代码来实现一下。

static int board[][] = new int[4][4];   //棋盘
static int tag = 1;                     //骨牌编号
/**
 * 分治算法典例2———棋盘覆盖问题
 * @date    2019/11/3   afternoon
 * @param tr    棋盘左上角方格的行号
 * @param tc    棋盘左上角方格的列号
 * @param dr    特殊方格所在的行号
 * @param dc    特殊方格所在的列号
 * @param size  棋盘宽度
 * @param s     当前棋盘宽度的一半
 * @param tr+s  当前棋盘中间行的行号
 * @param tc+s  当前棋盘中间列的列号
 */
public static void chess(int tr, int tc, int dr, int dc, int size){
    if(size == 1)
        return;
    int newtag = tag++;
    int s = size / 2;     //分割棋盘
    //覆盖左上角子棋盘
    if(dr < tr+s && dc < tc+s){ //特殊方格在此棋盘中
        chess(tr,tc,dr,dc,s);
    }else{      //此棋盘中无特殊方格
        board[tr+s-1][tc+s-1] = newtag;
        chess(tr,tc,tr+s-1,tc+s-1,s);
    }
    //覆盖右上角子棋盘
    if(dr < tr+s && dc >= tc+s){
        chess(tr,tc+s,dr,dc,s);
    }else{
        board[tr+s-1][tc+s] = newtag;
        chess(tr,tc+s,tr+s-1,tc+s,s);
    }
    //覆盖左下角子棋盘
    if(dr >= tr+s && dc < tc+s){
        chess(tr+s,tc,dr,dc,s);
    }else{
        board[tr+s][tc+s-1] = newtag;
        chess(tr+s,tc,tr+s,tc+s-1,s);
    }
    //覆盖右下角子棋盘
    if(dr >= tr+s && dc >= tc+s){
        chess(tr+s,tc+s,dr,dc,s);
    }else{
        board[tr+s][tc+s] = newtag;
        chess(tr+s,tc+s,tr+s,tc+s,s);
    }
}

接下来的问题还是有点困难，叫做打印进度问题。

日程安排问题

问题：循环赛有 n=2^k 名选手参加。 设计竞赛日程需满足以下要求：

1）每位选手必须与其他n-1名选手比赛一次；

2）每位玩家每天只能参加一次比赛。

分析，根据上述要求，比赛表可以设计为一个n行n-1列的二维表，其中第i行j列的元素代表本场比赛的选手编号第 i 位选手在第 j 天参加比赛。

使用分而治之的策略，所有参与游戏的玩家可以分为两部分。 n=2^k个玩家的游戏日程可以由n=2^(k-1)个玩家的游戏日程确定。 这种划分会递归进行，直到只剩下两名玩家，通过这种分而治之的策略可以逐步构建游戏时间表。

说白了就是：先默认构造明细表第一行，即0,1,2,3,...然后先对明细表进行划分，将左上角复制到右下角，并将右上角复制到左下角。

第一行初始化我就不细说了，直接让 chess[0][i] = i+1

我们用Excel中的图表来演示一下

代码

/**
 * 将比赛日程表设计成n行n列，表中除了第一列，其他n-1列才是我们要的，数组下标行列都从0开始，第i行j列代表第（i+1）位选手在第j天的对手：
 * 表格初始化会将第一行按1到n一次填充，然后递归填充下面的，用左上角和右上角分别去填充右下角和左下角，因为要是对称矩阵（具体原因好好想想）
 * @param p     表示行序号
 * @param q     表示列序号
 * @param t     表示当前传进函数方格的规模也就是大小
 * @param arr   表格
 */
public static void arrange(int p, int q, int t, int arr[][]){
    if(t>=4){           //如果规模大于4，就继续递归
        arrange(p,q,t/2,arr);
        arrange(p,q+t/2,t/2,arr);
    }
    //填左下角
    for(int i=p+t/2;i