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和条件编译后,各种情况都能轻松应付。再次强调:编程不是看书看会的,也不是听课听会的,而是练会的。本章后面的上机编程习题中包含了很多正文中没有提到的内容,对能力的提高很有好处。如有可能,请在上机实践时运用输出中间结果、设计伪代码、计时测试等方法。

1 / 4
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功