为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

ch6 递归算法(梁)

2013-01-01 30页 ppt 337KB 22阅读

用户头像

is_346787

暂无简介

举报
ch6 递归算法(梁)null第6章 递归算法第6章 递归算法主讲:梁宝兰第 6 章 递归算法第 6 章 递归算法主要内容:递归的概念 递归算法的执行过程 递归算法的设计方法 递归过程和运行时栈 递归算法的效率分析 递归算法到非递归算法的转换6.1 递归的概念6.1 递归的概念递归算法 直接或间接调用自身的算法称为递归算法 1、问题的定义是递归的 例:阶乘函数定义 6.1 递归的概念6.1 递归的概念2、问题的解法存在自调用 例:在有序数组a中查找是否存在元素x。 二分查找思想: 在a[low]~a[hight](low为寻找...
ch6  递归算法(梁)
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: 第一次比较:low=0,high=10,mid=5;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,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索