[工学]算法竞赛入门经典授课教案第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问题（1）INCLUDEINTMAININTN,COUNT0SCANF“D“,WHILEN1IFN21NN31ELSEN/2COUNTPRINTF“DN“,COUNTRETURN0提示27WHILE循环的格式为“WHILE条件循环体”。从程序24中可得，WHILE循环与FOR循环可以相互转化。在本程序中的COUNT，相当于一个计算器，这个功能在编程中会经常遇到。提示28当需要统计某种事物的个数时，可以用一个变量来充当计算器。这个程序是正确的吗输入987654321（根据题目所给范围N109，这是合法输入）输出1提示29不要忘记测试。一个看上去正确的程序可能隐含错误。提示210在观察无法找出错误时，可以用“输出中间结果”的方法查错。WHILEN1IFN21NN31PRINTF“D“,NELSEN/2PRINTF“D“,NCOUNT第一次输因乘法溢出。程序243N1问题（2）INCLUDEINTMAININTN,COUNT0SCANF“D“,WHILEN1IFN21N3N1/22COUNTELSEN/2COUNTPRINTF“DN“,COUNTRETURN0例23阶乘之和。输入N，计算S123N的末6位（不含前导0）。N106。这里，N表示前N个正整数之积。样例输入10样例输出37913【分析】用S变量来累加阶乘之和。核心算法只有一句话FORI1IINTMAININTI,J,N,S0SCANF“D“,FORI1IINCLUDEINTMAINCONSTINTMOD1000000INTI,J,N,S0SCANF“D“,FORI1IINCLUDEINTMAINCONSTINTMOD1000000INTI,J,N,S0SCANF“D“,CLOCK_TSTART,FINISHSTARTCLOCKFORI1I25N25”即可。23文件操作例24数据统计。输入一些整数，求出它们的最小值、最大值和平均值（保留3位小数）。输入保证这些数都是不超过1000的整数。样例输入28351736样例输出184375【分析】如果是先输入整数N，然后输入N个整数，相信能写出程序。关键在于整数的个数是不确定的。下面给出程序程序27数据统计（错误）INCLUDEINTMAININTX,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类型的数据不能直接用和来比较大小，即不要测试精确的浮点型数值，需要用精度比较，来测试一个可接受的数值范围。如FORI0FABS10I1E5I0124364位整数题目输入正整数N，统计它的正因子个数。N1012。例如，N30时，输出应该为8。【分析】（1）如果I是N的约数，则N/I也是N的约数。所以可以从1枚举到。N（2）N太大（N1012），超过了INT类型的表示范围（2312311，比229229略宽）。（3）有一种比INT更大的类型，称为LONGLONG，它的表示范围是2632631，比10191019略窄。在VC60中（没有LONGLONG数据类型），如果要定义一个LONGLONG数据类型的变量A（64位整数）应该定义如下_INT64A输入输出的时候用I64D，如SCANF“I64D“,PRINTF“I64D“,A本题的程序如下INCLUDEINCLUDEINTMAIN_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的类型）的数据。插入器（VOIDMAINUNSIGNEDLONGN/无符号的长整型数，占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习题28子序列的和（SUBSEQUENCE）输入两个正整数NVOIDMAINDOUBLEM,NDOUBLESUM0SCANF“LFLF“,/假设用户输入的N总是不大于M/FORMNMM1SUMSUM10/MM/注意，不能写成SUM1/MM/PRINTF“5LF“,SUMRETURN习题29分数化小数（DECIMAL）输入正整数A,B,C，输出A/B的小数形式，精确到小数点后C位。A,B106，C100。例如A1，B6,C4时应输出01667。【分析】注意到A,B,C均为正整数，所以输出结果的小数点后至少会有1位。另外，从本题的示例输出中可以感知到，小数的最后一位，是要考虑到四舍五入进位的。采取的策略是模拟整数除法的过程，利用整除所得的余数，不断地对目标结果求精。程序如下INCLUDEVOIDMAININTA,B,CSCANF“DDD“,PRINTF“D“,A/B/先输出整数和小数点FORINTI1I5PRINTF“D“,A/B1ELSEPRINTF“D“,A/BPRINTF“N“习题210排列（PERMUTATION）用1,2,3,9组成3个三位数ABC，DEF和GHI，每个数字恰好使用一次，要求ABCDEFGHI123。输出所有解。提示不必太动脑筋。【分析】采用的策略是穷举法解题。尽管说“不必太动脑筋”，但也不意味着“一点儿都不用动脑筋”。如果说三个三位数是ABC,DEF,GHI，比率是123，那么显然D2A并且G3A。所以，12A，G3A；这些论断，都可以减少电脑穷举所需扫描的范围，提高运行速度。如果还能够提出更加精确的论断，就还能进一步提高程序的运行速度。程序如下INCLUDEVOIDMAININTA,B,C,D,E,F,G,H,IFORA1AINCLUDEUSINGNAMESPACESTDVOIDMAININTX,Y,ZFORINTABC123ABCVOIDMAININTA,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表示当用户输入ENDCHA