分治法思路：
将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
分治算法可以由递归过程来表示，因为分治法就是一种找大规模问题与小规模问题关系的方法，是递归设计的一种具体策略。
步骤
1.分解
将原问题分解为若干规模较小，相互独立，与原问题相同的子问题。
2.解决
若干子问题较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。
3.合并
将已求解的各个子问题的解，逐步合并为原问题的解。
有的问题分解后不需要合并子问题的解，此时就不需要再做第3步了。多数问题需要子问题的解，按照题意使用恰当的方法合并成为整个问题的解。需要具体问题具体分析。
算法框架
分治法的一般算法设计模式如下：
Divide-and-Conquer(int n){
if(n<=n0){
//n为问题规模 ,n0为可解子问题的规模
解子问题;
return(子问题的解);
}
for(i=1;i<=k;i++){
//分解成较小的子问题p1,p2,...,pk
yi=Divide-and-Conquer(|Pi|);//递归解决
}
T=MERGE(y1,y2,...yk);//合并子问题
return(T);//返回问题的解
}
典型二分法
（一）
在算法设计中，每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。
二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。
问题：金块问题
老板有一袋金块（共n块），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块，假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
方法1：逐个查找比较
最简单的方就是逐个的比较查找，算法类似于选择排序。先拿两块进行比较，留下最重的与下一块比较，直到全部比较完毕就找到了最重的金子
完整代码如下：
//金块算法1：逐个查找比较
#include<stdio.h>
int main(){
void maxmin(float a[],int n);//定义查找比较的函数
float a[5]={
5,3,1,9,0};
int i;
maxmin(a,5);
return 0;
}
void maxmin(float a[],int n){
float max,min;
int i;
int count=0;
max=min=a[0];
for(i=1;i<n;i++){
if(max<a[i]) {
//记录每次比较重量最大的金块
max=a[i];
count++;
}
if(min>a[i]){
//记录每次比较重量最小的金块
min=a[i];
count++;
}
}
printf("max=%.2f\nmin=%.2f\ncount=%d\n",max,min,count);//输出结果
}
方法2：分治法（二分法）
1.将数据等分为两组（两组数据可能差1），目的是分别选取其中最大值（最小值）。
2.递归分解直到每组元素的个数不大于2，可简单的找到最大值（最小值）。
3.回溯时将分解的两组解大者取大，小者取小
用分治法可以用较少的比较次数解决问题。
完整代码如下：
//金块算法2:运用递归实现分半查询
#include<stdio.h>
float a[5]={
3,6,9,2,5};
int main(){
void maxmin(int i,int j,float &fmax,float &fmin,int &count);//fmax的地址,fmin的地址
float fmax=0,fmin=0;
int count=0;
maxmin(0,4,fmax,fmin,count);
//传递地址是为了能够把值带出来
printf("fmax=%f\nfmin=%f\ncount=%d\n",fmax,fmin,count);
return 0;
}
void maxmin(int i,int j,float &fmax,float &fmin,int &count){
int mid;
int k;
float lmax,lmin,rmax,rmin;
count++;
//递归结束条件(子问题的解)
//当分到只剩一个数
if(i==j){
fmax=a[i];fmin=a[i];
}
else if(i==j-1){
//(i,j为下标，在分解过程中,i总在左,j总在右 )假如只剩两个数
if(a[i]>a[j]){
fmax=a[i];
fmin=a[j];
}
else if(a[j]>a[i]){
fmax=a[j];
fmin=a[i];
}
}
else{
//其他情况（还剩很多数），则继续递归分解
mid=(i+j)/2;//继续分半
maxmin(i,mid,lmax,lmin,count);
maxmin(mid+1,j,rmax,rmin,count);
if(lmax>rmax) fmax=lmax;
else fmax=rmax;
if(lmin<rmin) fmin=lmin;
else fmin=rmin;
}
}
（二）二分法不相似情况
需要构造与原问题相似子问题。
问题：残缺棋盘
残缺棋盘是一个有2k*2k（k>0）个方格的棋盘，其中恰有一个方格残缺，其中残缺的方格用蓝色阴影表示。
①号
②号
③号
④号
这样的棋盘我们成为“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：
（1）两个三格板不能重叠。
（2）三格板不能覆盖残缺方格，但必须要覆盖其他所有的方格。
解决：
以k=2为例（此时共有16个小方格），用二分法进行分解，得到的是由4个k=1的棋盘组成。
注意这四个棋盘，并不都是与原问题相似的子问题，只有残缺方格在左上角的棋盘时，左上角1号子棋盘与原问题相似。
既然不是与原问题相似的子问题，自然不能够独立求解，所以我们要用巧妙的方法，将2,3，4号子棋盘也转化成与原问题相似的子问题。
我们把紫色阴影覆盖的方格，也看作是残缺方格（我们称之为“伪”残缺方格），这样，每一个子残缺棋盘就都转化为与原问题相似的子问题了。
这样处理过后：
1号子棋盘可以用③号三格板覆盖
2号子棋盘可以用③号三格板覆盖
3号子棋盘可以用②号三格板覆盖
4号子棋盘可以用①号三格板覆盖
这样就覆盖了所有棋盘，满足题意。
如下图所示，粉色阴影是用题中给出的三格板覆盖的位置。
解决了k=2的情况，相当于解决了所有的情况，因为分治算法就是把大规模问题逐步分解成独立且相似的子问题。
思路清晰了之后，我们来解决一般情况
代码分析：
1.数据结构设计 ：我们用一个二维数组Board[][]来模拟棋盘，覆盖残缺棋盘所需要的三格板数目为（size2-1）/3
（size为棋盘的行数或列数）
2.棋盘识别
我们用左上角方格所在行和列来唯一确定一个棋盘，残缺方格或“伪”残缺方格用行号和列号记录。
tr：棋盘左上角方格所在行
td：棋盘左上角方格所在列
dr：残缺方块所在行
dl：残缺方块所在列
3.棋盘填充
将三格板编号1-（size2-1）/3，将每个方格板的编号填充在代表棋盘的数组中，以这种方式表示棋盘被方格板覆盖。
完整代码如下：
#include<iostream>
using namespace std;
int count=0;
int size=1;
int Board[8][8];
int main(){
void Cover(int tr,int tc,int dr,int dc,int size);//填充棋盘的函数
void OutputBoard(int size);
int x,y;
int i;
int k;
//输入棋盘规模
cout<<"请确认棋盘规模，输入k大小（2k×2k）:"<<endl ;
cin>>k;
for(i=1;i<=k;i++) size=size*2;
cout<<"请输入残缺棋子位置（行号，列号）:"<<endl;
cin>>x>>y;
Cover(0,0,x,y,size);
OutputBoard(size);
}
void Cover(int tr,int tc,int dr,int dc,int size){
if(size<2) return;
int t=count++;
int s=size/2;
//如果残缺在左上角
if(dr<tr+s&&dc<tc+s){
Cover(tr,tc,dr,dc,s);
Board[tr+s-1][tc+s]=t;
Board[tr+s][tc+s-1]=t;
Board[tr+s][tc+s]=t;
//返回，填充其他部分
Cover(tr,tc+s,tr+s-1,tc+s,s);
Cover(tr+s,tc,tr+s,tc+s-1,s);
Cover(tr+s,tc+s,tr+s,tc+s,s);
}
//右上角
else if(dr<tr+s&&dc>=tc+s) {
Cover(tr,tc+s,dr,dc,s);
Board[tr+s-1][tc+s-1]=t;
Board[tr+s][tc+s-1]=t;
Board[tr+s][tc+s]=t;
//返回，填充其他部分
Cover(tr,tc,tr+s-1,tc+s-1,s);
Cover(tr+s,tc,tr+s,tc+s-1,s);
Cover(tr+s,tc+s,tr+s,tc+s,s);
}
else if(dr>=tr+s&&dc<tc+s){
Cover(tr+s,tc,dr,dc,s);
Board[tr+s-1][tc+s-1]=t;
Board[tr+s-1][tc+s]=t;
Board[tr+s][tc+s]=t;
//返回，填充其他部分
Cover(tr,tc,tr+s-1,tc+s-1,s);
Cover(tr,tc+s,tr+s-1,tc+s,s);
Cover(tr+s,tc+s,tr+s,tc+s,s);
}
else if(dr>=tr+s&&dc>=tc+s){
Cover(tr+s,tc+s,dr,dc,s);
Board[tr+s-1][tc+s-1]=t;
Board[tr+s-1][tc+s]=t;
Board[tr+s][tc+s-1]=t;
//返回，填充其他部分
Cover(tr,tc,tr+s-1,tc+s-1,s);
Cover(tr,tc+s,tr+s-1,tc+s,s);
Cover(tr+s,tc,tr+s,tc+s-1,s);
}
}
void OutputBoard(int size){
//输出棋盘的内容
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
cout<<Board[i][j];
}
cout<<endl;
}
}
（三）二分法不独立情况
上面的例题，经过二分法分解或经过简单处理后，就得到了相似且相互独立的子问题。对于分解后不独立的情况，主要表现在子问题之间包含公共子问题。
问题：求数列的最大字段和
给定n个元素的整数列（可能为负整数）(斜体标注的都为下标)
a1,a2,…,an.
求形如:ai,ai+1,…aj(i/j=1…n,i<=j)的子段
使其和为最大。当所有整数为负整数时定义其最大字段和为0。
例如当（a1,a2,a3,a4,a5,a6）=(-2,11,-1,13,-5,-2)
最大字段和为i=2,j=4(下标从1开始).
解决：
用二分法将数据分为两组，找出两个子问题的解，两个子问题的解不能简单地得到原问题的解，因为两个子问题的中间还有公共子问题，也就是说两个子问题不能真正的分开。此时再想使用二分法，则需要对公共子问题单独处理。
代码思路：
使用二分法将原问题分解，虽然分解得到的子问题并不相互独立，但是对公共子问题进行单独的处理。
将原问题分解成三部分
（从中间分开）
左边部分
右边部分
中间部分（中间部分单独处理时进行再分）
对左边部分和右边部分：
递归二分，直到分解到只剩一个元素。
对中间部分：
中间部分包含的序列可能是整个序列，把整个序列分为左右两部分，两边各向两侧扩展，最后两边的值相加为中间部分最大字段和。
从中间数据开始向一侧扩展，如果加上元素大于原来的和，则加上此元素，否则跳过这个元素继续扩展。
完整代码如下:
#include<stdio.h>
int len=5;
int main(){
double max_sum(double a[],int left,int right);//left,right是数组下标范围 这是一个递归函数
double max=0;
double a[5]={
-1,-2,0,3,6};
max=max_sum(a,1,5);
printf("%.2f\n",max);
return 0;
}
double max_sum(double a[],int left,int right){
int i;
double s1=0,s2=0;//中间部分左边为s1,中间部分右边为s2
double lefts=0,rights=0;//临时变量标示左边部分的和，和右边部分的和
double left_sum=0;
double right_sum=0;
double center_sum=0;
if(left==right){
//如果这个数为正数就返回，如果为负数就返回0
if(a[left]>0) return (a[left]);
else return (0);
}
else{
//递归求左边部分和右边部分最大和
int center=(left+right)/2;
left_sum=max_sum(a,left,center);
right_sum=max_sum(a,center+1,right);
//对公共子问题进行单独求解
//求中间部分最大和
for(i=0;i<center;i++){
lefts=lefts+a[center-i];
if(lefts>s1) s1=lefts;
rights=rights+a[center+i+1];
if(rights>s2) s2=rights;
}
center_sum=s1+s2;
//比较三部分大小
if(left_sum>right_sum){
if(left_sum>center_sum) return (left_sum);
else return (center_sum);
}
else{
if(right_sum>center_sum) return (right_sum);
else return (center_sum);
}
}
}
非等分分治
问题：选择第k小的数
对于给定的n个元素的数组a[0,n-1],要求从中找出第k小的数。
解决：
通过改写快速排序算法来解决选择问题。
（快速排序算法回忆：首先选择第一个数作为分界数据，将比它小的数据存储在它的左边，将比它大的数据存储在它的右边，它存储在左右两个子集中间。这样左右两个子集就是原问题分解后的独立子问题，再用同样的方法解决这些子问题，直到每个数据只有一个数据，就自然有序了，也就完成了全部数据的排序工作。）
代码思路：
一趟排序中分解出的左子集中元素个数nleft，有以下几种情况：
1. nleft=k-1，则分界数据就是选择问题的答案。
2. nleft>k-1,则选择问题的答案在左子集中找，问题规模变小了。
3. 则选择问题的答案在右子集中找，问题变为寻找第k-nleft-1小的数了，问题规模变小了。（因为随着子区间下标不同，k这个答案下标也会变化）
如果直接用快速排序算法的话，需要把数组全部排序后，再找第k小的数。而分治算法是边排边找，节省时间效率。
下面，将通过快速排序的算法和分治算法的比较，来观察两种方法的不同。
完整代码如下：
#include<stdio.h>
#include<time.h>
#include<math.h>
void swap(int a[],int x,int y);//交换函数
int main(){
//比较两种算法的时间复杂度
//快速排序算法函数
int a[7]={
-1,3,-2,7,6,0,9};
int len=7;//数组长度
int k;
int n=20,i=0;
double time;
int num;
clock_t start,end;
void kuaisupaixu(int a[],int left,int right);
//非等分分治算法
int feidengfenfenzhi(int a[],int len,int k);
//输入k
printf("查找数组中第k小的数，请输入k（0~7）:");
scanf("%d",&k);
/*------------------------------*/
//调用快速排序算法
start=clock();
for(;i<n;i++){
kuaisupaixu(a,0,len-1);//一次运行时间太短，运行100次取平均值
}
end=clock();
time=(double)(end-start)/CLOCKS_PER_SEC/n;
printf("您要查找的第k小的元素为:%d\n",a[k-1]);
printf("函数调用时间为：%.30lf\n",time);
/*------------------------------*/
//调用非等分分治
start=clock();
for(;i<n;i++){
num=feidengfenfenzhi(a,len,k);
}
end=clock();
time=(double)(end-start)/CLOCKS_PER_SEC/n;
printf("您要查找的第k小的元素为:%d\n",num);
printf("函数调用时间为：%.30lf\n",time);
/*------------------------------*/
return 0;
}
void kuaisupaixu(int a[],int left,int right){
int temp=a[left];//把第一个变量设置为分界变量
int i=left;//左指针赋初值
int j=right;//右指针赋初值
if(left==right){
return;
}
if(left==right-1){
if(a[left]>a[right]) swap(a,left,right);
return;
}
//把比分界变量小的数放前面，把比分界变量大的数放在后面 (利用递归把数从小到大排列)
//实现一次排序
while(1&&j>=left&&i<=right){
//右边扫描 (找出小于分界变量的数 )
while(a[j]>=temp&&j>=left){
if(j>i) j=j-1;
else break;
}
//左边扫描(找出大于分界变量的数 )
while(a[i]<=temp&&i<=right){
if(i==j) break;
else i=i+1;
}
if(i==j){
//每轮探测以i==j结束
swap(a,i,left);
break;
}
if(i>=j){
break;
}
swap(a,i,j);
}
//左边递归
if(i!=left){
digui(left,i-1);
}
//右边递归
if(i!=right){
digui(i+1,right);
}
}
int feidengfenfenzhi(int a[],int len,int k){
int digui(int a[],int left,int right,int k);
int i;
if(k<0||k>=len){
printf("您查找的数字不在数组中！\n");
}
else{
return digui(a,0,len-1,k);
}
}
int digui(int a[],int left,int right,int k){
//利用快速排序思路，找到一个基准数（选第一个），小于基准数的放左边，大于基准数的放右边
int i,j;
int p;
int temp;
if(left>=right) return a[left];
i=left,j=right+1;//指定左右指针（因为用do while循环所以j先加一）
temp=a[left];//指定基准数
//把小数放前面，大数放后面（从小到大排列）
//右边循环
//指针指向小于基准数的下标，等待交换
while(1){
do{
i=i+1;
}while(a[i]<temp);//指针向后移动，直到碰到大于temp的数
do{
j=j-1;
}while(a[j]>temp); //指针向前移动，直到碰到小于temp的数
//左边循环
//指针指向大于基准数的下标，等待交换
if(i>=j) break;
swap(a,i,j);
}
//从循环里出来的时候i==j,且以此时指针指向的数为分界点，划分新的区间进行递归
if(j-left+1==k) {
return temp;
}
a[left]=a[j];
a[j]=temp;
if(j-left+1<k){
//查找的数在右边
return digui(a,j+1,right,k-j-1+left);//k的值改变
}
else{
//查找的数在左边
return digui(a,left,j-1,k);
}
}
void swap(int a[],int x,int y){
//传入的x,y为下标
int t;//借助额外变量实现两个数的交换
t=a[x];
a[x]=a[y];
a[y]=t;
}
最后
原创不易，如果对您有帮助，请点个赞再走呀（づ￣3￣）づ╭❤ ～拜托啦
今天的文章数值计算方法迭代法例题_数值计算方法迭代法例题[通俗易懂]分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/77392.html
