算法设计与分析_递归与分治

递归算法

1.递归需要有边界条件、递归前进段和递归返回段。
①当边界条件不满足时，递归前进；
②当边界条件满足时，递归返回。
③注意：在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。
2.递归的缺点：
①递归算法解题的运行效率较低。
②在递归调用过程中，系统为每一层的返回点、局部变量等开辟了堆栈来存储。递归次数过多容易造成堆栈溢出等。

集合的全排列问题

``

//产生从元素k～m的全排列，作为前k—1个元素的后缀
void Perm(int list[], int k, int m)
{
	//构成了一次全排列，输出结果
	if(k==m)
	{
		for(int i=0;i<=m;i++)
			cout<<list[i]<<" ";
		cout<<endl;
	}
	else
		//在数组list中，产生从元素k～m的全排列
		for(int j=k;j<=m;j++)
		{
			swap(list[k],list[j]);
			Perm(list,k+1,m);
			swap(list[k],list[j]);
		}
}

整数划分问题

正整数n的划分数p(n)=f(n,n)

正整数n的划分算法
int split(int n,int m)
{
	if(n==1||m==1) return 1;
	else if (n<m) return split(n,n);
	else if(n==m) return split(n,n-1)+1;
	else return split(n,m-1)+split(n-m,m);
}

分治法

1.分治法在每一层递归上都有三个步骤：
①分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
②解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
③合并：将各个子问题的解合并为原问题的解。
2.分治法所能解决的问题一般具有以下几个特征：
①该问题的规模缩小到一定的程度就可以容易地解决；
②该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
③利用该问题分解出的子问题的解可以合并为该问题的解；
④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

选择问题
对于给定的n个元素的数组a[0：n—1]，要求从中找出第k小的元素。
输入
输入有多组测试例。
对每一个测试例有2行，第一行是整数n和k（1≤k＜n≤1000），第二行是n个整数。
输出
第k小的元素

利用快速排序算法的思想，来解决选择问题。
记一趟快速排序后，分解出左子集中元素个数为 nleft,则选择问题可能是以下几种情况之一：
① nleft ＝k﹣1，则分界数据就是选择问题的答案。
②nleft ＞k﹣1，则选择问题的答案继续在左子集中找，问题规模变小了。
③ nleft ＜k﹣1，则选择问题的答案继续在右子集中找，问题变为选择第k-nleft-1 小的数，问题的规模变小了

输油管道问题

算法1：对数组a排序（一般是升序），取中间的元素int n;					//油井的数量
int x;					//x坐标，读取后丢弃
int a[1000];				//y坐标
cin>>n;
for(int k=0;k<n;k++)
	cin>>x>>a[k];
sort(a,a+n);				//按升序排序
//计算各油井到主管道之间的输油管道最小长度总和
int min=0;
for(int i=0;i<n;i++)
	min += (int)fabs(a[i]-a[n/2]);
cout<<min<<endl;

算法2：采用分治策略求中位数
int n;					//油井的数量
int x;					//x坐标，读取后丢弃
int a[1000];				//y坐标
cin>>n;
for (int i=0; i<n; i++)
	cin>>x>>a[i];
int y = select(0, n-1, n/2);		//采用分治算法计算中位数
//计算各油井到主管道之间的输油管道最小长度总和
int min=0;
for(int i=0;i<n;i++)
	min += (int)fabs(a[i]-y);
cout<<min<<endl;