算法竞赛入门经典授课教案 循环结构程序设计.doc

《算法竞赛入门经典授课教案 循环结构程序设计.doc》由会员分享，可在线阅读，更多相关《算法竞赛入门经典授课教案 循环结构程序设计.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 循环结构程序设计【教学内容相关章节】2.1for循环 2.2循环结构程序设计 2.3文件操作2.4小结与习题【教学目标】1掌握for循环的使用方法；2掌握while循环的使用方法；3学会使用计算器和累加器；4学会用输出中间结果的方法调试；5学会用计时函数测试程序效率；6学会用重定向的方式读写文件；7学会fopen的方式读写文件；8了解算法竞赛对文件读写方式和命名的严格性；9记住变量在赋值之前的值是不确定的；10学会使用条件编译指示构建本地运行环境。【教学要求】掌握for循环的使用方法；掌握while循环的使用方法；掌握几个常用的文件操作库函数fopen、fclose、fprintf、f

2、scanf等。【教学内容提要】在有些程序中，需要反复执行某些语句。将n条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。相关的语句有：for、while、do while、break、continue等。既可以从文件中读取数据, 也可以向文件中写入数据。读写文件之前，首先要翻开文件。读写文件结束后，要关闭文件。C/C+提供了一系列库函数，声明于stdio.h中，用于进行文件操作。这里介绍其中几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。【教学重点、难点】教学重点：1掌握for循环的使用方法；2掌握w

3、hile循环的使用方法；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); return 0;提示2-1：for循环的格式：for(初始化；条件；调整) 循环体；

4、提示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; b+) if(aabb是完全平方数) printf(%dn, aabb);注意：1上面不是真正的

5、程序，把这样的代码称为伪代码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 + b*11; m = sqrt(n); if(floor(m+0.5) = m) printf(%dn, n);

6、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 = n / 100; lo = n % 100; if(hi/10 = hi%10 & lo/10 = lo%10) p

7、rintf(%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问题可以看出，n也不是“递增式的循环，且循环次数也不确定，这种情况非常适合用while循环来实现。程序2-4 3n+1问题

8、#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+，相当于一个计算器，这个功能在编程中会经常遇到。提示2-8：当需要统计某种事物的个数时，可以用一个变量来充当计算器。提示2-9：不要忘记测试。一个看上去正确的程序可能隐含

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#include int main() int i, j, n, S = 0; scanf(%d, &n); for(i =

10、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：在循环体开始处定义的变量，每次执行循环体时会重新声明并初始化。提示2-12：要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变。程序

11、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, S); printf(Time used = %.2lfn, (double)clock() / CLOCKS_PER_SEC);

12、 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_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，时钟计时单元的长度为1毫秒，clock()/CLOCKS_PER_SEC就是将毫秒转化为

13、秒。提示2-13：可以使用time.h和clock()函数获得程序运行时间。常数CLOCKS_PER_SEC与操作系统有关，请不要直接使用clock()的返回值，而应总是除以CLOCKS_PER_SEC。提示2-14：很多程序的运行时间与规模n存在着近似的简单关系。可以通过计时函数来发现或验证这一关系。 本节的两个例题展示了计数器、累加器的使用和循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。另外，本节中介绍的两个工具输出中间结果和计时函数，都有是相当实用的。2.3 文件操作例2-4 数据统计。输入一些整数，求出它们的最小值、最大值和平均值保存3位小数。输入保证这些数都是不超过

14、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) max = x; n+; printf(%d %d %.3lfn, min, max, (double)s/n); return 0;说明：1scanf函数的返回值是成功输入的变量个数。当输入结束

15、时，scanf无法再次读取x，将返回0。2在测试时，输入2 8 3 5 1 7 3 6，按Enter键后，没有输出结果，所以此时按Enter键并不意味着输入的结束。提示2-15：在Windows下，输入完毕后先按Enter键，再按Ctrl+Z键，最后再按Enter键，即可结束键入。在Linux下，输入完毕后按Ctrl+D键即可结束输入。通过提示2-15，输入可以结束了。但是此程序的运行结果是不确定的。提示2-16：变量在未赋值之前的值是不确定的。特别地，它不一定等于0。解决上面程序的运行结果不对的方法是在变量使用前赋初值。由于min保存的是最小值，它的初值应该是一个很大的数；反过来，max的初

16、值应该是一个很小的数。一种方法是定义一个很大的常数，如INF=1000000000，然后让max=INF，而min=-INF，而另一种方法是先读取第一个整数x，然后令max=min=x。另一个好的方法是用文件把输入数据保存在文件中，输出数据也保存在文件中。事实上，几乎所有算法竞赛的输入数据和标准答案都是保存在文件中的。使用文件最简单的方法是使用输入输出重定向，只需要在main函数的入口处参加以下两条语句：freopen(input.txt,r,stdin);freopen(output.txt,w,stdout);它将使得scanf从文件input.txt读入，printf写入文件output

17、.txt。但是并不是所有算法竞赛都允许用程序读写文件。甚至有的竞赛允许访问文件，但不允许freopen这样的重定向方式读写文件。请参赛之前仔细阅读文件读写的相关规定。提示2-17：请在比赛之前了解文件读写的相关规定：是标准输入输出也称标准I/O，即直接读键盘、写屏幕，还是文件输入输出？如果是文件输入输出，是否禁止用重定向方式访问文件？多年来，无数选手因文件相关问题丢掉了大量的得分。一个普适的原那么是：详细阅读比赛规定，并严格遵守。例如，如果题目规定程序名称为test，输入文件名为test.in，输出文件名为test.out，就是不要犯以下错误。错误1：程序存为t1.c应该改成test.c。 错

18、误2：从input.txt读取数据应该从test.in读取。 错误3：从tset.in读到数据拼写错误，应该从test.in读取。 错误4：数据写到test.ans扩展名错误，应该是test.out。 错误5：数据写到c:contesttest.out不能加路径，哪怕是相对路径。文件名应该只有8个字符：test.out。提示2-18：在算法竞赛中，选手应严格遵守比赛的文件名规定，包括程序文件名和输入输出文件名。不要弄错大小写，不要拼错文件名，不要使用绝对路径或相以路径。 利用文件是一种好的自我测试方法，但如果比赛要求采用标准输入输出，就必须在自我测试完毕之后删除重定向语句。下面来介绍一种方法可

19、以在本机测试时用文件重定向，但一旦提交到比赛，就自动“删除重定向语句。代码如下：程序2-8 数据统计重定向版#define LOCAL#include #define INF 1000000000int main()#ifdef LOCAL freopen(data.in, r, stdin); freopen(data.out, w, stdout);#endif int x, n = 0, min = INF, max = -INF, s = 0; while(scanf(%d, &x) = 1) s += x; if(x max) max = x;/* printf(x = %d, mi

20、n = %d, max = %dn, x, min, max);*/ n+; printf(%d %d %.3lfn, min, max, (double)s/n); return 0;上面是一份典型的比赛代码，包含了几个特别的地方：1重定向的局部被写在了#ifdef和#endif中。它的含义是：只有定义了符号LOCAL，才编译两条freopen语句。2输出中间结果的printf语句写在注释中它在最后版本的程序中不应该出现，但是又舍不得删除它万一发现了新的bug，需要再次用它输出中间信息。把它注释化的好处是：一旦需要的时候，把注释符去掉即可。上面的代码在程序首部就定义了符号LOCAL,因此在本

21、机测试时使用重定向方式读写文件。如果比赛要求读写标准输入输出，只需在提交之前删除#define LOCAL即可。一个更重好的方法是在编译选项而不是程序里定义这个LOCAL符号，这样在提交之前不需要修改程序。如果比赛要求用文件输入输出，但禁止用重定向的方式，程序如下：程序2-9 数据统计fopen版#include #define INF 1000000000int main() FILE *fin, *fout; fin = fopen(data.in, rb); fout = fopen(data.out, wb); int x, n = 0, min = INF, max = -INF,

22、s = 0; while(fscanf(fin, %d, &x) = 1) s += x; if(x max) max = x; n+; fprintf(fout, %d %d %.3lfn, min, max, (double)s/n); fclose(fin); fclose(fout); return 0;说明：1本程序先声明变量fin和fout，把scanf改成fscanf，第一个参数为fin；把printf改成fprintf，第一个参数为fout，最后执行fclose，关闭两个文件。2重定向和fopen的区别。重定向的方法写起来简单、自然，但是不能同时读写文件和标准输入输出；fope

23、n的写法稍显繁琐，但是灵活性比拟大。如果想把fopen版的程序改成读写标准输入输出，只需赋值fin=stdin；fout=stdout；即可，不要想调用fopen和fclose。2.4 小结与习题2.4.1 输出技巧首先是输出技巧。通过对程序2-1进行小小的改动来实现输出2,4,6,8,2n，每个一行。为了方便，现把程序复复制如下：1 #include 2 int main()3 4 int i, n;5 scanf(%d, &n);6 for(i = 1; i = n; i+)7 printf(%dn, i);8 return 0;9 任务1：修改第7行，不修改第6行。解答：修改第7行的如下

24、：7 printf(%dn, 2*i);任务2：修改第6行，不修改第7行。解答：修改第6行的如下：6 for(i = 2; i = 2*n; i+=2)2.4.2 浮点数陷阱“!=运算符表示“不相等，那么下面的程序的运行结果是什么？#include int main() double i;for(i=0;i!=10;i+=0.1) printf(%.1lfn,i);return 0;说明：对于i可以到达10.0，但永远不会与10相等，所以for循环是一个死循环。对于float和dobule类型的数据不能直接用 =和!=来比拟大小，即不要测试精确的浮点型数值，需要用精度比拟，来测试一个可接受的数

25、值范围。课本P85页有这样的说明。例如，if(fabs(sales_tax-0.065)=0.0001).2.4.3 64位整数题目：输入正整数n，统计它的正因子个数。n1012。例如，n=30时，输出应该为8。【分析】1如果i是n的约数，那么n/i也是n的约数。所以可以从1 枚举到。2n太大n1012，超过了int类型的表示范围-231231-1，比-229229略宽。3有一种比int更大的类型，称为long long，它的表示范围是-263263-1，比-1019-1019略窄。在VC6.0中没有long long数据类型，如果要定义一个long long数据类型的变量a64位整数应该定义

26、如下：_int64 a; 输入输出的时候用 %I64d，如：scanf(%I64d,&a);printf(%I64d,a); 此题的程序如下：#include #include int main() _int64 n, /* 注意int64之前是两个下划线_*/ x,count=0; /* 假设x是n的因子，count为计数器 */scanf(%I64d,&n);for(x=1;x=(_int64)sqrt(n);x+)if(n%x = 0) count += 2; /* 之所以+2，是因为x和n/x都是n的因子 */ if(n/x = x) count = count-1; printf(%

27、I64dn, count);return 0;2.4.4 C+中的输入输出“A+B问题：输入假设干对整数，输出每对之和。通过经典的“A+B问题，来用C+语言来研究输入输出。1方法一#include /功能和C中的stdio.h很接近，但有些许不同using namespace std;int main() int a,b; while(scanf(%d%d, &a, &b)=2) printf(%dn, a+b); return 0;上面的C+程序很像C程序。唯一的区别是原来的stdio.h变成了cstdio，并且多了一条语句using namespace std。这是一个普遍规律要在C+程序

28、中使用C语言头文件，请去掉扩展名.h，并在最前面加上小字母c。例如，stdio.h在C+中的新名字是cstdio。另外，第一行中以/开头的是C+特有的“单行注释，它和C中的传统注释/*和*/可以混合使用。2方法二不用记住%d、%lf等恼人的占位符#include /头文件iostream包含了对输入输出流的定义using namespace std;int main() int a,b; while(cinab) couta+bn; return 0;下面用输入输出文件流来修改方法二，程序如下：#include using namespace std;ifstream fin(aplusb.i

29、n);ofstream fout(aplusb.out);int main() int a, b; while(finab) fouta+b从流中输入数据。比方本程序中有一个输入流fin，finab表示从输入流中读取两个指定类型即变量a和b的类型的数据。插入器向流中输出数据。比方本程序中有一个输出流fout，fouta+b n;表示把a+b的值和换行字符n输出到文件输出流fout中。如果想再次使用cin和cout，是否要逐个把程序中的所有fin和fout替换为cin和cout？不用这么麻烦，只需要把fin和fout的声明语句去掉，并加上这样两行即可：#define fin cin#define

30、 fout cout2.4.5 ACM题目中的输入输出1ACM题目特点由于ACM竞赛题目的输入数据和输出数据一般有多组不定，并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最根本的要求。这也是困扰初学者的一大问题。经常有刚接触ACM在线测试系统的同学抱怨：“为什么我在OJOnline Judge上连简单的A+B也通不过？先给一个竞赛样例：题目名称：A+B for Input-Output Practice (I)链接地址：Time Limit: 1 SecondsMemory Limit:32768KProblem DescriptionYour task is to Calcul

31、ate a + b.Too easy?! Of course! I specially designed the problem for acm beginners. You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim. InputThe input will consist of a series of pairs of integers a and b, separated by a

32、space, one pair of integers per line. OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample Input1 510 20Sample Output630初学者很常见的一种写法：#include void main() int a,b; scanf(“%d %d,&a,&b); printf(“%d,a+b)

33、;但上述代码提交上述到OJ上不能通过，是什么原因呢？这就是下面需要解决的问题。下面来分类进行介绍。2根本输入1第一类输入输入不说明有多少个Input Block,以EOF为结束标志，例如上面的例子。源代码如下：#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dn,a+b); 本类问题的输入方案为：C语法while(scanf(%d %d,&a, &b) != EOF) . C+语法while( cin a b ) . 说明：scanf函数返回值就是读出的变量个数，如：scanf(%d %d, &a,

34、&b ); ，如果只有一个整数输入，返回值是1；如果有两个整数输入，返回值是2；如果一个都没有，那么返回值是-1。EOF是一个预定义的常量，等于-1。2第二类输入输入一开始就会说有n个Input Block,下面接着是输入n个Input Block。参见：HDOJ_1090=1090。源代码如下：#include int main() int n,i,a,b; scanf(%d,&n); for(i=0;in;i+) scanf(%d %d,&a, &b); printf(%dn,a+b); 本类问题的输入方案为：C语法scanf(%d,&n); for( i=0 ; i n; for( i=

35、0 ; in ; i+ ) . 3第三类输入输入不说明有多少个Input Block,但以某个特殊输入为结束标志。参见：HDOJ_1091=1091。源代码如下：#include int main() int a,b;while(scanf(%d %d,&a, &b) &(a!=0 & b!=0) printf(%dn,a+b); 上面程序有什么问题？本类问题的输入方案为：C语法while(scanf(“%d,&n) ！=EOF & n!=0 ) . C+语法while( cin n & n != 0 ) . 4第四类输入以上几种情况的组合，可以参照如下网页，进行上机实验。=1092=1093

36、=10945第五类输入输入一整行的字符串。参见：HDOJ_1048htt=1048。本类问题的输入方案为：C语法char buf20; gets(buf); C+语法如果用string buf;来保存，那么用语句getline( cin , buf ); 。如果用char buf 255 ; 来保存，那么用语句cin.getline( buf, 255 );。说明：scanf(%s%s,str1,str2)，在多个字符串之间用一个或多个空格分隔；假设使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。通常情况下，接受短字符用scanf函数，接受长字符

37、用gets函数。getchar函数每次只接受一个字符，经常c=getchar()这样来使用。cin.getline的用法getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式函数原型如下：istream& getline(char line, int size, char endchar=n);不用管它的返回类型，来关心它的三个参数：char line就是一个字符数组，用户输入的内容将存入在该数组内。int size表示最多接受几个字符？用户超过size的输入都将不被接受。char endchar表示当用户输入endchar指定的字

38、符时，自动结束。默认是回车符。结合后两个参数，getline可以方便地实现：用户最多输入指定个数的字符，如果超过，那么仅指定个数的前面字符有效，如果没有超过，那么用户可以通过回车来结束输入。char name4;cin.getline(name,4,n);由于endchar 默认已经是 n，所以后面那行也可以写成：cin.getline(name,4);。思考：以下题目属于哪一类输入？owproblem.php?pid=1018=10133根本输出1第一类输出一个Input Block对应一个Output Block，Output Block之间没有空行。参见：HDOJ_1089=1089。本

39、类问题的输出方案为：C语法 . printf(%dn,ans); C+语法 .cout ans endl; 2第二类输出一个Input Block对应一个Output Block，每个Output Block之后都有空行。参见：HDOJ_1095=1095。源代码如下：#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dnn,a+b); 解决方法如下：C语法 . printf(%dnn,ans); C+语法 . cout ans endl endl; 3第三类输出一个Input Block对应一个Output Block，Output Block之间有空行。参见：HDOJ_1096=1096。源代码如下：#include int main() in