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

水亦心 AI与区块链技术

戳一戳!和我一起走进信息学的世界

导读

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


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

往期回顾

【NOIP竞赛/CSP认证】

▶  赛前必看!信息学名师带你复习NOIP竞赛初赛及CSP认证初赛


【信息学精华帖】

▶  收藏!交流会内容全公开,让你陪孩子更好地学习信息学

▶  信息学的万般好处!附C++必备基础知识总结

▶  信息学提高班知识体系详解与家长常见问题解答!让孩子赢在提高班学习的起跑线!

▶  再回首,最全提高班知识总结,做更优秀的自己!

▶  早知道!信息学集训班大揭秘!你想知道的的都在这!


信息学集训

▶  01 温故知新,以更好状态学习数据结构和算法
▶  02 信息学初赛必备计算机知识大串讲
▶  03 位运算与进制初步
▶  04 进制进阶与编码
▶  05 字符串进阶操作
▶  06 栈理论与实战
▶  07 队列理论与实战
▶  08 栈与队列实战
▶  09 算法及其复杂度
▶  10 经典排序算法思想精讲1
▶  11 经典排序算法思想精讲2

▶  12 排序算法分析与sort函数详解

▶  13 枚举算法理论与实战

▶  14 贪心算法理论与实战


【数据结构前导课】

▶  1 温故知新——一篇文章领略信息学C++知识结构
▶  2 披荆斩棘——只学C++,可以做哪些竞赛题
▶  3 运筹帷幄——一篇文章,让指针学起来也很简单!
▶  4 初试锋芒——顺序表写起来也很简单
▶  5 小试牛刀——STL库之vector数组
▶  6 触类旁通——链表基本理论与信息学竞赛必考点
▶  7 更进一步——STL库之List链表

▶  8 知“人”善任——深入理解顺序表和链表的区别与应用


【C++提高班教程】

▶  C++强化 | 01 新学期再出发!温故知新!
▶  C++强化 | 02 继续前行,三大结构终极介绍
▶  C++强化 | 03 一维数组入门
▶  C++强化 | 04 数组越界
▶  C++强化 | 05 一维数组经典应用
▶  C++强化 | 06 一篇文章带你掌握字符数组
▶  C++强化 | 07 二维数组
▶  C++强化 | 08 二维数组经典案例
▶  C++强化 | 09 一篇文章带你探索函数的奥秘
▶  C++强化 | 10 函数进阶必备
▶  C++强化 | 11 这样学递归,才不会觉得难
▶  C++强化 | 12 格式化输入输出与文件操作
▶  C++强化 | 13 结构体入门
  C++强化 | 14 结构体进阶


【C++基础班教程】

▶  C++总结 | 01 程序的世界
▶  C++总结 | 02 输出、换行与注释
▶  C++总结 | 03 变量定义、赋值与运算
▶  C++总结 | 04 算术运算符与赋值运算符
▶  C++总结 | 05 cin语句
▶  C++总结 | 06 程序中的数据类型
▶  C++总结 | 07 数据类型补充
▶  C++总结 | 08 顺序结构
▶  C++总结 | 09 if 和 if-else
▶  C++总结 | 10 if嵌套与逻辑运算符
▶  C++总结 | 11 开关语句switch-case
▶  C++总结 | 12 for循环及其应用
▶  C++总结 | 13 数据范围与数据类型
▶  C++总结 | 14 break与continue
▶  C++总结 | 15 while与do-while
▶  C++总结 | 16 循环嵌套及其应用

1 看个例子

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


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


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


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


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

2 分治算法理论

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


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

1 分治算法介绍

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

2 分治算法适用情况

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


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


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


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


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


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

4 分治算法步骤

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


分、治、并


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


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


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

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

3 分治算法经典例题

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

1 找数字

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


1、分析


我们举个例子:


1 3 5 7 9 11


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


但如果数特别多,枚举算法的复杂度为  。如果采用分治法,我们可以使用二分法,也就是折半查找。折半找到和4最接近且比4小的值,我们记为a,在原序列中a后面是b,也就是比4大的数中最接近4的数,我们计算4-a和b-4,如果相等,我们就输出a和b;如果不相等我们就输出差最小的。


当然另外一种情况是查找的就是序列中的,例如我们输入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与区块链技术

长按二维码关注

文章推荐