程序设计基础6反猜数游戏C语言教学课件

1、第6部分 反猜数游戏何光宇，2010.61 复习2 补充知识：栈、函数调用机理与递归3 反猜数游戏教学重点C语言学习需要掌握三个方面内容：C语言知识编程技能：使用Visual C+，查找帮助调试排除常见错误等分析问题和解决问题能力1 复习C语言知识解题方法2.1 栈2.2 基于栈的函数调用机理2.3 递归2.4 栈与递归2.5 递归与循环2 栈、函数调用机理与递归栈: 一种”后进先出”数据结构。操作系统用其为变量进行内存空间分配.开始调用时实参被压入堆栈(push),供子程序使用;调用结束后参数被弹出,堆栈恢复到原有位置.2.1 栈1.调用前堆栈位置堆栈2.调用时，压入参数后, 堆栈位置(实参

2、值即传递给了形参）3. 调用结束后堆栈位置主调函数被调函数基于栈的函数调用过程：1 开始调用时，参数值被压入栈（参数值被传递到被调函数）2 在栈中为被调函数使用变量分配内存空间3 执行被调函数（栈中变量值相应改变）4 被调函数执行完毕，分配空间收回，栈恢复到调用前位置5 返回值被赋值给相应变量（如果没有赋值语句，则返回值被抛弃）2.2 基于栈的函数调用机理递归是指一个函数除了可调用其它函数外，还可以直接或间接地调用自身递归反映的思想：可以将问题转化为一个弱一些、与自身相似的问题，再予以求解是计算机思维中非常重要的一类求解问题方法举例：n！ = (n-1)! * n要点：递归关系、递归终止条件2

3、.3 递归 double factorial(int n) if (n=1) return 1; return n*factorial(n-1); 设计要点：找出递归方程式和递归终止条件递归方程式：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。N! = N*(N-1)!递归终止条件：所描述问题的最简单情况，它本身不再使用递归的定义。N=1递归方法只需少量的步骤就可描述出解题过程所需要的多次重复计算，大大地减少了算法的代码量栈是一种应用范围广泛的数据结构，适用于各种具有“后进先出”特性的问题 函数调用利用栈来完成递归是函数调用特殊形式，同样利用栈来实现2.4 栈与递归递归调用过程中

4、调用关系示例过程A1在其过程体的某一处调用过程A2，A2以在其过程体的某一处调用过程A3，A3不调用其他过程。当过程A1执行到的r处时，它自己实际上被挂起来，而被调用过程A2开始运行。一直等到A2执行完毕这后才返回过程A1的r1处继续执行A1剩下部分。 在过程A2的上述运行中，由于调用了A3，A2同样在t处挂起并一直等到A3执行结束后返回t1处才能继续执行后继语句。 相应的工作栈状态变化 每遇到一个过程调用便立刻将相应的返回位置(及其它有用的信息)进栈；每当一被调用过程执行结束时，工作栈栈顶元素下好是此过程的返回位置。 2.5 递归与循环的比较 递归与循环都是解决“重复操作”的机制。递归使一些

5、复杂的问题处理起来简单明了。就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然 。递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。【例】任给十进制的正整数，请从高位到低位逐位输出各位数字。循环算法设计： 本题目中要求“从高位到低位”逐位输出各位数字，但由于我们并不知道正整数的位数，算法还是“从低位到高位”逐位求出各位数字比较方便。 这样就不能边计算边输出，而需要用数组保存计算

6、的结果，最后倒着输出。循环算法如下：void f3(int n) int j,i=0,a16; while(n=10) ai=n % 10; i=i+1; n=n/10; ai=n; for(j=i;j=0;j=j-1) printf(“%d”,n);递归算法设计： 与f2不同，递归算法是先递归地求n/10的个位数字，然后再求个位数字n的个位数字并输出。这样输出操作是在回溯时完成的。递归停止条件与f2相同为n10。递归算法如下：void f4(n) if(n10) print(“%d”,n); else f4(n/10); print(”%d”, n % 10); 递归是一种强有力的算法设计方

7、法。递归是一种比循环更强、更好用的实现“重复操作”的机制。因为递归不需要编程者（算法设计者）自己构造“循环不变式”，而只需要找出递归关系和最小问题的解。递归与数学归纳法递归非递归程序可读性易难代码量大小小大时间长短占用空间大小适用范围广窄设计难度易难游戏者想四个任意数字，让计算机来猜这四个数。如果计算机猜中或游戏者给出的答案为44， 则程序结束解题思路：列出求解问题步骤(分析问题，列出步骤)对难以求解子问题先抽象，确定要做什么。待其他子问题解决后，再来分析解决此问题。3 反猜数游戏步骤：1 打印游戏规则2 提示：游戏者想好四个数，按某个键继续3 进行猜测4 提示游戏者评价猜测结果5 如果猜测结

8、果是40，则打印胜利标志,程序结束6 如果猜测结果是44，则打印放弃标志,程序结束7 返回第3步进行猜测正向，根据每次猜测结果，确定猜测结果应该是什么？逆向：（基于枚举的搜索）列出所有可能答案在所有可能结果中选一个给猜数者根据猜数者反馈，对所有可能答案进行筛选1 打印游戏规则2 提示：游戏者想好四个数，按某个键继续3 列出所有可能答案4 在所有可能结果中选一个给猜数者5 提示游戏者评价猜测结果6 如果猜测结果是40，则打印胜利标志,程序结束7 如果猜测结果是44，则打印放弃标志,程序结束8 根据游戏者评价猜测结果，对可能结果进行筛选9 返回第3步细化后问题求解思路难点1：如何列出所有可能答案难

9、点2：在所有可能结果中选一个给猜数者难点3：如何根据猜数者所猜答案，对可能结果进行筛选进一步思考：将所有数字都猜一次，看哪个数字所需的猜数次数最多？哪个数字所需的猜数次数最少。分析原因，找出所需猜数次数最少的猜数方法。2.1 早期程序设计方法2.2 结构化程序设计方法2.3 面向对象程序设计方法2.4 反猜数游戏2 结构化程序设计与面向对象编程29早期的程序设计方法追求程序的高效率，编程过份依赖技巧，而不注重所编写程序的结构，也就是没有固定程序设计方法的时期。程序的可读性、可重用性都很差。其中一个典型问题是频繁使用goto语句。虽然这种方法存在很多问题，但对于单人完成较为简单的任务，事实上还是

10、经常被采用的。2.1 早期的程序设计方法30结构化方法出现在70年代中期，我们可以这样理解它：结构化程序设计方法是从程序要实现的功能的角度出发的。一般按照自顶向下、逐步求精的方式，将程序要完成的功能逐级划分成许多小的功能模块，象搭积木一样搭起来。这些小的功能模块最终都可以转化成三种基本控制结构的组合。所谓的功能可以理解为对数据的操作。在程序实现中，特定的功能或功能模块一般用函数来实现，它们要对特定的数据进行操作。2.2 结构化程序设计方法31结构化设计方法的特点结构化程序设计方法的主要技术是自顶向下、逐步求精，采用单入口、单出口的控制结构自顶向下是一种分解问题的技术，逐步求精指结构化程序的连续

11、分解，最终成为下面三种基本控制结构的组合三种基本控制结构：顺序、分支、循环32分支结构语句1语句2语句3条件语句2语句1语句1语句2顺序结构循环结构33例：从键盘输入一个学生的信息（包括姓名、年龄、性别、学号等）和一个老师的信息（包括姓名、年龄、性别、是否授课等），然后将信息输出到屏幕。一个简单的例子34分析：根据需求（题目要求），我们可以把问题划分为两个功能模块，一个是输入模块，一个是输出模块，做完了输入模块，再做输出模块。再具体考虑每个模块如何实现（逐步求精）。我们用C语言来写，参看下面的代码：35/ void main()/ 主函数开始/ 声明用于存储学生信息的变量char strStu

12、dentName20;/ 学生姓名int nStudentAge;/ 学生年龄char cStudentSex;/ 学生性别int nStudentNumber; / 学生学号/ 声明用于存储老师信息的变量char strTeacherName20;/ 老师姓名int nTeacherAge;/ 老师年龄char cTeacherSex;/ 老师性别int nIsTeaching; / 是否授课/ 输入模块GetStudentInfo();/ 输入学生信息GetTeacherInfo();/ 输入老师信息/ 输出模块PrintStudentInfo();/ 输出学生信息PrintStudent

13、Info();/ 输出老师信息描述学生的数据描述老师的数据函数函数36上面的例子中，我们可以进一步将属于学生和老师的变量放入结构中。这样可以在一定程度上完成对数据的封装。但在结构化程序设计中，数据与对其进行操作的函数仍是分离的。/ 声明学生结构Studentstruct Studentchar strStudentName20;/ 学生姓名int nStudentAge;/ 学生年龄char cStudentSex;/ 学生性别int nStudentNumber; / 学生学号;/ 声明老师结构Teacherstruct Teacherchar strTeacherName20;/ 老师姓名

14、int nTeacherAge;/ 老师年龄char cTeacherSex;/ 老师性别int nIsTeaching; / 是否教书;3738问题：函数用于完成一定的功能，它们都是针对特定的数据进行操作的。那么我们能不能以特定的数据为中心，将数据与对其进行操作的函数封装起来呢？392.3面向对象程序设计方法面向对象程序设计出现在80年代中后期面向对象程序设计是建立在结构化程序设计基础上的，但它不再是从功能入手，而是从对象（人、地方、事情等）入手面向对象程序设计以类作为构造程序的基本单位，它具有封装、数据抽象、继承、多态等特点40简单地说，对象就是现实世界中的各种实体，包括人、地点和事物等。

15、例如，桌子、椅子、教室、学生、老师、电话、汽车等等。一般都要从属性和行为两个方面来对它们加以描述。在这里，我们认为对象和对象的实例是同一个概念。什么是对象？41对象具有的一些特征称为属性，以一个人为例，他的姓名、年龄、身高、体重等可以作为他的属性。这些属性会有其对应的值，一般至少会有一项区别于其它对象，它们在程序设计中对应的是一定的数据。为了达到目的，对象必须提供的功能（或必须提供的服务）称为对象的行为，在程序设计中对应一定的方法（函数）。属性和行为42类描述了一组具有相同属性（数据元素）和相同行为（函数）的对象。类的数据成员是对对象属性的抽象，类的函数成员是对对象行为的抽象，而类本身就是对对

16、象的抽象。 可以理解为一种扩充的数据类型，既定义了如何存储数据，也定义了如何对数据进行操作。什么是类？43class Student/ Student类的声明public: / 公有成员Student();/ 构造函数Student();/ 析构函数char*GetName();/ 查询姓名intGetAge();/ 查询年龄charGetSex();/ 查询姓名intGetNumber();/ 查询学号boolSetName(char* n);/ 设置姓名boolSetAge(int age);/ 设置年龄boolSetSex(char* s);/ 设置性别boolSetNumber(int

17、 num);/ 设置学号protected: / 保护成员charm_strName20;/ 姓名，字符串数组intm_nAge;/ 年龄，整型charm_cSex;/ 性别，字符型intm_nNumber;/ 学号，整型;例：C+中类的声明Student类成员函数成员函数成员变量44Student A;/ 声明Student的对象AA.SetName(“张三”);/ 设置A的名字A.SetAge(20);/ 设置A的年龄例：C+中类使用4546总的来说，结构化程序设计方法是一种模块化程序设计方法，它在解决问题时是以功能为中心的，一定的功能模块虽然也作用于特定的数据，但它们并没有被封装在一起。

18、面向对象程序设计方法则是以对象为中心来解决问题的。属于同种对象的属性（数据）和服务（功能）被抽象出来封装到一起。47简单地说，对象就是现实世界中的各种实体，包括人、地点和事物等。例如，桌子、椅子、教室、学生、老师、电话、汽车等等。一般都要从属性和行为两个方面来对它们加以描述。在这里，我们认为对象和对象的实例是同一个概念。什么是对象？2.4 反猜数游戏如何过滤？6月19日左右，具体时间、地点下周通知已参加大作业的同学不参加考试 考试题目形式：考试范围：C语言（即前十三周所讲内容）题型：编程题3道，算法题（只要求写出程序流程，不要求具体编程)1道，程序阅读题（挑出已有程序中错误） 2道。关于考试1 本周日课上进行演示。2 演示按大组进行按所选题目，将参加大作业的同学分成了11组，每组指定了两个联系人。大组内可互相交流和协作，尽量保证彼此之间实现功能有些区别。课上留3040分钟供大家进行讨论请选作特定题目的同学，到联系人那里登记，留下班级、学号、姓名、邮件和电话等联系方式请联系人将选作人信息汇总后