《算法竞赛入门经典授课教案第2章 循环结构程序设计》由会员分享，可在线阅读，更多相关《算法竞赛入门经典授课教案第2章 循环结构程序设计（26页珍藏版）》请在金锄头文库上搜索。
1、第2章 循环结构程序设计第2章 循环结构程序设计【教学内容相关章节】2.1for循环 2.2循环结构程序设计 2.3文件操作2.4小结与习题【教学目标】（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；（3）学会使用计算器和累加器；（4）学会用输出中间结果的方法调试；（5）学会用计时函数测试程序效率；（6）学会用重定向的方式读写文件；（7）学会fopen的方式读写文件；（8）了解算法竞赛对文件读写方式和命名的严格性；（9）记住变量在赋值之前的值是不确定的；（10）学会使用条件编译指示构建本地运行环境。【教学要求】掌握for循环的使用方法；掌握while循环的使用方法；掌握几个
2、常用的文件操作库函数fopen、fclose、fprintf、fscanf等。【教学内容提要】在有些程序中，需要反复执行某些语句。将n条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。相关的语句有：for、while、do while、break、continue等。既可以从文件中读取数据, 也可以向文件中写入数据。读写文件之前，首先要打开文件。读写文件结束后，要关闭文件。C/C+提供了一系列库函数，声明于stdio.h中，用于进行文件操作。这里介绍其中几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。
3、【教学重点、难点】教学重点：（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；（3）掌握文件有关操作；（4）条件编译。教学难点：（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；【课时安排（共2学时）】2.1for循环 2.2循环结构程序设计 2.3文件操作2.4小结与习题2.1 for循环请用for循环实现输入正整数n，打印1,2,3,10，每个占用一行。程序如下：程序2-1 输出1,2,3,n的值#include int main() int i, n; scanf(%d, &n); for(i = 1; i = n; i+) printf(%dn, i
4、); return 0;提示2-1：for循环的格式：for(初始化；条件；调整) 循环体；提示2-2：尽管for循环反复执行相同的语句，但这些语句每次的执行效果往往不同。提示2-3：编写程序时，要特别留意“当前行”的跳转和变量的改变。有了for循环，可以解决一些简单的问题。例2-1 aabb。输出所有形如aabb的四位完全平方数（即前两位数字相等，后两位数字也相等）。【分析】分支和循环结合在一起时威力特别强大：可以枚举所有可能的aabb，然后判断它们是否是完全平方数。注意，a的范围是19，但b可以是0。主程序如下：for(a = 1; a = 9; a+) for(b = 0; b = 9;
5、 b+) if(aabb是完全平方数) printf(%dn, aabb);注意：（1）上面不是真正的程序，把这样的代码称为伪代码（psedocode）。（2）上面用到了循环的嵌套：for循环的循环体自身又是一个循环。提示2-4：不拘一格的使用伪代码来思考和描述算法是一种值得推荐的做法。提示2-5：把伪代码改写成代码时，一般先选择较为容易的任务来完成。程序2-2 7744问题（1）#include #include int main() int a, b, n; double m; for(a = 1; a = 9; a+) for(b = 0; b = 9; b+) n = a*1100 +
6、 b*11; m = sqrt(n); if(floor(m+0.5) = m) printf(%dn, n); return 0;说明：函数floor(x)返回x的整数部分，使用floor(m+0.5)=m的原因是浮点数的运算（和函数）有可能存在误差。提示2-6：浮点运算可能存在误差。在进行浮点数比较时，应考虑到浮点误差。对于四位完全平方数的还有另一个思路就是枚举平方根x，从而避免开平方操作。程序2-3 7744问题（2）#include int main() int x, n, hi, lo; for(x = 1; ; x+) n = x * x; if(n 9999) break; hi
7、 = n / 100; lo = n % 100; if(hi/10 = hi%10 & lo/10 = lo%10) printf(%dn, n); return 0;说明：本程序中用到break和continue语句。break是指直接跳出本层循环，continue是指结束本次循环，但不跳出本层循环，进入下一次循环。2.2 循环结构程序设计例2-2 3n+1问题。猜想：对于任意大于1的自然数，若n为奇数，则将n变为3n+1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。例如3105168421。输入n，输出变换的次数。n109。样例输入：3样例输出：7【分析】从3n+1问题可以
8、看出，n也不是“递增”式的循环，且循环次数也不确定，这种情况非常适合用while循环来实现。程序2-4 3n+1问题#include int main() int n, count = 0; scanf(%d, &n); while(n 1) if(n % 2 = 1) n = n*3+1; else n /= 2; count+; printf(%dn, count); return 0;提示2-7：while循环的格式为：“while(条件) 循环体;”。从程序2-4中可得，while循环与for循环可以相互转化。在本程序中的count+，相当于一个计算器，这个功能在编程中会经常遇到。提示
9、2-8：当需要统计某种事物的个数时，可以用一个变量来充当计算器。提示2-9：不要忘记测试。一个看上去正确的程序可能隐含错误。提示2-10：在观察无法找出错误时，可以用“输出中间结果”的方法查错。例2-3 阶乘之和。输入n，计算S=1!+2!+3!+n!的末6位（不含前导0）。n106。这里，n!表示前n个正整数之积。样例输入：10样例输出：37913【分析】用S变量来累加阶乘之和。核心算法只有一句话：for(i=1;i=n;i+) S+=i!。在C语言中没有阶乘运算符，所以还需要一个循环来求i!: for(j=1;j=i;j+) factorial*=j;。 代码如下：程序2-5 阶乘之和（1
10、）#include int main() int i, j, n, S = 0; scanf(%d, &n); for(i = 1; i = n; i+) int factorial = 1; for(j = 1; j = i; j+) factorial *= j; S += factorial; printf(%dn, S % 1000000); return 0;注意：每执行一次循环体，都要重新声明一次累乘器factorial，并初始化为1（因为是乘积，所以初始化为1，要是初始化为0，则循环后的factorial=i!=0）。提示2-11：在循环体开始处定义的变量，每次执行循环体时会重新
11、声明并初始化。提示2-12：要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变。程序2-6 阶乘之和（2）#include #include int main() const int MOD = 1000000; int i, j, n, S = 0; scanf(%d, &n); for(i = 1; i = n; i+) int factorial = 1; for(j = 1; j = i; j+) factorial = (factorial * j % MOD); S = (S + factorial) % MOD; printf(%dn
12、, S); printf(Time used = %.2lfn, (double)clock() / CLOCKS_PER_SEC); return 0;说明：（1）这个程序真正的特别之处在于计时函数clock()的使用。该函数返回程序目前为止运行的时间，以毫秒为单位。这样，在程序结束之前调用它，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。（2）在VC+6.0中time.h下宏定义的常量CLOCKS_PER_SEC，其值为1000。VC+6.0中该符号常量定义如下： #define CLOCKS_PER_SEC 1000对于CLOCKS_
13、PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，时钟计时单元的长度为1毫秒，clock()/CLOCKS_PER_SEC就是将毫秒转化为秒。提示2-13：可以使用time.h和clock()函数获得程序运行时间。常数CLOCKS_PER_SEC与操作系统有关，请不要直接使用clock()的返回值，而应总是除以CLOCKS_PER_SEC。提示2-14：很多程序的运行时间与规模n存在着近似的简单关系。可以通过计时函数来发现或验证这一关系。 本节的两个例题展示了计数器、累加器的使用和循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。另外，本节中介绍的两个工具输出中间结果和计时函数，都有是相当实用的。2.3 文件操作例2-4 数据统计。输入一些整数，求出它们的最小值、最大值和平均值（保留3位小数）。输入保证这些数都是不超过1000的整数。样例输入：2 8 3 5 1 7 3 6样例输出：1 8 4.375【分析】如果是先输入整数n，然后输入n个整数，相信能写出程序。关键在于：整数的个数是不确定的。下面给出程序：程序2-7 数据统计（错误）#include int main() int x, n = 0, min, max, s = 0; while(scanf(%d, &x) = 1) s += x; if(x max
