电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

第7章分治算法(C++版)VIP免费

第7章分治算法(C++版)_第1页
1/24
第7章分治算法(C++版)_第2页
2/24
第7章分治算法(C++版)_第3页
3/24
第七章分治算法所谓分治就是指的分而治之,即将较大规模的问题分解成几个较小规模的问题,通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相似。找出各部分的解,然后把各部分的解组合成整个问题的解。1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的:解决子问题所需的工作总量(由子问题的个数、解决每个子问题的工作量决定)合并所有子问题所需的工作量。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+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(lusingnamespacestd;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<y)cout<<"nofind"<m)jc(x,k-1);//在前半中查找}}【例3】一元三次方程求解有形如:ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。提示:记方程f(x)=0,若存在2个数x1和x2,且x1

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

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

您可能关注的文档

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群