第7章 分治算法(c++版)

《第7章 分治算法(c++版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章分治算法所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相似。找出各部分的解，然后把各部分的解组合成整个问题的解。1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：　　解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量决定）合并所有子问题所需的工作量。2、

2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法。3、分治的具体过程：{｛开始｝if①问题不可分②返回问题解else{③从原问题中划出含一半运算对象的子问题1；　　　　　　　　④递归调用分治法过程，求出解1；　　　　　　　　⑤从原问题中划出含另一半运算对象的子问题2；　　　　　　　　⑥递归调用分治法过程，求出解2；　　　　　　　　⑦将解1、解2组合成整个问题的解；}}//结束【例1】快速排序(递归算法)voidqsort(intl,intr){inti,j,mid,p;i=l;j=r;mid=a[(l+

3、r)/2];//将当前序列在中间位置的数定义为分隔数do{while(a[i]mid){j--;}//在右半部分寻找比中间数小的数if(i<=j){//若找到一组与排序目标不一致的数对则交换它们p=a[i];a[i]=a[j];a[j]=p;i++;j--;//继续找}}while(i<=j);//注意这里要有等号if(l

4、法实现二分查找即：有n个已经从小到大排序好的数据，输入一个数m，用二分查找算法，判断它是否在这n个数中。#includeusingnamespacestd;intjc(int,int);intn,a[1000],m;intmain(){intx,y,i;cin>>n;x=1;y=n;for(i=1;i<=n;i++)//输入排序好的数cin>>a[i];cin>>m;//输入要查找的数jc(x,y);//递归过程cout<

5、+y)/2;//取中间位置点if(a[k]==m)cout<<"thennumin"<y)cout<<"nofind"<m)jc(x,k-1);//在前半中查找}}【例3】一元三次方程求解有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），

6、且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。提示：记方程f（x）=0，若存在2个数x1和x2，且x1

7、5的地方有x1和x2两个数，即x1=x-0.0005，x2=x+0.0005。x1和x2间的距离（0.001）满足精度要求（精确到小数点后2位）。若出现如图1所示的两种情况之一，则确定x为f(x)=0的根。有两种方法计算f(x)=0的根x:1．枚举法根据根的值域和根与根之间的间距要求(≥1)，我们不妨将根的值域扩大100倍(-10000≤x≤10000)，依次枚举该区间的每一个整数值x，并在题目要求的精度内设定区间：x1=，x2=。若区间端点的函数值f(x1)和f(x2)异号或者在区间端点x1的函数值f(x1)=0，则

8、确定为f(x)=0的一个根。由此得出算法：输入方程中各项的系数a，b，c，d；for(x=-10000;x<=10000;x++)//枚举当前根*100的可能范围{x1=(x-0.05)/100；x2=(x+0.05)/100；//在题目要求的精度内设定区间if(f(x1)*f(x2)<0

9、

10、f(x1)==0)//若在区间两端的函