计算机算法设计 第二章.ppt

文档介绍：计算机算法设计 与分析
第二章递归与分治策略
引言
引言
分治法:将一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,分而治之。
注意:要保证分割出来的小问题每个都可解!
递归的概念
递归算法:直接或间接的调用自己的算法。
int max(int a, int b)
{if(a>=b) return a;
else return b;}
void main()
{ int a=3,b=5,c;
c=max(a,b);
printf(“%d”,c);}
int fac(int n)
{
if(n==0) return 1;
return n*fac(n-1);
}
递归的概念
优点:
符合人们解决问题的****惯。
有些数据结构本身具有递归的特性,二叉树。
使算法简洁,容易理解和分析。
递归的概念
例2-1 阶乘函数
int fac(int n)
{
if(n==0) return 1;
return n*fac(n-1);
}
1、初始值:每个递归
程序必须要初始值,
它是程序的出口。
2、自己调用自己的
时候,必须用较小的
函数值表示较大的函
数值。
递归的概念
例2-1 i数列
int i(int n)
{
if (n<=1) return1;
return i(n-1)+i(n-2);
}
递归的概念
注意:并非一切递归函数都可以用非递归方式定义。
双递归函数(函数及它的一个变量是由函数自身定义的)——Ackerman函数。
递归的概念——排列
记R={r1,r2,…,rn}是要排列的n个元素;如:R={1,2,3}
Ri=R-{ri},如: R1=R-{r1}=R-{1}={2,3}
Perm(X)表示X集合中的元素全排列。如: Perm(R)
( ri)Perm(X)表示在每个排列前加上一个前缀ri ,
如: (r1)Perm(R1)
递归的概念——排列
排列问题:
当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素;
当n=2时, Perm(R)由(r1) Perm(R1),…, (rn) Perm(Rn)构成。
…
if(k==m)
{ for(int i=0;i<=m;i++)
cout<<list[i]; cout<<endl;} //最后的排列结果
else
for(int i=k;i<=m;i++) //选择前缀
{ swap(list[k],list[i]);
perm(list,k+1,m);
swap(list[k],list[i]); //保证数列为最初的状态
}