算法设计与分析----分治法（C++）
一、分治法
1、定义
对于一个规模为n的问题：若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
2、特征
（1）该问题的规模缩小到一定的程度就可以容易地解决。
（2）该问题可以分解为若干个规模较小的相同问题。
（3）利用该问题分解出的子问题的解可以合并为该问题的解。
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3、分治法的思路
（1）分解成若干个子问题：注意可以分，与原问题形式相同的子问题
（2）求解子问题：若规模小，直接求，否则子问题规模还是比较大的话，用递归地求解。
【所谓递归求解方法是一致的】
（3）合并子问题：将各个子问题的解合并为最终的所需要的原答案。
4、排序问题
快速排序
解释：快速排序是对冒泡法排序的一种改进
基本思想：
（1）通过一趟排序要将排序的数据分割成独立的两部分
（2）其中一部分的所有数值要都比另外一部分的所有数据都要小
【一边全是小的】【另外一边全是大的】
（3）然后再按照此方法对这2部分的数据分别在进行快速排序
（4）整个排序过程可以递归进行，用以达到整个数值的排序
案例
例如，对于{2，5，1，7，10，6，9，4，3，8}序列
代码如下：
#include <stdio.h>
void disp(int a[],int n) //输出a中所有元素
{ int i;
for (i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
int Partition(int a[],int s,int t) //划分算法
{ int i=s,j=t;
int tmp=a[s]; //用序列的第1个记录作为基准
while (i!=j) //从序列两端交替向中间扫描,直至i=j为止
{ while (j>i && a[j]>=tmp)
j--; //从右向左扫描,找第1个关键字小于tmp的a[j]
a[i]=a[j]; //将a[j]前移到a[i]的位置
while (i<j && a[i]<=tmp)
i++; //从左向右扫描,找第1个关键字大于tmp的a[i]
a[j]=a[i]; //将a[i]后移到a[j]的位置
}
a[i]=tmp;
return i;
}
void QuickSort(int a[],int s,int t) //对a[s..t]元素序列进行递增排序
{ int i;
if (s<t) //序列内至少存在2个元素的情况
{ i=Partition(a,s,t);
QuickSort(a,s,i-1); //对左子序列递归排序
QuickSort(a,i+1,t); //对右子序列递归排序
}
}
int main()
{ int n=10;
int a[]={2,5,1,7,10,6,9,4,3,8};
printf("排序前:"); disp(a,n);
QuickSort(a,0,n-1);
printf("排序后:"); disp(a,n);
}
**【算法分析】**快速排序的时间主要耗费在划分操作上，对长度为n的区间进行划分，共需n-1次关键字的比较，时间复杂度为O(n)。
归并排序
基本思路
（1） 将所有的数据一分为二（分成2部分）
注意： 如果数据的个数是偶数个，则刚好可以均分为2部分
如果数据的个数是奇数个，则只能分成一边多一边少
【 定 左多右少？还是左少右多？】
（2） 继续分，把左边的部分再分成2部分，把右边的部分再分成2部分
（3） 重复分下去，最后剩下的每次只有1个数值
（4） 归：每次2组数据合并为1组数据，并且合并后的数组是从小到大的。
案例
例如，对于{2，5，1，7，10，6，9，4，3，8}序列
代码如下：
#include <stdio.h>
#include <malloc.h>
void disp(int a[],int n) //输出a中所有元素
{ int i;
for (i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void Merge(int a[],int low,int mid,int high)
//将a[low..mid]和a[mid+1..high]两个相邻的有序子序列归并为一个有序子序列a[low..high]
{ int *tmpa;
int i=low,j=mid+1,k=0; //k是tmpa的下标,i、j分别为两个子表的下标
tmpa=(int *)malloc((high-low+1)*sizeof(int)); //动态分配空间
while (i<=mid && j<=high) //在第1子表和第2子表均未扫描完时循环
if (a[i]<=a[j]) //将第1子表中的元素放入tmpa中
{ tmpa[k]=a[i];
i++;k++;
}
else //将第2子表中的元素放入tmpa中
{ tmpa[k]=a[j];
j++;k++;
}
while (i<=mid) //将第1子表余下部分复制到tmpa
{ tmpa[k]=a[i];
i++;k++;
}
while (j<=high) //将第2子表余下部分复制到tmpa
{ tmpa[k]=a[j];
j++;k++;
}
for (k=0,i=low;i<=high;k++,i++) //将tmpa复制回a中
a[i]=tmpa[k];
free(tmpa); //释放tmpa所占内存空间
}
void MergePass(int a[],int length,int n) //一趟二路归并排序
{ int i;
for (i=0;i+2*length-1<n;i=i+2*length) //归并length长的两相邻子表
Merge(a,i,i+length-1,i+2*length-1);
if (i+length-1<n) //余下两个子表,后者长度小于length
Merge(a,i,i+length-1,n-1); //归并这两个子表
}
void MergeSort(int a[],int n) //二路归并算法
{ int length;
for (length=1;length<n;length=2*length)
MergePass(a,length,n);
}
int main()
{ int n=10;
int a[]={2,5,1,7,10,6,9,4,3,8};
printf("排序前:"); disp(a,n);
MergeSort(a,n);
printf("排序后:"); disp(a,n);
}
【算法分析】对于上述二路归并排序算法，当有n个元素时，需要[log2n]趟归并，每一趟归并，其元素比较次数不超过n-1，元素移动次数都是n，因此归并排序的时间复杂度为O(nlog2n)。
5、查找问题
查找最大和次大元素
**【问题描述】**对于给定的含有n元素的无序序列，求这个序列中最大和次大的两个不同的元素。
例如：（2, 5, 1, 4, 6, 3），最大元素为6，次大元素为5。
代码如下：
#include <stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 99999 //表示最大的整数
void solve(int a[],int low,int high,int &max1,int &max2)
{
if (low==high) //区间只有一个元素
{
max1=a[low];
max2=-INF;
}
else if (low==high-1) //区间只有两个元素
{
max1=max(a[low],a[high]);
max2=min(a[low],a[high]);
}
else
{
int mid=(low+high)/2;
int lmax1,lmax2;
solve(a,low,mid,lmax1,lmax2); //左区间求lmax1和lmax2
int rmax1,rmax2;
solve(a,mid+1,high,rmax1,rmax2); //右区间求lmax1和lmax2
if (lmax1>rmax1)
{
max1=lmax1;
max2=max(lmax2,rmax1); //lmax2,rmax1中求次大元素
}
else
{
max1=rmax1;
max2=max(lmax1,rmax2); //lmax1,rmax2中求次大元素
}
}
}
int main()
{
int a[]={5,2,1,4,3};
int n=sizeof(a)/sizeof(a[0]);
int max1,max2;
solve(a,0,n-1,max1,max2);
printf("max1=%d,max2=%d\n",max1,max2);
}
**【算法分析】**对于solve(a，0，n-1，max1，max2)调用，其比较次数的递推式为：
T(1)=T(2)=1
T(n)=2T(n/2)+1 //合并的时间为O(1)
可以推导出T(n)=O(n)。
折半查找（二分查询)
思路：
对有序的数值，求中间值，判断中间值是否是要查询的值，
- 如果是则输出
- 如果不相等，如果中间值小于查找值，则继续再右边查找
- 如果不相等，如果中间值大于查找值，则继续再左边查找
代码如下：
//递归和非递归折半查找算法
#include <stdio.h>
int BinSearch(int a[],int low,int high,int k) //拆半查找算法
{ int mid;
if (low<=high) //当前区间存在元素时
{ mid=(low+high)/2; //求查找区间的中间位置
if (a[mid]==k) //找到后返回其物理下标mid
return mid;
if (a[mid]>k) //当a[mid]>k时,在a[low..mid-1]中递归查找
return BinSearch(a,low,mid-1,k);
else //当a[mid]<k时,在a[mid+1..high]中递归查找
return BinSearch(a,mid+1,high,k);
}
else return -1; //若当前查找区间没有元素时返回-1
}
int BinSearch1(int a[],int n,int k) //非递归拆半查找算法
{ int low=0,high=n-1,mid;
while (low<=high) //当前区间存在元素时循环
{ mid=(low+high)/2; //求查找区间的中间位置
if (a[mid]==k) //找到后返回其物理下标mid
return mid;
if (a[mid]>k) //继续在a[low..mid-1]中查找
high=mid-1;
else //a[mid]<k
low=mid+1; //继续在a[mid+1..high]中查找
}
return -1; //若当前查找区间没有元素时返回-1
}
int main()
{ int n=10,i;
int k=6;
int a[]={1,2,3,4,5,6,7,8,9,10};
i=BinSearch(a,0,n-1,k);
if (i>=0) printf("a[%d]=%d\n",i,k);
else printf("未找到%d元素\n",k);
}
**【算法分析】**折半查找的主要时间花在元素比较上，所以算法的时间复杂度为O(log2n)。
二、分治法实验
1、实验一 求解查找假币问题
【问题描述】编写一个实验程序查找假币，有N (N>3)个硬币，其中有一个假币，且假币 较轻，采用天平秤重方式找到这个假币，并给出操作步骤。
分析：
- 首先为每个银币编号，然后将所有的银币等分为两份，放在天平的两边。
- 因为假币分量较轻，因此天平较轻的一侧中一定包含假币。
- 再将较轻的一侧中银币等分为两份，重复上述做法。
- 直到剩下两枚银币，便可用天平直接找出假银币。
二分法代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 100
int a[MAX];
int n;
int SUM(int low,int high){
int sum=0;
for(int i=low;i<=high;i++){
sum+=a[i];
}
return sum;
}
int solve(int low,int high){
if(low==high){
return low;
}
if(low==high-1){
if(a[low]<a[high]) return low;
else return high;
}
int mid=(low+high)/2;
int sum1,sum2;
if((high-low+1)%2==0){
sum1=SUM(low,mid);
sum2=SUM(mid+1,high);
printf("硬币%d-%d和硬币%d-%d称重一次:",low,mid,mid+1,high);
}
else {
sum1=SUM(low,mid-1);
sum2=SUM(mid+1,high);
printf("硬币%d-%d和硬币%d-%d称重一次:",low,mid-1,mid+1,high);
}
if(sum1==sum2) {
printf("两者重量相同\n");
return mid;
}
else if(sum1<sum2){
printf("前者重量轻\n");
if((high-low+1)%2==0) return solve(low,mid);
else return solve(mid+1,high);
}
else {
printf("后者重量轻\n");
return solve(mid+1,high);
}
}
int main(){
int n=12;
for(int i=0;i<12;i++){
a[i]=2;
}
srand((unsigned)time(NULL));
a[rand()%n]=1;
printf("求解过程：");
printf("硬币%d是假币\n",solve(0,n-1));
}
三分法代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 102
int a[MAX];
int n;
int SUM(int low,int high){
int sum=0;
for(int i=low;i<=high;i++){
sum+=a[i];
}
return sum;
}
int solve(int low,int high){
int sum1,sum2;
if(low==high){
return low;
}
if(low==high-1){
if(a[low]<a[high]) return low;
else return high;
}
else if(low==high-2){
printf("硬币%d和硬币%d称重一次:",low,low+1);
sum1=a[low];
sum2=a[low+1];
if(sum1<sum2){
printf("硬币%d重量轻\n",low);
return low;
}
else if(sum1>sum2) {
printf("硬币%d重量轻\n",low+1);
return low+1;
}
else {
printf("两者重量相同\n");
return low+2;
}
}
int len=(high-low+1)/3;
int mid1=low+len-1;
int mid2=mid1+len;
sum1=SUM(low,mid1);
sum2=SUM(mid1+1,mid2);
printf("硬币%d-%d和硬币%d-%d称重一次:",low,mid1,mid1+1,mid2);
if(sum1<sum2){
printf("前者重量轻\n");
return solve(low,mid1);
}
else if(sum1>sum2) {
printf("后者重量轻\n");
return solve(mid1+1,mid2);
}
else {
printf("两者重量相同\n");
return solve(mid2+1,high);
}
}
int main(){
int n=120;
for(int i=0;i<n;i++){
a[i]=2;
}
srand((unsigned)time(NULL));
a[rand()%n]=1;
printf("求解过程：");
printf("硬币%d是假币\n",solve(0,n-1));
}
3、实验二 求解逆序数问题
【问题描述】给定N个整数Ai以及一个正整数C，问其中有多少对i、j满足Ai-Aj=C
【输入描述】第1行输入两个空格隔开的整数N和C，第2~N+1行每行包含一个整数Ai
【输出描述】输出一个数表示答案
输入样例:
5 3
2
1
4
2
5
输出样例:
3
分析：
满足Ai-Aj=C，即满足Ai=Aj+C
首先，对序列进行递增排序。把Aj(0≤j＜N)依次与Ai(j<i<n)进行循环比较，若Ai=Aj+C，则计数器count加1；若Ai>Aj+C，因为元素是递增排序，所以Ai后续的元素均大于Aj和C相加后的和，因此使用break结束本次循环比较，开始下一次比较。最后返回count
代码如下：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int f(vector<int> ve, int c) {
sort(ve.begin(), ve.end() - 1);
int count = 0;
int n = ve.size();
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(ve[j] == ve[i] + c)
count++;
else if(ve[j] > ve[i] + c)
break;
}
}
return count;
}
int main() {
int n,c;
cout <<"输入n值为：" ;
cin >> n;
cout <<"输入c值为：";
cin >> c;
int a[n];
cout <<"输入i值为："<<endl;
for(int i = 0; i < n; i++)
cin >> a[i];
vector<int> ve(a, a+n);
cout <<"输出结果为："<< f(ve, c);
return 0;
}