ch6 递归算法(梁)null第6章 递归算法第6章 递归算法主讲:梁宝兰第 6 章 递归算法第 6 章 递归算法主要内容:递归的概念
递归算法的执行过程
递归算法的设计方法
递归过程和运行时栈
递归算法的效率分析
递归算法到非递归算法的转换6.1 递归的概念6.1 递归的概念递归算法
直接或间接调用自身的算法称为递归算法
1、问题的定义是递归的
例:阶乘函数定义
6.1 递归的概念6.1 递归的概念2、问题的解法存在自调用
例:在有序数组a中查找是否存在元素x。
二分查找思想:
在a[low]~a[hight](low为寻找...
null第6章 递归算法第6章 递归算法主讲:梁宝兰第 6 章 递归算法第 6 章 递归算法主要内容:递归的概念
递归算法的执行过程
递归算法的
递归过程和运行时栈
递归算法的效率分析
递归算法到非递归算法的转换6.1 递归的概念6.1 递归的概念递归算法
直接或间接调用自身的算法称为递归算法
1、问
的定义是递归的
例:阶乘函数定义
6.1 递归的概念6.1 递归的概念2、问题的解法存在自调用
例:在有序数组a中查找是否存在元素x。
二分查找思想:
在a[low]~a[hight](low为寻找区域中开始处下标,high则为结束处的下标)寻找是否存在元素x;
若low>high,则不存在x,返回-1;
否则,求出中间元素下标mid=(low+high)/2;
若a[mid]==x ,则查找成功返回mid的值;
若a[mid]>x则在a[low]~a[mid-1]间继续寻找;
若a[mid]
21;则high=mid-1=4,并在a[low]~a[high]中继续查找;第二次比较:low=0,high=4,mid=2;a[mid]<21;则low=mid+1=3,并在a[low]~a[high]中继续查找;第三次比较:low=3,high=4,mid=3;a[mid]=21;则返回mid的值;null在有序表中查找20:
第一次比较:low=0,high=10,mid=5;a[mid]>20;则high=mid-1=4,并在a[low]~a[high]中继续查找;第二次比较:low=0,high=4,mid=2;a[mid]<20;则low=mid+1=3,并在a[low]~a[high]中继续查找;第三次比较:low=3,high=4,mid=3;a[mid]>20;则high=mid-1=2,并在a[low]~a[high]中继续查找;第四次比较:low>high, 20不存在数组中,返回-1;6.1 递归的概念6.1 递归的概念//算法实现
int bin_search (node r[ ],int low,int high,ElemType k)
{
int mid;
if(lowk)
return bin_search (r,low,mid-1,k); //左
else return bin_search (r, mid-1,high,k); //右
}6.2 递归算法的执行过程6.2 递归算法的执行过程//求阶乘的递归程序
int fact(int n)
{ int x,y;
if (n<0) { cout<<“error!”<>m>>n;
cout<<"路径总数:"<< road(m,n);<k) hig=mid-1; //在左子区间中查找
else low=mid+1; //在右子区间中查找
}
return(-1);
}一、 用循环结构的算法消除一、 用循环结构的算法消除//利用二维数组进行递推求解田字表中路径数函数
int road (int m,int n)
{ int r[MaxM][MaxN],count=0;
for(int x=0;x<=m;x++)
{ r[x][0]=1; }
for(int y=0;y<=n;y++)
{ r[0][y]=1; }
for( x=1;x<=m;x++)
for( y=1;y<=n;y++)
{ r[x][y]=r[x-1][y]+r[x][y-1]; }
return r[m][n];
}6.7 设计举例6.7 设计举例6.7.1 一般递归算法设计举例 例6-5 设计一个输出如下形式数值的递归算法。
n n n ... n
......
3 3 3
2 2
1
问题分析:该问题可以看成由两部分组成:一部分是输出一行值为n的数值;另一部分是原问题的子问题,其参数为n-1。当参数减到0时不再输出任何数据值,因此递归的出口是当参数n≤0时空语句返回。6.7 设计举例6.7 设计举例//算法设计:递归算法设计如下:
void Display(int n)
{ int i;
for(i = 1; i <= n; i++)
cout< 0) Display(n - 1); //递归, n<=0为递归出口
}委员会选举委员会选举例6-6 设计求解委员会问题的算法。委员会问题是:从一个有n个人的团体中选举k (k≤n)个人组成一个委员会,计算共有多少种构成方法。
递归算法分析:
设n个人分别为P(1),P(2)……P(n-1),P(n)
若:n=k或k=0则构成方法只有1种
否则:k>1且n>k,则P(1)要么在委员会中,要么不在,则;
当P(1)在委员中时,则需要在P(2)~P(n)中选举k-1个人
当P(1)在委员中时,则需要在P(2)~P(n)中选举k个人委员会选举委员会选举委员会选举委员会选举//委员会选举函数
int comm(n,k)//在n个人种选举k个委员的方法数
{
if (n==k||k==0)
return 1;
else
return comn(n-1,k-1)+comnn(n-1,k);
}null作业
9 10 11 12(1)本章实验本章实验利用非递归算法求解委员会选举问题。The EndThe End
本文档为【ch6 递归算法(梁)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。