主题：第74次比赛结果
天边蓝 [专家分：1810] 发布于 2008-10-21 10:02:00
第一题：
测试分为10个实例，n分别为2,10,100,1000,10000,100000,500000,1000000,5000000,10000000，序列数据为随机生成，下面是测试结果：
2楼 fenix124 220ms
4楼 flushtime 290ms
5楼 strugglemyself 结果错误
7楼 debroa723 3020ms
10楼 red999 结果错误 会死循环
12楼 goal00001111 >1m
15楼 zhangyuke 结果错误
16楼 toto996 1200ms
20楼 gangmae 结果错误
21楼 flushtime 结果错误
第二题所有代码都不合要求，经过简单的修改后只有7楼debroa723能通过简单的测试。
所以，我宣布本次比赛的冠军为debroa723，请他主持下次的编程比赛，大家鼓掌！！
回复列表 （共18个回复）
沙发
red999 [专家分：20] 发布于 2008-10-21 10:17:00
哎呀，还是顶一个
楼主能不能把测试数据放出来，大家也自己可以试试看看，自己改改，这样也能学到些东西
板凳
天边蓝 [专家分：1810] 发布于 2008-10-21 11:32:00
第一题的数据是随机生成的：
void getData(int array[],int n){
srand(time(0));
assert((n&1)==0);
array[0]=array[1]=rand()%100;
for(int i=1;i<n/2;i++)
array[2*i]=array[2*i+1]=array[2*i-1]+15;
array[rand()%n]=array[n-1]+15;
for(int i=0;i<n/4;i++)
swap(array[rand()%n],array[rand()%n]);
}
第二题本想在POJ上直接测试的，可突然换了环境，上不了POJ，所以就简单的写了几个实例。很抱歉，最近比较忙，有些代码没仔细看，如果有什么遗漏还望提出来……
3 楼
flushtime [专家分：200] 发布于 2008-10-21 13:18:00
囧，貌似我21楼代码中把 &与 ==的优先级搞错了
把
for(idx =0;mask&(1<<idx)==0;idx ++);
改成
for(idx =0;(mask&(1<<idx))==0;idx ++);
应该就好了。
偷懒想少些个括号，没想到就错了[em10]
4 楼
flushtime [专家分：200] 发布于 2008-10-21 13:19:00
如果是用Java，这种错误编译的时候就会报错了。。。
5 楼
boxertony [专家分：23030] 发布于 2008-10-21 14:41:00
4楼的算法不错，速度上与2楼非常接近，但存在一些问题，对于某些数据会陷入死循环。比如当
array[] = {4,3,2,2,1,4}时就会死循环。
6 楼
flushtime [专家分：200] 发布于 2008-10-21 15:18:00
嗯，是有这种情况，
partition函数，确切的讲是那个mid函数有点问题。
可以修正，把mid函数改成从5个数中选一个中值。或者像quick sort一样，当size 比较小的时候直接暴力求解。
7 楼
boxertony [专家分：23030] 发布于 2008-10-21 15:52:00
不是mid函数的问题，5选1虽然可以减少死循环发生的几率，但并不能杜绝；当size比较小暴力求解也不能解决问题，因为当size很大也同样可能陷入死循环。关键是你用来划分的循环存在漏洞。
8 楼
flushtime [专家分：200] 发布于 2008-10-21 16:39:00
这个倒没发觉，我还以为是因为mid取值时可能会取到边界值引起的……
9 楼
boxertony [专家分：23030] 发布于 2008-10-21 18:54:00
抱歉，我弄错了，5选1可以避免死循环（因为有题目的限制条件），但需要对4个的情况进行特殊处理。
10 楼
c++学者 [专家分：100] 发布于 2008-10-21 19:42:00
我想问楼主 怎眼测试一个程序的速度？
我来回复
您所在位置：