算法设计：第七讲_2013

3.1.3

递归与循环的比较

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

3.1.3

递归与循环的比较

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

3.1.3

递归与循环的比较

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

3.1.3

递归与循环的比较

【例题二】任给十进制的正整数，请从高位到低位 逐位输出各位数字。 循环实现： void f21(int n) {int j,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

递归与循环的比较

递归实现： void f22(int n) { if(n>10) f22(n/10); printf(n%10); }

3.1.3

递归与循环的比较

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

3.1.3

递归与循环的比较

例题1:任何一个正整数可以用2的幂次方表示。 例如：137=27+23+20 137=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的幂次表示： void f(int n,int r) { if(n==1) /*递归终点*/ printf(“2(“,r”)”); else {f(n/2,r+1); if(n%2) printf(“+2(“,r,”)”);} }

3.1.3

递归与循环的比较

考虑将指数使用2的幂次表示： void f(int n,int r) { if(n==1) /*n递归终点*/ switch(r) {case 0: printf(“2(0)”);break; case 1:printf(“2(1)”);break; case 2:printf(“2(2)”);break; default:printf(“2(“,f(r,0),”)”); }

3.1.3

递归与循环的比较

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

3.1.3

递归与循环的比较

例题2:找出n个自然数(1,2,3,…,n)中r个数的组合。例如，当n=5,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 {组合的总数}

constitute2() {int n=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时，所有组合为：5 5 5 5 5 5 4 4 4 3 4 4 4 3 3 2 3 3 2 2 3 2 1 2 1 1 2 1 1 1

算法设计

total=10

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

3.2

算法与数据结构

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

3.2

算法与数据结构

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

3.2

算法与数据结构

存储结构

连续存储：静态存储：

动态存储： 链式存储：

3.2

算法与数据结构

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

3.2

算法与数据结构

2)基于运算的考虑 如果在线性表中经常做的运算是按序号访问数据元 素，顺序表优于链表； 如果在线性表中经常做插入和删除操作，虽然二者 的时间复杂度都是O(n),但顺序表是以移动数据元素 为基本操作的；链表是以比较为基本操作，因此链表 优于线性表。

3.2

算法与数据结构

3)基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型， 操作简单。 链表的操作是基于指针的，操作复杂。

本文来源：https://www.bwwdw.com/article/ft61.html