主题:第38次编程比赛第1题结果
仅仅测试10,100,1000,10000,100000.10^6,10^7,10^8,10^9,4*10^9这十个数据。
关浩:对于几乎每一个n,结果都不正确
bigcarrot n=10000, 得到的结果是:9240, 正确的结果应是7560,
iakiak n=10000, 得到的结果是:9240, 正确的结果应是7560
jokings n=10,和n=1000都不正确, n=1000时, 得到的结果是:720, 正确的结果应是840
当n=1000000000,boxertony,boxertony:2 ,neverPE都能得到正确的结果,但当n=4000000000时,这几个程序的运行结果均有错误,正确的结果应是:3491888400,约数个数:1920
boxertony n=4000000000, 得到的结果是:2095133040,约数个数:1600
liyanguestc n=4000000000, 得到的结果是:2095133040,约数个数:1600
neverpe n=4000000000, 得到的结果是:3859455600,约数个数:1800,
boxertny:2 n=4000000000, 得到的结果和约数个数正确,但第一个约数为:3491888400
CCPP:对于测试用的每一个数据,均得到了正确的结果
第二部分:速度测度:测试环境, winxp+vc6, release版本,迅驰1.7G+256MB
上面5个程序能够计算到40亿,下表给出对所有的测试数据的运行速度,单位:秒
n 10 100 1000 10000 100000
boxertony:2 0.00001509 0.00001537 0.00000587 0.00000922 0.00003045
boxertony: 0.00000587 0.00001928 0.00002570 0.00001257 0.00004861
nevrPE: 0.00000279 0.00000447 0.00001062 0.00003436 0.00006928
ccpp: 0.00000168 0.00000140 0.00000335 0.00005252 0.00052046
liyanguestc:0.00000223 0.00000643 0.00009135 0.00043916 0.00482519
n 1000000 10000000 100000000 1000000000 4000000000
boxertony:2 0.00006034 0.00012627 0.00021874 0.00048190 0.00090207
neverPE: 0.00014583 0.00026121 0.00047604 0.00083921 0.00110377
liyanguestc 0.00528028 0.01643002 0.02104569 0.01936922 0.02473666
boxertony 0.00006817 0.00030982 0.00052884 0.00904892 0.00518278
ccpp 0.00639523 0.07418541 0.84192181 8.28413444 33.55162681
其它的一些程序,运行速度较慢,只给出了n<=100000时的运得时间,单位秒
n 10 100 1000 10000 100000 1000000
xyhx: 0.00000223 0.00000335 0.00003324 0.00027741 0.00542974 0.10319272
wshong: 0.00000140 0.00000140 0.00001900 0.00021651 0.00833318 0.24690708
wlsss:2 20.00001676 0.00005280 0.00060371 0.00978309 0.21565450 3.88031468
szh: 0.00001397 0.00000643 0.00004693 0.00255703 0.23082487 15.1256950
abcdxjs:2 0.00000223 0.00001201 0.00036345 0.01015883 0.26358573 5.87724193
freeeerf: 0.00000112 0.00000447 0.00019416 0.00570100 0.27625634 6.46042584
abcdxjs: 0.00000196 0.00002235 0.00035172 0.00941768 0.37579413 10.2762345
------------------------------------------------------------------------
jackin0627: 0.00001006 0.00005001 0.00205277 0.13284370 12.02666400
wlsss: 0.00000363 0.00007962 0.00307441 0.20188795 15.4070198
linxuanxu: 0.00003688 0.00007571 0.00750431 0.68107874 85.03517430
iter: 0.00000140 0.00025171 0.00565044 0.73974737 -----------
侍鱼: 0.00000223 0.00008688 0.00830078 0.78068386 89.63446723
mantiser: 0.00002347 0.00010001 0.01008089 0.90212415 108.6726159
可以看到,前7个程序,速度明显较快,复杂度大体为sqrt(n)*n,而后6个程序,速度很慢,复杂度大体为n*n,需要加强算法方面的训练
第三部分:一些其它问题:
1。以下几个程序,没按要求编写,因此没能进行测试。这次提交程序达到28个,测试者不可能去修改每一个程序去进行,下次注意。
libo93122
luyantie
magicalking
qiulihua83
seekmm
ysol
luyantie
2.joekings的程序在release编译不能运行,没有进行速度测试。
liyanguestc,程序有一些错误,不应该在Search函数中,以arr为参数进行分配和释放内存
mantiser, alTemp数组定义的太小,改为2000
boxertony:2: 程序不能通过编译,增加了一个数组定义,并对 countDivisort的调用语句做了修改得以编译通过。
综合以上情况,我宣布,本次编程比赛的[color=FF0000]冠军为ccpp[/color]. boxertony提交的第二个程序,当n=4000000000时,能够得正确的结果,仅仅约数的排列顺序有误,错误较小,且速度最快,故本次比赛的优胜奖授于boxertony.上上届冠军得主neverPE的程序算法不错,且很简洁,但当n超过整数的范围,结果不正确,只能表示遗憾了。

您所在位置:



