2算法基本工具_part1.ppt

*;主要内容;*;*;*;*;*;*;*;*;*;*;算法如下：;*;;*;*;*;*;*;*;*;*;*;*;*;*;*;3 递归设计要点- 整数的分划问题 ;模型建立： ;算法如下：;递归与循环的比较;;;递归算法设计： 1）同上，算法从低位到高位逐位求出各位数字并输出，求个位数字的算式为 n mod 10，下一步则是递归地求n\10的个位数字。 2）当n10时，n为一位数停止递归。 递归算法如下： f2(n) {if(n10) print(n); else { print( n mod 10); f2(n\10);} } ;*;【例3】找出n个自然数(1,2,3,…,n)中r个数的组合。;算法设计1：;算法1如下：;或者? constitute2（） ?{int n=5,r=3,i,j,k,t; ???t=0; ????for(i=1;i=n-r+1; i=i+1) for(j=i+1;j= n-r+2;j=j+1) for(k=j+1;k=n-r+3;k=k+1) ???????????? {t=t+1; print(i,j,k);} ?? print(total=,t); } ;? 在循环算法设计中，对n=5的实例，每个组合中的数据从小到大排列或从大到小排列一样可以设计出相应的算法。但用递归思想进行设计时，每个组合中的数据从大到小排列却是必须的；因为递归算法设计是要找出大规模问题与小规模问题之间的关系。;例如，当n=５,r=3时，所有组合为： ５????? ４????? ３????????? ５????? ４????? ２????????? ５????? ４????? １????????? ５????? ３????? ２????????? ５????? ３????? １????????? ５????? ２????? １????????? ４????? ３????? ２????????? ４????? ３????? １????????? ４????? ２????? １????????? ３????? ２????? １ total=10?? ; 分析n=5,r=3时的10组组合数。 1）首先固定第一个数５，其后就是n=4,r=2的组合数，共6个组合。 2）其次固定第一个数4，其后就是n=3,r=2的组合数，共3个组合。 3）最后固定第一个数3，其后就是n=2,r=2的组合数，共1个组合。 至此找到了“５个数中３个数的组合”与“４个数中２个数的组合、3个数中２个数的组合、2个数中２个数的组合”的递归关系。;则递归算法的三个步骤为： ;递归算法如下： ;分析：算法2递归的深度是r，每个算法要递?? m-k+1次，所以的时间复杂性是O（r*n）。 ;?