算法基本工具(Part1).ppt

算法如下： Divinteger(n, ?m) ?{if ?（n ? ?1 ?or ?m ? ?1 or m n?） ? Error(“输入参数错误”)； /*nm Q(n,m)是无意义的*/ else ?if ?（n ?= ?1 ?or ?m ?= ?1） ? ?return（1）； else ?if （?n ? ?m ） return ?Divinteger(n, ?n) ? else ?if ?（n ?= ?m ） return(1 ?+ ?Divinteger(n, ?n-1)) ? else ? ?return(Divinteger(n,m-1)+Divinteger(n-m,m)); } * 递归与循环的比较 ◆递归与循环都是解决“重复操作”的机制。 ◆递归使一些复杂的问题处理起来简单明了。 ◆就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。 ◆每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然 。 ◆递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。 * 下面通过几个具体的例子来说明循环和递归的差异和优劣。【例1】任给十进制的正整数，请从低位到高位逐位输出各位数字。循环算法设计：从题目中我们并不能获知正整数的位数，再看题目的要求，算法应该从低位到高位逐位求出各位数字并输出。详细设计如下：1）? 求个位数字的算式为 n mod 102）? 为了保证循环体为“不变式”，求十位数字的算式仍旧为n mod 10，这就要通过算式n=n\10，将n的十位数变成个位数。 * 循环算法如下： f1(n) {while(n=10) { print( n mod 10); n=n\10;} print(n); } * 递归算法设计： 1）同上，算法从低位到高位逐位求出各位数字并输出，求个位数字的算式为 n mod 10，下一步则是递归地求n\10的个位数字。 2）当n10时，n为一位数停止递归。 递归算法如下： f2(n) {if(n10) print(n); else { print( n mod 10); f2(n\10);} } * * 【例2】任给十进制的正整数，请从高位到低位逐位输出各位数字。 循环算法设计：本题目中要求“从高位到低位”逐位输出各位数字，但由于我们并不知道正整数的位数，算法还是“从低位到高位”逐位求出各位数字比较方便。这样就不能边计算边输出，而需要用数组保存计算的结果，最后倒着输出。 循环算法如下： f3(n) {int j,i=0,a[16]; while(n=10) { a[i]=n mod 10; i=i+1; n=n\10; } a[i]=n; for(j=i;j=0;j=j-1) print(a[j]); } 递归算法设计： 与f2不同，递归算法是先递归地求n\10的个位数字，然后再求个位数字n的个位数字并输出。这样输出操作是在回溯时完成的。递归停止条件与f2相同为n10。 递归算法如下： f4(n) {if(n10) print(n); else { f4(n\10); print( n mod 10); } } 【例3】找出n个自然数(1,2,3,…,n)中r个数的组合。 例如，当n=５,r=3时，所有组合为： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 ????? ?????????????? total=10???? {组合的总数} 算法设计1： 1）n个数中r的组合，其中每r个数中，数不能相同； 2）任何两组组合的数，所包含的数也不应相同。 例如，５、４、３与３、４、５。为此，约定前一个数应小于后一个数。将上述两条作为约束条件；