信息学集训 | 15 分治算法理论与实战

导读

信息学能够有助于孩子未来工作发展，提升孩子的综合能力。

这一节课我们走进分治算法的世界，了解分治算法的思想，了解分治算法的适用情况，了解分治算法的步骤，并通过几道经典题目来深入领悟分治算法。

1 看个例子

军旗很多人都玩过，从职务上来说，分为：

司令、军长、师长、旅长、团长
营长、连长、排长、工兵

司令如果想把命令传下去，传递给所有的工兵，如果自己传递，那太累了，效率也太低了。

可以怎么办呢？司令可以把命令传递给军长，军长得到消息后，传递给自己下属的所有师长，师长得到消息后传递给自己下属的所有旅长，……，一级一级往下传递消息，直到传递到每一个工兵。

这种做法的思想就是“分而治之”。一级一级往下，分开管理。这就是我们今天要讲的分治法。

2 分治算法理论

分治算法是非常经典的算法，分治算法也是思想，经常和递归算法结合使用！我们今天的一个例题中，就会将分治和递归结合起来，这个算法我们之前也讲过——快速排序算法。

让我们先一起来了解一下分治算法的理论吧！

1 分治算法介绍

所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。二分法也是最常用的分治算法。

2 分治算法适用情况

分治算法并不是无所不能的，分治算法能够使用的场景也有一定的限制：

1、问题必须是可分解的；
2、分解得到的子问题应该是同类型问题；
3、子问题必须相互独立；
4、子问题可以继续分解为更小的子问题。（非强制）
5、最小子问题必须是可解的
6、子问题的解能合并为父问题的解，并最终合并为该问题的解。

前两个限制保证了问题可以分治。如果不能分解或分解得到的子问题完全不同，每种子问题都要单独考虑，这就是枚举算法了。

第三个限制保证了分治的正确性和高效性，如果分解不相互独立，就会重复计算或者错误计算。

第四和第五个限制保证分治后的子问题可解，如果分治后的子问题不可解，就无法合并了。

最后一个限制保证了分治的最终还是为了整体。如果无法合并成为整体，分治就没有意义了。

4 分治算法步骤

分治算法一般要和递归或者循环结合。主要包括三个步骤：

分、治、并

分是指通过递归不断分解直到子问题可解。

治是指可以通过某种算法解决子问题。

并是指将所有子问题的解合并。

下面让我们通过例题来深入领悟吧！

3 分治算法经典例题

本节课的作业，就是复习上面的所有知识，并完成下面两道题目！

1 找数字

一串数字从小到大排列。现在输入一个数n介于最小值和最大值之间，现在输出和n最接近的数。

1、分析

我们举个例子：

1 3 5 7 9 11

然后我们先考虑最特殊的情况，即有两个最接近的数字，例如输入4。一种方法是从前往后依次找或者从后往前依次找。这种思想就是枚举的思想。

但如果数特别多，枚举算法的复杂度为 

当然另外一种情况是查找的就是序列中的，例如我们输入5，我们直接找小于等于5且和5最接近的。然后相等，直接输出5即可。

2、代码

这道题目我们使用递归的方法来实现：

#include<iostream>
using namespace std;

int a[5] = {1,3,5,7,9};

int fun(int l, int r, int n){
  int mid = (l+r)/2;
  if(l+1<r){
if(a[mid] == n) {
cout<<n;
return 0;
}
else if(a[mid] > n) return fun(l,mid,n);
    else return fun(mid,r,n);
  }
  else {
    if(n-a[l] == a[l+1]-n) 
      cout<<a[l]<<" "<<a[l+1]<<endl;
    else if(n-a[l] > a[l+1]-n) 
      cout<<a[l+1]<<endl;
    else cout<<a[l]<<endl;
    return 0;
  }
}

int main(){

  int n;
  cin>>n;

  fun(0,4,n); 

  return 0;
}

大家也可以把数组元素设为输入方式。原理也是一样的。

2 一元三次方程求解

编写一个程序，求解一元三次方程，已知该一元三次方程有三个解，且解的取值范围是从-100到100。现在求解下面方程的解，结果保留两位小数：

a*x^3+b*x^2+c*x+d = 0

输入abcd的值，输出该方程的解。注：输入的方程一定有解。

1、枚举法思想

因为我们知道解在-100到100之间，结果保留两位小数。那我们就从-100到100遍历所有情况。间隔是0.01。

如果x带入恰好让方程为零，那直接输出x即可。

如果方程的解不是精确的，我们就要考虑这几种情况：

第一种情况如下图所示，

如果某一点是方程的解，那该点左右两边的值对应的函数值一个为正，另一个为负。

第二种情况：

这种情况，只有两个解，解两边的函数值都大于0或者都小于0。

第三种情况：

这个时候，方程只有一个解。

因为题目中明确说明，方程有三个解，所以只有第一种情况，也就是说，如果某个点和它后面的点对应的函数值，相乘为负数，那说明，这两个点就非常接近最终结果了。我们输出离x轴最接近的即可。

简单来说，我们可以直接判断y值和x轴的距离，如果小于我们设定的范围，我们就认为它是解。例如y值和x轴的距离小于0.00001。

2、枚举法代码

#include<cstdio> 
#include<iostream>
using namespace std;
double a,b,c,d;
int main()
{
  double x,y;
  cin>>a>>b>>c>>d;
  for (x=-100;x<=100;x+=0.01) {
y = a*x*x*x+b*x*x+c*x+d;
if (y<=0.00001 && y>=-0.00001)
      printf("%.2f ",x); //要保留两位小数 
    }
}

3、分治法思想

如果是分治法，我们就不用遍历所有情况，我们可以从两端开始考虑。折半找。但是会出现问题，因为一元三次方程不是单调的，所以不能直接用二分。

所以我们可以先用枚举，从-100到100，分整数小段，分别计算每一小段的值。然后对于每一小段分别使用二分。

4、分治法代码

按照后面的思想，代码如下：

#include<cstdio> 
#include<iostream>
using namespace std;
double a,b,c,d;

double f(double x)   //将x代入函数
{
  return (a*x*x*x + b*x*x + c*x + d);
}

int main()
{
  for (x=-100;x<=100;x++) { //枚举每一个可能的根
x1=x;x2=x+1; //确定根的可能区间
if (f(x1)==0) printf("%.2f ",x1); //若x1为根，则输出 
else if (f(x1)*f(x2)<0) { //若根在区间[x1，x2]中
      while (x2-x1>=0.001) { //若区间[x1，x2]不满足精度要求，则循环
        xx = (x2+x1)/2; //计算区间[x1，x2]的中间位置
        if ((f(x1)*f(xx))<=0) x2=xx; //若根在左区间，则调整右指针
else x1=xx; //若根在右区间，则调整左指针
} 
printf("%.2f ",x1); //区间[x1，x2]满足精度要求，确定x1为根
}
}
return 0;
}

3 快速排序算法

快速排序是我们前面着重讲的排序算法。我们先来简单回顾一下排序算法的思想，然后再考虑其代码实现。

1、思想

快速排序，就是将序列按照某一个元素分成两部分，例如从小到大，比该元素小的放左边，比该元素大的放右边，然后对于每一个小部分再按照相同的方法排序，直到其两边都只剩下小于等于一个元素。按照其左右关系排好序即可。

2、代码

这里的代码优化了上面的流程，如果有些部分已经从小到大有序，那我们就不用考虑这些部分，只对剩下的无需部分排序即可。

void quickSort(int left,int right){
  int i=left, j=right, mid=a[(left+right)/2];
  while(i<=j) //注意这里要有等号
{
while(a[i]<mid) i++; //在左边找大于等于mid的数
    while(a[j]>mid) j--; //在右边找小于等于mid的数
    if(i<=j){
swap(a[i],a[j]); //交换
i++, j--; //继续找
}
}
if(left<j) qsort(left,j); //分别递归继续排序
  if(i<right) qsort(i,right);
}

6 作业

本节课的作业，就是复习上面的所有知识，并完成下面的题目！

1 取余运算

输入b，p，k的值，求b^p mod k的值。其中b，p，k为长整形数；

​ ​ ​ ​ ​

AI与区块链技术