欢迎来到天天文库
浏览记录
ID:21190691
大小:77.50 KB
页数:4页
时间:2018-10-20
《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位数字一一只需要在程序
此文档下载收益归作者所有