C语言程序设计-提高篇-第5章 递归共同体

1、C语言程序设计提高篇,第5章 递归、共同体和枚举,内容概述,递归 共同体 枚举,教学目标,掌握递归的概念与应用； 牢记共用体变量的定义，并能正确地使用； 描述枚举类型的定义及使用方法 。,5.1递归,定义 所谓“递归”就是允许程序调用自己本身的过程或函数。 构成递归需具备的条件 1. 子问题须与原始问题为同样的事，且更为简单； 2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。,递归不是一种数据结构，而是一种有效的算法设计,注意：递归算法必须是逐步有规律简化的，最终要有一个非递归的出口，不能出现无穷调用的情况。,阶乘的递归定义,（1）5！=5 4！ （2）4！=4 3！ （3） 3

2、！=3 2！ （4） 2！=2 1！ （5） 1！=1 0！ （6） 0！=1,（a）if（n= =0） fact = 1；/*定义出口*/ else （b） x= n - 1； （c） 求出y=x！； /*顺序递推求解*/ （d） fact = n * y； /*回溯递推求值*/ ,程序实现递归阶乘算法的伪程序,例1：用递归求阶乘的算法。 long int fact(int n) int x; long int y; if (n=0) return 1; /*定义递归出口将1返回给fact(0)*/ y=fact(n-1)*n; return(y); void main() long int

3、 fn; fn=fact(5); printf(nfn=%ldn,fn); ,long int fact（int n） int x； long int y； if (n=0) return 1； x=n-1； y=fact（x）； return（n*y）； ,例1：用递归求阶乘的算法。,#include void main() long int fn； fn=fact(5)； printf(”nfn=%ld”，fn); ,求解阶乘 5! 的过程,主程序 main : fact(5),参数 5 计算 5*fact(4) 返回 120,参数 4 计算 4*fact(3) 返回 24,参数 3 计算

4、 3*fact(2) 返回 6,参数 2 计算 2*fact(1) 返回 2,参数 1 计算 1*fact(0) 返回 1,参数传递,结果返回,递归调用,回归求值,参数 0 直接定值 = 1 返回 1,n=5,5!,5*4!,4*3!,3*2!,2*1!,1,1,1*2,2*3,6*4,24*5,120,回推,递推,递归结束条件,n!=,(n=1) n*(n-1)! (n1),函数的递归调用 递归调用函数直接或间接调用自身。 递归函数这种调用自身的函数为递归函数。,递归算法的设计 具有某种可借用类同自身的子问题描述的性质。 相对于问题来说,子问题将更加简化。 某一有限步的子问题有直接的解存在。

5、,例2：Hanoi塔,假设有三根木桩分别为A、B和C。在木桩A上安置了N个圆盘，由上到下编号为1，2，N，编号越大的圆盘直径也越大。现需要将A木桩上的N个圆盘借助B木桩移到C木桩上，且必须按照下述移动规则： 1. 直径较小的圆盘永远置于直径比较大的圆盘上; 2. 圆盘可任意地由任何一个木桩移到其他的木桩上; 3. 一次只能移动一个盘子。,汉诺塔(Tower of Hanoi)问题的解题思路： 如果 n=1，则将这一个盘子直接从A柱移到C柱上。否 则，执行以下三步： 1.用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上； 2.将A柱上最后一个盘子直接移到C柱上； 3.用A柱做过渡，将B柱上的(

6、n-1)个盘子移到C柱上。,#include void Hanoi(int n,char x,char y,char z) if(n=1) printf(Move disk %d from %c to %cn,n,x,z); else Hanoi(n-1, x, z, y); printf(Move disk %d from %c to %cn,n,x,z); Hanoi(n-1, y, x, z); void main( ) int num; char one,two,three; scanf(%d , ,5.2共同体,一种自定义的数据类型,一、共用体数据类型的特点,与结构体类似之处：由不同

7、的数据项组成一个整体。,与结构体不同之处：占用的内存单元不同。,二、共用体类型定义,定义方式与结构体类型完全相同。,把结构体类型中的关键字struct换成union即可。,例：struct memb, float v;,int n;,char c;, stag;,stag占内存7个字节的空间,union memb, float v;,int n;,char c;, ustag;,utag占的内存空间为, 共用体类型变量每次只能存放一个成员的值。,三、共用体类型变量的引用,引用方法同结构体变量：,(共用体类型变量名).,共用体类型变量的输入输出同结构体类型变量相同。,例3：,#include u

8、nion memb float v; int n; char c; ; void main( ) union memb utag; utag.c=T; utag.n=18; utag.v=36.7; printf(%5.1fn%dn%cn,utag.v,utag.n,utag.c); ,运行结果： 36.7 1108528333 ？,？,想一想：,若改变成员的赋值顺序：,utag.v=36.7;,utag.c=T;,utag.n=18;,则运行结果为：0.0 84 T,构造类型(数组，结构体，共用体)的定义可以嵌套。,struct priv, int n;,float f;,char c;,u

9、nion publ, int ns;,float fs;,struct priv mud;, spe5;,spe为共用体类型数组，每个数组元素所占用的内存单元为：,5.3枚举,一、枚举类型,是一种自定义的用标识符表示的集合,这个集合自动具有序号,二、枚举类型的定义,1. 定义的一般形式,enum 类型名标识符1， 标识符2，标识符n;,枚举变量的定义与结构变量类似 （1）间接定义 例如，enum weekdays workday; （2）直接定义 例如，enum Sun,Mon,Tue,Wed,Thu,Fri,Sat workday;,3. 序号,标识符1， 标识符2，标识符n,0,1,n1,

10、自动设置, 人为设置,enum 类型名标识符1=1, 标识符2, , 标识符n,例：enum workdayMON, TUE, WED, THU, FRI;,enum workdayMON=1, TUE, WED, THU, FRI;,3,0,1,2,4,3,1,2,4,5,说明 （1）枚举型仅适应于取值有限的数据。 （2）取值表中的值称为枚举元素，枚举元素是常量。在编译器中，按定义的顺序取值0、1、2、.。所以枚举元素可以进行比较，比较规则是：序号大者为大。例如，上例中的Mon=1 、Tue=2、Fri=5，所以TueMon、Fri最大。 （3）枚举元素的值也是可以人为改变的：定义时由程序指

11、定。例如，如果enum weekdays Sun=, Mon ,Tue, Wed, Thu, Fri, Sat；则Sun=，Mon=，从Tue=2开始，依次增。,例4： #include void main() enum weekdayssun,mon,tue,wed,thu,fri,satdate; int i; printf(please input the date(1-30):); scanf(%d, ,填空题 函数f定义如下，计算写出f(f(4)的值是 。 int f(int x) int k=1; x+=k+; return x;,练 习,6,程序阅读题 # includeint f(int m, int n) if(m%n=0) return n; else return f(n, m%n); void main() printf(%dn, f(840, 48);,输出结果为： 24,练 习,int f1(int, int), f11(int);void f2(int);void main() int i, j; for(i=0; i5; i+) f2(5-i)*3); for(j=0; j=i; j+) printf(“%3d”, f1(i, j); putchar(n);int f