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

——提高篇C语言程序设计—提高篇第5章递归、共同体和枚举——提高篇内容概述递归共同体枚举——提高篇教学目标掌握递归的概念与应用；牢记共用体变量的定义，并能正确地使用；描述枚举类型的定义及使用方法。——提高篇5.1递归定义所谓“递归”就是允许程序调用自己本身的过程或函数。构成递归需具备的条件1.子问题须与原始问题为同样的事，且更为简单；2.不能无限制地调用本身，须有个出口，化简为非递归状况处理。——提高篇递归不是一种数据结构，而是一种有效的算法设计注意：递归算法必须是逐步有规律简化的，最终要有一个非递归的出口，不能出现无穷调用的情况。——提高篇阶乘的递归定义（1）5！=5×4！（2）4！=4×3！（3）3！=3×2！（4）2！=2×1！（5）1！=1×0！（6）0！=1时当时当1,)!1(0,1!nnnnn——提高篇（a）if（n==0）fact=1；/*定义出口*/else{（b）x=n-1；（c）求出y=x！；/*顺序递推求解*/（d）fact=n*y；/*回溯递推求值*/}程序实现递归阶乘算法的伪程序——提高篇•例1：用递归求阶乘的算法。•longintfact(intn)•{•intx;•longinty;•if(n==0)return1;/*定义递归出口将1返回给fact(0)*/•y=fact(n-1)*n;•return(y);•}•voidmain()•{•longintfn;•fn=fact(5);•printf(\nfn=%ld\n,fn);•}——提高篇longintfact（intn）{intx；longinty；if(n==0)return1；x=n-1；y=fact（x）；return（n*y）；}例1：用递归求阶乘的算法。#includestdio.hvoidmain(){longintfn；fn=fact(5)；printf(”\nfn=%ld”，fn);}——提高篇求解阶乘5!的过程主程序main:fact(5)参数5计算5*fact(4)返回120参数4计算4*fact(3)返回24参数3计算3*fact(2)返回6参数2计算2*fact(1)返回2参数1计算1*fact(0)返回1参数传递结果返回递归调用回归求值参数0直接定值=1返回1——提高篇n=55!5*4!4*3!3*2!2*1!111*22*36*424*5120回推递推递归结束条件n!=1(n=1)n*(n-1)!(n1)——提高篇函数的递归调用递归调用——函数直接或间接调用自身。递归函数——这种调用自身的函数为递归函数。递归算法的设计•具有某种可借用类同自身的子问题描述的性质。•相对于问题来说,子问题将更加简化。•某一有限步的子问题有直接的解存在。——提高篇例2：Hanoi塔假设有三根木桩分别为A、B和C。在木桩A上安置了N个圆盘，由上到下编号为1，2，…N，编号越大的圆盘直径也越大。现需要将A木桩上的N个圆盘借助B木桩移到C木桩上，且必须按照下述移动规则：1.直径较小的圆盘永远置于直径比较大的圆盘上;2.圆盘可任意地由任何一个木桩移到其他的木桩上;3.一次只能移动一个盘子。——提高篇——提高篇汉诺塔(TowerofHanoi)问题的解题思路：如果n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：1.用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上；2.将A柱上最后一个盘子直接移到C柱上；3.用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。——提高篇#includestdio.hvoidHanoi(intn,charx,chary,charz){if(n==1)printf(Movedisk%dfrom%cto%c\n,n,x,z);else{Hanoi(n-1,x,z,y);printf(Movedisk%dfrom%cto%c\n,n,x,z);Hanoi(n-1,y,x,z);}}voidmain(){intnum;charone,two,three;scanf(%d,&num);scanf(%c%c%c,&one,&two,&three);Hanoi(num,one,two,three);}——提高篇5.2共同体一种自定义的数据类型一、共用体数据类型的特点与结构体类似之处：由不同的数据项组成一个整体。与结构体不同之处：占用的内存单元不同。——提高篇二、共用体类型定义定义方式与结构体类型完全相同。把结构体类型中的关键字struct换成union即可。——提高篇例：structmemb{floatv;intn;charc;}stag;stag占内存7个字节的空间unionmemb{floatv;intn;charc;}ustag;utag占的内存空间为100110051007vnc2001vnc200220032004共用体类型变量每次只能存放一个成员的值。——提高篇三、共用体类型变量的引用引用方法同结构体变量：(共用体类型变量名).成员名共用体类型变量的输入输出同结构体类型变量相同。——提高篇例3：#includestdio.hunionmemb{floatv;intn;charc;};voidmain(){unionmembutag;utag.c='T';utag.n=18;utag.v=36.7;printf(%5.1f\n%d\n%c\n,utag.v,utag.n,utag.c);}运行结果：36.71108528333？——提高篇想一想：若改变成员的赋值顺序：utag.v=36.7;utag.c=‘T’;utag.n=18;则运行结果为：0.084T——提高篇构造类型(数组，结构体，共用体)的定义可以嵌套。structpriv{intn;floatf;charc;}unionpubl{intns;floatfs;structprivmud;}spe[5];——提高篇spe为共用体类型数组，每个数组元素所占用的内存单元为：2001mudfsns200220032004200520062007——提高篇5.3枚举一、枚举类型是一种自定义的用标识符表示的集合这个集合自动具有序号——提高篇二、枚举类型的定义1.定义的一般形式enum类型名{标识符1，标识符2，…，标识符n};２．枚举变量的定义──与结构变量类似（1）间接定义例如，enumweekdaysworkday;（2）直接定义例如，enum{Sun,Mon,Tue,Wed,Thu,Fri,Sat}workday;——提高篇3.序号标识符1，标识符2，…，标识符n01n1·自动设置——提高篇·人为设置enum类型名{标识符1=1,标识符2,…,标识符n}例：enumworkday{MON,TUE,WED,THU,FRI};enumworkday{MON=1,TUE,WED,THU,FRI};3012431245——提高篇３．说明（1）枚举型仅适应于取值有限的数据。（2）取值表中的值称为枚举元素，枚举元素是常量。在Ｃ编译器中，按定义的顺序取值0、1、2、...。所以枚举元素可以进行比较，比较规则是：序号大者为大。例如，上例中的Mon=1、Tue=2、……、Fri=5，所以TueMon、Fri最大。（3）枚举元素的值也是可以人为改变的：定义时由程序指定。例如，如果enumweekdays{Sun=７,Mon＝１,Tue,Wed,Thu,Fri,Sat}；则Sun=７，Mon=１，从Tue=2开始，依次增１。——提高篇例4：#includestdio.hvoidmain(){enumweekdays{sun,mon,tue,wed,thu,fri,sat}date;inti;printf(pleaseinputthedate(1-30):);scanf(%d,&i);date=(enumweekdays)((i+4)%7);switch(date){casesun:printf(Sunday\n);break;casemon:printf(Monday\n);break;casetue:printf(Tuesday\n);break;casewed:printf(Wednesday\n);break;casethu:printf(Thursday\n);break;casefri:printf(Friday\n);break;casesat:printf(Saturday\n);break;default:printf(inputerror!);break;}}——提高篇填空题函数f定义如下，计算写出f(f(4))的值是。intf(intx){intk=1;x+=k++;returnx;}练习6——提高篇程序阅读题#includestdio.hintf(intm,intn){if(m%n==0)returnn;elsereturnf(n,m%n);}voidmain(){printf(%d\n,f(840,48));}输出结果为：24练习——提高篇intf1(int,int),f11(int);voidf2(int);voidmain(){inti,j;for(i=0;i5;i++){f2((5-i)*3);for(j=0;j=i;j++)printf(“%3d”,f1(i,j));putchar(’\n’);}}intf1(intm,intn){returnf11(m)/f11(n)/f11(m-n);}intf11(intk){if(k=1)return1;returnk*f11(k-1);}voidf2(intn){inti;for(i=1;i=n;i++)putchar(’’);}111121133114641练习