算法设计：第七讲

第第页算法设计：第七讲3.1.3

递归与循环的比较

递归与循环设计的思想不同，但都采纳“从具体到抽象”的设计方法，并且都是解决“重复操作”的机制。递归使一些繁复的问题处理起来简约明白。每个迭代算法原那么上总可以转换成与它等价的递归算法；反之不然。

3.1.3

递归与循环的比较

【例题一】任给十进制的正整数，请从低位到高位逐位输出各位数字。递归实现：循环实现：voidf12(intn)voidf11(intn){{while(n=10)printf(n%10);{print(n%10);if(n10)f12(n/10);n=n/10;}}print(n);}

3.1.3

递归与循环的比较

【比较】(1)时间效率和空间效率，循环要优于递归。时间效率┖log10n┘,但递归需要保存和恢复现场，信息量很大，因此费时。空间效率：循环O(1),递归O(n)(2)就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间(调用和返回均需要额外的时间)与存贮空间(用来保存不同次调用状况下变量的当前值的栈空间)。

3.1.3

递归与循环的比较

【例题二】任给十进制的正整数，请从高位到低位逐位输出各位数字。循环实现：voidf21(intn){intj,i=0,a[16];for(j=i-1;j=0;j--)while(n!=0)print(a[j]);}{a[i]=n%10;i=i+1;n=n/10;}

3.1.3

递归与循环的比较

递归实现：voidf22(intn){if(n10)f22(n/10);printf(n%10);}

3.1.3

递归与循环的比较

【比较】:它们的空间效率是相等的。虽然时间效率有所差别，但递归程序更简约，可读性好。【小结】:递归算法的时间包括递归和回溯两部，当问题需要“后进先出”的操作(即在回溯过程中操作)时，还是用递归算法更有效。

3.1.3

递归与循环的比较

例题1:任何一个正整数可以用2的幂次方表示。例如：137=27+23+20137=2(7)+2(3)+2(0)137=2(2(2)+2(1)+2(0))+2(2(1)+2(0))+2(0)

3.1.3

递归与循环的比较

先不考虑将指数运用2的幂次表示：voidf(intn,intr){if(n==1)/*递归终点*/printf(“2(“,r”)”);else{f(n/2,r+1);if(n%2)printf(“+2(“,r,”)”);}}

3.1.3

递归与循环的比较

考虑将指数运用2的幂次表示：voidf(intn,intr){if(n==1)/*n递归终点*/switch(r){case0:printf(“2(0)”);break;case1:printf(“2(1)”);break;case2:printf(“2(2)”);break;default:printf(“2(“,f(r,0),”)”);}

3.1.3

递归与循环的比较

else{f(n/2,r+1);if(n%2)switch(r){case0:printf(“+2(0)”);break;case1:printf(“+2(1)”);break;case2:printf(“+2(2)”);break;default:printf(“+2(“,f(r,0),”)”);}}

3.1.3

递归与循环的比较

例题2:找出n个自然数(1,2,3,…,n)中r个数的组合。例如，当n=5,r=3时，全部组合为：123124125134135145234235245345total=10{组合的总数}

constitute2(){intn=5,r=3,i,j,k,t;t=0;for(i

=1;i=n-2;i=i+1)for(j=i+1;j=n-1;j=j+1)for(k=j+1;k=n;k=k+1){t=t+1;print(i,j,k);}print('total=',t);}

3.1.3

递归与循环的比较

当要求r为任意小于n的数字时，由于没有掌握循环层数的机制，所以循环算法无能为力。运用递归就可以解决该问题。在运用递归解决时，每个组合中的数据需要从大到小排列，递归设计就是找到大问题与小问题之间的关系。

例如，当n=5,r=3时，全部组合为：555555444344433233223212112111

算法设计

total=10

课后思索：设计算法实现：从n个不同的任意数中，取出r个数的组合。要求：n、n个数及r均从键盘输入。

3.2

算法与数据结构

计算机处理的问题类型可以分为数值型和非数值型的，处理的数据也特别广泛。在解决非数值型问题的时候，不仅仅是问题分析、数学建模和算法设计，还需要设计出合适的数据结构。算法设计的实质：对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法，从而实现对数据的处理。

3.2

算法与数据结构

一个问题可以建立不同的数据结构，可以从以下方面评价这些数据结构：规律结构能否精确的表示数据的3个层次：数据项、数据元素、数据元素之间的关系。规律结构要易于存储实现存储实现方式的选择，要特别留意问题的规模该存储结构是否易于处理功能的实现。是否有利于算法效率的提高

3.2

算法与数据结构

存储结构

连续存储：静态存储：

动态存储：链式存储：

3.2

算法与数据结构

在选取存储结构时权衡因素有：1)基于存储的考虑–对线性表的长度或存储规模难以估量时，不宜采纳顺次表；–链表不用事先估量存储规模，但链表的存储密度较低。

3.2

算法与数据结构

2)基于运算的考虑假如在线性表中常常做的运算是按序号访问数据元素，顺次表优于链表；假如在线性表中常常做插入和删除操作，虽然二者的时间繁复度都是O(n),