算法设计与分析----分治法

算法设计与分析----分治法(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)。

折半查找(二分查询)

思路:

对有序的数值,求中间值,判断中间值是否是要查询的值,

  1. 如果是则输出
  2. 如果不相等,如果中间值小于查找值,则继续再右边查找
  3. 如果不相等,如果中间值大于查找值,则继续再左边查找

代码如下:

//递归和非递归折半查找算法
#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)个硬币,其中有一个假币,且假币 较轻,采用天平秤重方式找到这个假币,并给出操作步骤。

分析:

  1. 首先为每个银币编号,然后将所有的银币等分为两份,放在天平的两边。
  2. 因为假币分量较轻,因此天平较轻的一侧中一定包含假币。
  3. 再将较轻的一侧中银币等分为两份,重复上述做法。
  4. 直到剩下两枚银币,便可用天平直接找出假银币。

二分法代码如下:

#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;
}
上一篇:分治算法——快速排序 原理与C++代码实现(简短)


下一篇:上下界网络流