NOIP竞赛循环代价

2.3循环的代价例题2-4阶乘之和输入n，计算S＝1！＋2！＋3！＋…＋n！的末6位（不含前导0）。n≤106，n！表示前n个正整数之积。样例输入：10样例输出：37913【分析】这个任务并不难，引入累加变量S之后，核心算法只有“for（inti＝1；i＜＝n；i＋＋）S＋＝i！”。不过，C语言并没有阶乘运算符，所以这句话只是伪代码，而不是真正的代码。事实上，还需要一次循环来计算i！，即“for（intj＝1；j＜＝i；j＋＋）factorial*＝j；”。代码如下：程序2-7阶乘之和（1）#includestdio.hintmain(){intn,S=0;scanf(%d,&n);for(inti=1;i=n;i++){intfactorial=1;for(intj=1;j=i;j++)factorial*=j;S+=factorial;}printf(%d\n,S%1000000);return0;}注意累乘器factorial（英文“阶乘”的意思）定义在循环里面。换句话说，每执行一次循环体，都要重新声明一次factorial，并初始化为1（想一想，为什么不是0）。因为只要末6位，所以输出时对106取模。提示2-15：在循环体开始处定义的变量，每次执行循环体时会重新声明并初始化。有了刚才的经验，下面来测试一下这个程序：n＝100时，输出-961703。直觉告诉我们：乘法又溢出了。这个直觉很容易通过“输出中间变量”法得到验证，但若要解决这个问题，还需要一点数学知识。提示2-16：要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变。在修正这个错误之前，还可以进行更多测试：当n＝106时输出什么？更会溢出不是吗？但是重点不在这里。事实上，它的速度太慢！下面把程序改成“每步取模”的形式，然后加一个“计时器”，看看究竟有多慢。程序2-8阶乘之和（2）#includestdio.h#includetime.hintmain(){constintMOD=1000000;intn,S=0;scanf(%d,&n);for(inti=1;i=n;i++){intfactorial=1;for(intj=1;j=i;j++)factorial=(factorial*j%MOD);S=(S+factorial)%MOD;}printf(%d\n,S);printf(Timeused=%.2f\n,(double)clock()/CLOCKS_PER_SEC);return0;}上面的程序再次使用到了常量定义，好处是可以在程序中使用代号MOD而不是常数1000000，改善了程序的可读性，也方便修改（假设题目改成求末5位正整数之积）。这个程序真正的特别之处在于计时函数clock（）的使用。该函数返回程序目前为止运行的时间。这样，在程序结束之前调用此函数，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。提示2-17：可以使用time.h和clock（）函数获得程序运行时间。常数CLOCKS_PER_SEC和操作系统相关，请不要直接使用clock（）的返回值，而应总是除以CLOCKS_PER_SEC。输入“20”，按Enter键后，系统瞬间输出了答案820313。但是，输出的Timeused居然不是0！其原因在于，键盘输入的时间也被计算在内——这的确是程序启动之后才进行的。为了避免输入数据的时间影响测试结果，可使用一种称为“管道”的小技巧：在Windows命令行下执行echo20|abc，操作系统会自动把20输入，其中abc是程序名(8)。如果不知道如何操作命令行，请参考附录A。笔者建议每个读者都熟悉命令行操作，包括Windows和Linux。在尝试了多个n之后，得到了一张表，如表2-1所示。表2-1程序2-8的输出结果与运行时间表由表2-1可知：第一，程序的运行时间大致和n的平方成正比（因为n每扩大1倍，运行时间近似扩大4倍）。甚至可以估计n＝106时，程序大致需要近5个小时才能执行完。提示2-18：很多程序的运行时间与规模n存在着近似的简单关系。可以通过计时函数来发现或验证这一关系。第二，从40开始，答案始终不变。这是真理还是巧合？聪明的读者也许已经知道了：25！末尾有6个0，所以从第5项开始，后面的所有项都不会影响和的末6位数字——只需要在程序的最前面加一条语句“if（n＞25）n＝25；”，效率和溢出都将不存在问题。本节展示了循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。这两个问题都不是那么容易解决的，将在后面章节中继续讨论。另外，本节中介绍的两个工具——输出中间结果和计时函数，都是相当实用的。2.5注解与习题不知不觉，本章已经开始出现一些挑战了。尽管难度不算太高，本章的例题和习题已经出现了真正的竞赛题目——仅使用简单变量和基本的顺序、分支与循环结构就可以解决很多问题。在继续前进之前，请认真总结，并且完成习题。2.5.1习题习题2-1水仙花数（daffodil）输出100～999中的所有水仙花数。若3位数ABC满足ABC＝A3＋B3＋C3，则称其为水仙花数。例如153＝13＋53＋33，所以153是水仙花数。习题2-2韩信点兵（hanxin）相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入包含多组数据，每组数据包含3个非负整数a，b，c，表示每种队形排尾的人数（a＜3，b＜5，c＜7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100。输入到文件结束为止。样例输入：216213样例输出：Case1:41Case2:Noanswer习题2-3倒三角形（triangle）输入正整数n≤20，输出一个n层的倒三角形。例如，n＝5时输出如下：#########################习题2-4子序列的和（subsequence）输入两个正整数n＜m＜106，输出，保留5位小数。输入包含多组数据，结束标记为n＝m＝0。提示：本题有陷阱。样例输入：246553665536000样例输出：Case1:0.42361Case2:0.00001习题2-5分数化小数（decimal）输入正整数a，b，c，输出a/b的小数形式，精确到小数点后c位。a，b≤106，c≤100。输入包含多组数据，结束标记为a＝b＝c＝0。样例输入：164000样例输出：Case1:0.1667习题2-6排列（permutation）用1，2，3，…，9组成3个三位数abc，def和ghi，每个数字恰好使用一次，要求abc：def：ghi＝1：2：3。按照“abcdefghi”的格式输出所有解，每行一个解。提示：不必太动脑筋。下面是一些思考题。题目1。假设需要输出2，4，6，8，…，2n，每个一行，能不能通过对程序2-1进行小小的改动来实现呢？为了方便，现把程序复制如下：1#includestdio.h2intmain()3{4intn;5scanf(%d,&n);6for(inti=1;i=n;i++)7printf(%d\n,i);8return0;9}任务1：修改第7行，不修改第6行。任务2：修改第6行，不修改第7行。题目2。下面的程序运行结果是什么？“！＝”运算符表示“不相等”。提示：请上机实验，不要凭主观感觉回答。#includestdio.hintmain(){doublei;for(i=0;i!=10;i+=0.1)printf(%.1f\n,i);return0;}2.5.2小结循环的出现让程序逻辑复杂了许多。在很多情况下，仔细研究程序的执行流程能够很好地帮助理解算法，特别是“当前行”和变量的改变。有些变量是特别值得关注的，如计数器、累加器，以及“当前最小/最大值”这样的中间变量。很多时候，用printf输出一些关键的中间变量能有效地帮助读者了解程序执行过程、发现错误，就像本章中多次使用的一样。别人的算法理解得再好，遇到问题时还是需要自己分析和设计。本章介绍了“伪代码”这一工具，并建议“不拘一格”地使用。伪代码是为了让思路更清晰，突出主要矛盾，而不是写“八股文”。在程序慢慢复杂起来时，测试就显得相当重要了。本章后面的几个例题几乎个个都有陷阱：运算结果溢出、运算时间过长等。程序的运行时间并不是无法估计的，有时能用实验的方法猜测时间和规模之间的近似关系（其理论基础将在后面介绍），而海量数据的输入输出问题也可以通过文件得到缓解。尽管不同竞赛在读写方式上的规定不同，熟练掌握了重定向、fopen和条件编译后，各种情况都能轻松应付。再次强调：编程不是看书看会的，也不是听课听会的，而是练会的。本章后面的上机编程习题中包含了很多正文中没有提到的内容，对能力的提高很有好处。如有可能，请在上机实践时运用输出中间结果、设计伪代码、计时测试等方法。