回 帖 发 新 帖 刷新版面

主题:第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超过整数的范围,结果不正确,只能表示遗憾了。

回复列表 (共9个回复)

沙发

恭喜恭喜。

neverPE的错误出在质因子少了两个,很是可惜啊,我觉得他的算法是最好的;我的程序的结果错误出在比较函数(没有考虑无符号数的比较)。至于楼主说我的第二份程序编译没通过,我查看了一下,原来是我第二次修改上传的时候,没有上传成功造成的。很抱歉,给楼主带来了测试的麻烦,呵呵。

板凳


呵呵  我自己也知道  自己算法上还有很大空白

在第2年希望能有充分的巩固吧   :)

最进编程目的就是练练手  不然生了就麻烦了 - -

呵呵  辛苦liangbch兄了    :)  [em12]

3 楼

辛苦了,liangbch兄

惭愧啊,
只是结果正确而已,算法太一般了(其实我已经到极限了)

4 楼

我得第一个程序有一个bug
在第二个程序中fix了
拜托比较一下 
http://www.programfan.com/club/showbbs.asp?id=188072

5 楼

liangbch兄辛苦了,这么多数据,我看到都晕了~呵呵

6 楼

ccpp果然牛人……有没有兴趣收我这个徒弟……呵呵

7 楼

应BigCarrot的要求,对其在 http://www.programfan.com/club/showbbs.asp?id=188072 的代码进行测试:测试结果如下:
  正确性测试,测试的10个数据全部通过,和ccpp的结果完全一样。
  速度方面:速度非常快,但仍不及boxertony提交的第二个程序有NeverPE的程序,以下是我在P4 2.6 256M,windows 2000环境下的测试结果。

boxertony2:  n=4000000000  time=0.000831560656 s
neverPE:     n=4000000000  time=0.000974125590 s
bigcarrot:2: n=4000000000  time=0.006621627333 s

8 楼

人气很旺,提交的人很多,liangbch兄测试辛苦了。
我这次交的程序完成比较匆忙,连注释都没写,抱歉了。boxertony兄居然专门花时间看这个没注释的程序,深感荣幸。程序错在没有真正用到最后一个素数19,最简单的修改就是加上一个素数23。

结果并不是最重要,但是有点遗憾的是没有看到让人眼睛一亮的算法,比如第36次的ccpp,和第37次10948452天才的程序。 

祝贺ccpp和boxertony,期待ccpp的第39次。

9 楼

楼住辛苦了!

我来回复

您尚未登录,请登录后再回复。点此登录或注册