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

第2章循环结构程序设计【教学内容相关章节】21FOR循环22循环结构程序设计23文件操作24小结与习题【教学目标】（1）掌握FOR循环的使用方法；（2）掌握WHILE循环的使用方法；（3）学会使用计算器和累加器；（4）学会用输出中间结果的方法调试；（5）学会用计时函数测试程序效率；（6）学会用重定向的方式读写文件；（7）学会FOPEN的方式读写文件；（8）了解算法竞赛对文件读写方式和命名的严格性；（9）记住变量在赋值之前的值是不确定的；（10）学会使用条件编译指示构建本地运行环境。【教学要求】掌握FOR循环的使用方法；掌握WHILE循环的使用方法；掌握几个常用的文件操作库函数FOPEN、FCLOSE、FPRINTF、FSCANF等。【教学内容提要】在有些程序中，需要反复执行某些语句。将N条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。相关的语句有FOR、WHILE、DOWHILE、BREAK、CONTINUE等。既可以从文件中读取数据,也可以向文件中写入数据。读写文件之前，首先要打开文件。读写文件结束后，要关闭文件。C/C提供了一系列库函数，声明于STDIOH中，用于进行文件操作。这里介绍其中几个常用的文件操作库函数FOPEN、FCLOSE、FPRINTF、FSCANF等。【教学重点、难点】教学重点（1）掌握FOR循环的使用方法；（2）掌握WHILE循环的使用方法；（3）掌握文件有关操作；（4）条件编译。教学难点（1）掌握FOR循环的使用方法；（2）掌握WHILE循环的使用方法；【课时安排（共2学时）】21FOR循环22循环结构程序设计23文件操作24小结与习题21FOR循环请用FOR循环实现输入正整数N，打印1,2,3,10，每个占用一行。程序如下程序21输出1,2,3,N的值INCLUDEINTMAININTI,NSCANF“D“,FORI1IINCLUDEINTMAININTA,B,NDOUBLEMFORA1AINTMAININTX,N,HI,LOFORX1XNXXIFN9999BREAKHIN/100LON100IFHI/10HI10RETURN0说明本程序中用到BREAK和CONTINUE语句。BREAK是指直接跳出本层循环，CONTINUE是指结束本次循环，但不跳出本层循环，进入下一次循环。22循环结构程序设计例223N1问题。猜想对于任意大于1的自然数，若N为奇数，则将N变为3N1，否则变为N的一半。经过若干次这样的变换，一定会使N变为1。例如3105168421。输入N，输出变换的次数。N109。样例输入3样例输出7【分析】从3N1问题可以看出，N也不是“递增”式的循环，且循环次数也不确定，这种情况非常适合用WHILE循环来实现。程序243N1问题INCLUDEINTMAININTN,COUNT0SCANF“D“,WHILEN1IFN21NN31ELSEN/2COUNTPRINTF“DN“,COUNTRETURN0提示27WHILE循环的格式为“WHILE条件循环体”。从程序24中可得，WHILE循环与FOR循环可以相互转化。在本程序中的COUNT，相当于一个计算器，这个功能在编程中会经常遇到。提示28当需要统计某种事物的个数时，可以用一个变量来充当计算器。提示29不要忘记测试。一个看上去正确的程序可能隐含错误。提示210在观察无法找出错误时，可以用“输出中间结果”的方法查错。例23阶乘之和。输入N，计算S123N的末6位（不含前导0）。N106。这里，N表示前N个正整数之积。样例输入10样例输出37913【分析】用S变量来累加阶乘之和。核心算法只有一句话FORI1IINTMAININTI,J,N,S0SCANF“D“,FORI1IINCLUDEINTMAINCONSTINTMOD1000000INTI,J,N,S0SCANF“D“,FORI1IINTMAININTX,N0,MIN,MAX,S0WHILESCANF“D“,IFXMAXMAXXNPRINTF“DD3LFN“,MIN,MAX,DOUBLES/NRETURN0说明（1）SCANF函数的返回值是成功输入的变量个数。当输入结束时，SCANF无法再次读取X，将返回0。（2）在测试时，输入28351736，按ENTER键后，没有输出结果，所以此时按ENTER键并不意味着输入的结束。提示215在WINDOWS下，输入完毕后先按ENTER键，再按CTRLZ键，最后再按ENTER键，即可结束键入。在LINUX下，输入完毕后按CTRLD键即可结束输入。通过提示215，输入可以结束了。但是此程序的运行结果是不确定的。提示216变量在未赋值之前的值是不确定的。特别地，它不一定等于0。解决上面程序的运行结果不对的方法是在变量使用前赋初值。由于MIN保存的是最小值，它的初值应该是一个很大的数；反过来，MAX的初值应该是一个很小的数。一种方法是定义一个很大的常数，如INF1000000000，然后让MAXINF，而MININF，而另一种方法是先读取第一个整数X，然后令MAXMINX。另一个好的方法是用文件把输入数据保存在文件中，输出数据也保存在文件中。事实上，几乎所有算法竞赛的输入数据和标准答案都是保存在文件中的。使用文件最简单的方法是使用输入输出重定向，只需要在MAIN函数的入口处加入以下两条语句FREOPEN“INPUTTXT“,“R“,STDINFREOPEN“OUTPUTTXT“,“W“,STDOUT它将使得SCANF从文件INPUTTXT读入，PRINTF写入文件OUTPUTTXT。但是并不是所有算法竞赛都允许用程序读写文件。甚至有的竞赛允许访问文件，但不允许FREOPEN这样的重定向方式读写文件。请参赛之前仔细阅读文件读写的相关规定。提示217请在比赛之前了解文件读写的相关规定是标准输入输出（也称标准I/O，即直接读键盘、写屏幕），还是文件输入输出如果是文件输入输出，是否禁止用重定向方式访问文件多年来，无数选手因文件相关问题丢掉了大量的得分。一个普适的原则是详细阅读比赛规定，并严格遵守。例如，如果题目规定程序名称为TEST，输入文件名为TESTIN，输出文件名为TESTOUT，就是不要犯以下错误。错误1程序存为T1C（应该改成TESTC）。错误2从INPUTTXT读取数据（应该从TESTIN读取）。错误3从TSETIN读到数据（拼写错误，应该从TESTIN读取）。错误4数据写到TESTANS（扩展名错误，应该是TESTOUT）。错误5数据写到CCONTESTTESTOUT（不能加路径，哪怕是相对路径。文件名应该只有8个字符TESTOUT）。提示218在算法竞赛中，选手应严格遵守比赛的文件名规定，包括程序文件名和输入输出文件名。不要弄错大小写，不要拼错文件名，不要使用绝对路径或相以路径。利用文件是一种好的自我测试方法，但如果比赛要求采用标准输入输出，就必须在自我测试完毕之后删除重定向语句。下面来介绍一种方法可以在本机测试时用文件重定向，但一旦提交到比赛，就自动“删除”重定向语句。代码如下程序28数据统计（重定向版）DEFINELOCALINCLUDEDEFINEINF1000000000INTMAINIFDEFLOCALFREOPEN“DATAIN“,“R“,STDINFREOPEN“DATAOUT“,“W“,STDOUTENDIFINTX,N0,MININF,MAXINF,S0WHILESCANF“D“,IFXMAXMAXX/PRINTF“XD,MIND,MAXDN“,X,MIN,MAX/NPRINTF“DD3LFN“,MIN,MAX,DOUBLES/NRETURN0上面是一份典型的比赛代码，包含了几个特别的地方（1）重定向的部分被写在了IFDEF和ENDIF中。它的含义是只有定义了符号LOCAL，才编译两条FREOPEN语句。（2）输出中间结果的PRINTF语句写在注释中它在最后版本的程序中不应该出现，但是又舍不得删除它（万一发现了新的BUG，需要再次用它输出中间信息）。把它注释化的好处是一旦需要的时候，把注释符去掉即可。上面的代码在程序首部就定义了符号LOCAL,因此在本机测试时使用重定向方式读写文件。如果比赛要求读写标准输入输出，只需在提交之前删除DEFINELOCAL即可。一个更重好的方法是在编译选项而不是程序里定义这个LOCAL符号，这样在提交之前不需要修改程序。如果比赛要求用文件输入输出，但禁止用重定向的方式，程序如下程序29数据统计（FOPEN版）INCLUDEDEFINEINF1000000000INTMAINFILEFIN,FOUTFINFOPEN“DATAIN“,“RB“FOUTFOPEN“DATAOUT“,“WB“INTX,N0,MININF,MAXINF,S0WHILEFSCANFFIN,“D“,IFXMAXMAXXNFPRINTFFOUT,“DD3LFN“,MIN,MAX,DOUBLES/NFCLOSEFINFCLOSEFOUTRETURN0说明（1）本程序先声明变量FIN和FOUT，把SCANF改成FSCANF，第一个参数为FIN；把PRINTF改成FPRINTF，第一个参数为FOUT，最后执行FCLOSE，关闭两个文件。（2）重定向和FOPEN的区别。重定向的方法写起来简单、自然，但是不能同时读写文件和标准输入输出；FOPEN的写法稍显繁琐，但是灵活性比较大。如果想把FOPEN版的程序改成读写标准输入输出，只需赋值FINSTDIN；FOUTSTDOUT；即可，不要想调用FOPEN和FCLOSE。24小结与习题241输出技巧首先是输出技巧。通过对程序21进行小小的改动来实现输出2,4,6,8,2N，每个一行。为了方便，现把程序复复制如下1INCLUDE2INTMAIN34INTI,N5SCANF“D“,6FORI1IINTMAINDOUBLEIFORI0I10I01PRINTF“1LFN“,IRETURN0说明对于I可以达到100，但永远不会与10相等，所以FOR循环是一个死循环。对于FLOAT和DOBULE类型的数据不能直接用和来比较大小，即不要测试精确的浮点型数值，需要用精度比较，来测试一个可接受的数值范围。课本P85页有这样的说明。例如，IFFABSSALES_TAX0065INCLUDEINTMAIN_INT64N,/注意INT64之前是两个下划线（_）/X,COUNT0/假设X是N的因子，COUNT为计数器/SCANF“I64D“,FORX1X/功能和C中的STDIOH很接近，但有些许不同USINGNAMESPACESTDINTMAININTA,BWHILESCANF“DD“,RETURN0上面的C程序很像C程序。唯一的区别是原来的STDIOH变成了CSTDIO，并且多了一条语句USINGNAMESPACESTD。这是一个普遍规律要在C程序中使用C语言头文件，请去掉扩展名H，并在最前面加上小字母C。例如，STDIOH在C中的新名字是CSTDIO。另外，第一行中以/开头的是C特有的“单行注释”，它和C中的传统注释（/和/）可以混合使用。（2）方法二（不用记住D、LF等恼人的占位符）INCLUDE/头文件IOSTREAM包含了对输入输出流的定义USINGNAMESPACESTDINTMAININTA,BWHILECINABCOUTUSINGNAMESPACESTDIFSTREAMFIN“APLUSBIN“OFSTREAMFOUT“APLUSBOUT“INTMAININTA,BWHILEFINABFOUT）从流中输入数据。比如本程序中有一个输入流（FIN），FINAB表示从输入流中读取两个指定类型（即变量A和B的类型）的数据。插入器（VOIDMAININTA,BSCANF“DD”,PRINTF“D”,AB但上述代码提交上述到OJ上不能通过，是什么原因呢这就是下面需要解决的问题。下面来分类进行介绍。2基本输入（1）第一类输入输入不说明有多少个INPUTBLOCK,以EOF为结束标志，例如上面的例子。源代码如下INCLUDEINTMAININTA,BWHILESCANF“DD“,本类问题的输入方案为C语法WHILESCANF“DD“,，如果只有一个整数输入，返回值是1；如果有两个整数输入，返回值是2；如果一个都没有，则返回值是1。EOF是一个预定义的常量，等于1。（2）第二类输入输入一开始就会说有N个INPUTBLOCK,下面接着是输入N个INPUTBLOCK。参见HDOJ_1090（HTTP/ACMHDUEDUCN/SHOWPROBLEMPHPPID1090）。源代码如下INCLUDEINTMAININTN,I,A,BSCANF“D“,FORI0INFORI0IINTMAININTA,BWHILESCANF“DD“,上面程序有什么问题本类问题的输入方案为C语法WHILESCANF“D”,GETSBUFC语法如果用STRINGBUF来保存，则用语句GETLINECIN,BUF。如果用CHARBUF255来保存，则用语句CINGETLINEBUF,255。说明SCANF“SS“,STR1,STR2，在多个字符串之间用一个或多个空格分隔；若使用GETS函数，应为GETSSTR1GETSSTR2字符串之间用回车符作分隔。通常情况下，接受短字符用SCANF函数，接受长字符用GETS函数。GETCHAR函数每次只接受一个字符，经常CGETCHAR这样来使用。CINGETLINE的用法GETLINE是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下ISTREAM不用管它的返回类型，来关心它的三个参数CHARLINE就是一个字符数组，用户输入的内容将存入在该数组内。INTSIZE表示最多接受几个字符用户超过SIZE的输入都将不被接受。CHARENDCHAR表示当用户输入ENDCHAR指定的字符时，自动结束。默认是回车符。结合后两个参数，GETLINE可以方便地实现用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。CHARNAME4CINGETLINENAME,4,N由于ENDCHAR默认已经是N，所以后面那行也可以写成CINGETLINENAME,4。思考以下题目属于哪一类输入HTTP/ACMHDUEDUCN/SHOWPROBLEMPHPPID1018HTTP/ACMHDUEDUCN/SHOWPROBLEMPHPPID10133基本输出（1）第一类输出一个INPUTBLOCK对应一个OUTPUTBLOCK，OUTPUTBLOCK之间没有空行。参见HDOJ_1089（HTTP/ACMHZIEEEDUCN/SHOWPROBLEMPHPPID1089）。本类问题的输出方案为C语法PRINTF“DN“,ANSC语法COUTINTMAININTA,BWHILESCANF“DD“,解决办法如下C语法PRINTF“DNN“,ANSC语法COUTINTMAININTICASE,N,I,J,A,SUMSCANF“D“,FORI0IINCLUDEINTMAININTJ0FORJ0J总结练习总结的过程，使得自己编程水平得到提高；（2）可以在HTTP/ACMHDUEDUCN或其它网站上多多练习；（3）可以去杭电ACM论坛或其它ACM论坛上，与别人分享经验；（4）有问题可以在GOOGLE、BAIDU上去搜索。246小结现在对本章介绍的循环总结如下（1）介绍了在编程中的一些经验，如使用计算器、累加器、以及“当前最小/最大值”这样的中间变量。使用PRINTF输出一些关键的中间变量能有效地帮助我们了解程序执行过程、发现错误。（2）遇到问题需要自己分析和设计，可以先写出“伪代码”，然后转换成程序。伪代码是为了让思路更清晰，突出主要矛盾。（3）编写好程序后，测试显得相当重要。如前面的例子中几乎都有陷阱运算结果溢出、运算时间过长等。对于海量的输入输出问题可以通过文件得到缓解。（4）再次强调编程不是看书看会的，也不是听课听会的，而是练会的。247上机练习注意，本章的题目需用文件输入输出。如果题目代号为ABC，那么输入文件为ABCIN，输出文件为ABCOUT。如果对文件操作不熟练，请尽量把FOPEN、FREOPEN两种方法都尝试一下。习题21位数（DIGIT）输入一个不超过109的正整数，输出它的位数。例如12735的位数是5。请不要使用任何数学函数，只用四则运算和循环语句实现。【分析】采取的策略是不断地整除10，检查商是否大于10。程序如下INCLUDEVOIDMAINUNSIGNEDLONGN/无符号的长整型数，占4字节存储空间/INTDIGIT1/位数/SCANF“LD“,FORN10NN/10DIGITDIGIT1PRINTF“D“,DIGITRETURN习题22水仙花数（DAFFODIL）输出100999中的所有水仙花数。若3位数ABCA2B2C2，则称其为水仙花数。例如153135333，所以153是水仙花数。【分析】采取的策略是穷举100999之内的所有数据，检查是否满足题目的要求。程序如下INCLUDEVOIDMAININTN,A,B,C/N的百、十、个位/FORN100NVOIDMAININTA,/三人一排，余A人/B,/五人一排，余B人/C,/七人一排，余C人/SUM/总人数/SCANF“DDD“,FORSUM10SUM100PRINTF“NOANSWER“RETURN习题24倒三角形（TRIANGLE）输入正整数N20，输出一个N层的倒三角形。例如N5时输出如下【分析】该图形一共有N行，这次要考虑每行中，先输出若干个空格，所以，其外循环为FORI1IVOIDMAININTN,/输出N行NMAININTI,JFORI1IINTMAININTI,J,KFORI1IINTMAININTI,JCHARCHFORI1IMAININTI,J,KFORI1IVOIDMAININTM,N,I,NEWDATA,/新读到的数据/COUNT/计数器/FREOPEN“STATINTXT“,“R“,STDINFREOPEN“STATOUTTXT“,“W“,STDOUTSCANF“D“,FORI1IVOIDMAININTN,I,M,NEWDATA,/新输入的数据/COUNT/计数器/SCANF“D“,SCANF“D“,COUNT0FORI1IVOIDMAININTN,I,M,NEWDATA,/新输入的数据/COUNT/计数器/FREOPEN“统计的变种INTXT“,“R“,STDINFREOPEN“统计的变种OUTTXT“,“W“,STDOUTSCANF“D“,SCANF“D“,COUNT0FORI1IVOIDMAINUNSIGNEDINTN/我们认为INT已经足够表达所谓的“正整数”范围/DOUBLESUM0SCANF“U“,FORN1NN1SUMSUM10/NPRINTF“3F“,SUMRETURN习题27近似计算（APPROXIMATION）计算，直到最后一项小于106。14357【分析】本题主要考察循环语句的使用。秘诀是要从绝对值最小的项开始向绝对值大的项累加。程序如下INCLUDEVOIDMAININTNDOUBLESUM0INTSYMBOLN1000001/显然，1/1000001小于0000001/FORN1NN2IFN1/221SYMBOL1ELSESYMBOL1SUMSUMSYMBOL10/NPRINTF“20LF“,SUMRETURN习