noip竞赛循环代价

《noip竞赛循环代价》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2.3循环的代价例题2-4阶乘之和输入n，计算5=1!+2!+3!+...+n!的末6位(不含前导0)。n<106,n!表东前r?个正整数之积。样例输入：10样例输出：37913【分析】这个任务并不难，引入累加变量S之肜，核心算法只宥"for(inti=l;i<=n；i++)s+=i!〃。不过，C语言并没有阶乘运算符，所以这句话只是伪代码，而不是真正的代码。事实上，还需要一次循环来计算i!，即"for(intj=l；j<=i；j++)factorial*=j；"o代码如下:程序2-7阶乘之和(1)#includeintmain(){intn,S=0;scanf("%

2、d",&n);for(inti=1;i<=n;i++){intfactorial=1;for(intj=1;j<=i;j++)factorial*=j;S+=factorial;}printf("%dS%1000000);return0;}注意累乘器factorial(英文"阶乘〃的意思)定义在循环里面。换句话说，每执行一次循环体，都要重新声明一次factorial,并初始化为1(想一想，为什么不是0)。因为只要末6位，所以输出时对106取模。提示2-15:在循环体开始处定义的变量，每次执行循环体时会重新声明并初始化。有丫刚才的经验，下面来测试一下这个程序：n=100吋，输出-

3、961703。直觉告诉我们：乘法又溢出了。这个直觉很容易通过"输出中间变量"法得到验证，但若要解决这个M题，还需要一点数学知识。提示2-16:耍计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变。在修正这个错误之前，还可以进行更多测试：当n=106吋输出什么？更会溢出不是叼？但是重点不在这里。事实上，它的速度人慢！下面把程序改成"每步取模〃的形式，然后加一个"计吋器〃，看看究竞宥多慢。程序2-8阶乘之和(2)#include#includeintmain(){constintMOD=1000000;intn

4、,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,,JS);printf("Timeused=%.2f"(double)clock()/CLOCKS_PER_SEC);return0;}上面的程序再次使用到了常量定义，好处是可以在程序中使用代号MOD而不是常数1000000,改善Y程序的可读性，也方便修改(假设题□改成求末5位正整数之积)。这个程序真正的特别

5、之处在于计吋函数clock()的使用。该函数返回程序目前为止运行的时间。这样，在程序结束之前调用此函数，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以"秒〃为单位。提示2-17:可以使用time.h和clock()函数获得程序运行时间。常数CLOCKS_PER_SEC和操作系统相关，请不要直接使用clock()的返回值，而应总是除以CLOCKS_PER_SEC。输入"20〃，按Enter键后，系统瞬间输出了答案820313。但是，输出的Timeused居然不是0!其原因在于，键盘输入的时间也被计算在内一一这的确是程序启动之厄才进行的。为了避免输

6、入数裾的时间影响测试结果，可使用一种称为"管道〃的小技巧：在Windows命令行下执行echo20

7、abc，操作系统会自动把20输入，其中abc是程序名I如果不知道如何操作命令行，请参考附录A。笔者建议每个读者都熟悉命令行操作，也拈Windows和Linux。在尝试丫多个A7之后，得到了一张表，如表2-1所示。农2-1程序2-8的输出结泶.4/运行吋則农n20408016016006400128002560051200答案820313940313940313940313940313940313940313940313940313时间<0.01<0.01：0.01<0.010.050.

8、702.7()11.0843.72由表2-1吋知：第一，程序的运行时间大致和n的平方成正比(因为n每扩大1倍，运行吋间近似扩大4倍)。甚至可以估计n=106时，程序大致需要近5个小时才能执行完。提示2-18:很多程序的运行时间与规模n存在着近似的简单关系。可以通过计时函数来发现或验证这一关系。第二，从40开始，答案始终不变。这是真理还是巧合？聪明的读者也许已经知道了：25!末尾冇6个0,所以从第5项开始，后面的所冇项都不会影响和的末6位数字一一只需要在程序