回 帖 发 新 帖 刷新版面

主题:[讨论]第39次编程比赛结果

第一题未通过测试的朋友:
liyanguestc_1f:
没有按要求编写函数:若存在这样的i(m个),函数Majority返回m,否则函数返回0。而你返回的是这个自然数 i。
tenm_7f:
方法比较直接,而且没有按要求编写函数:没有完整的计算可能存在的超过半数i的个数
batmanlf_10f:
    =>Wrong,right is 6,but you get 0
        array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wlsss_15f:
     =>Wrong,right is 6,but you get 4
        array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
joekings_f17:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有问题,参见完整代码。
ghbxx2004_f20:
没有按要求编写函数:题目已知 m > n/2,
而你的代码是 :if(m >= (n/2) ){return m;}
bloodybg_f21:(修改后,对你的程序进行了效率测试)
使用全局变量arrayNum时,
int Majority(int vote[], int n)
{
    //arrayNum = 0;//在调用函数Majority时arrayNum没有赋值为0
    int *a, *b;
    ...
//结果造成你的函数不能循环使用,
//原因是,在第二次调用函数Majority时,arrayNum的值不是0,而继续保存上一次的遗留值。
gohan_f28:
        =>Wrong,right is 6,but you get 0
       array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
hwjian_f31:
        =>Wrong,right is 6,but you get 10
       array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
天边蓝_f32:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有点繁琐,参见完整代码。
forjane_f42:
    =>Wrong,right is 6,but you get 0
       array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wksuper_f47:
没有按要求编写函数:没有计算可能存在的超过半数i的个数。
yelv_f49:
方法比较直接,而且没有按要求编写函数:没有没有完整的计算可能存在的超过半数i的个数。

大部分未通过测试的朋友,主要原因是没有按要求编写函数接口,或者写代码时过于疏忽,
因为上面的朋友使用的都是同一种算法:先排序,后查找并计数。
有完整的代码供大家参考,如下:(n=1千万时,耗时781 ms)
int Compare(const void*x, const void *y){ 
    return *(int*)x - *(int*)y;
}
int Majority (int vote[], int n)
{
   int i,j,half = n/2;
   int count = half+1;
   qsort(vote, n, sizeof(int), Compare);//排序 
   //sort(vote,vote+n);
   for(i = 0; i < int(n/2.0+0.5); i++){//平台式查找  
       if(vote[i] == vote[i + half]){          
              for(j = i + half + 1; j < n; j++){
                     if(vote[j] == vote[i]) 
                   ++count;//开始记数 
                       else
                            break;
                }
                return count;//计算完毕,结束函数
       }
   }
    return 0;
}

效率测试:
当数组的大小为2万时,一些朋友的程序开始见慢,
wlsss_4f:time cost is :3375 ms 
hyl084_f25:time cost is :5594 ms 
qingfengjianke_f46:time cost is :1640 ms
jihao111_f53:time cost is :3329 ms
而其他朋友的程序都能控制在 10ms(左右)以下。

当数组的大小为1千万时
jackin0627_3f:  938 ms 
01835cwj_6f:   2766 ms   
rickone_f18:    313 ms 
bloodybg_f21:   688 ms 
孤独的猫_f22:   531 ms 
天国龙_f23:     516 ms 
jxstudying_f24:1141 ms 
xyhx_f26:       860 ms 
火海时代_f27:  1375 ms 
SonicLing_f30: 8328 ms 
neverPE_35:       0 ms 
yunzhou008_f37:5000 ms 
amen_f41:      4078 ms 
wshong_f44:    1500 ms 
侍鱼_f48:       515 ms
liangbch:      172 ms
BigCarrot:     232 ms

[color=008000]当数组的大小为1亿(机器状态最好时)时
neverPE_35:       0 ms //为什么总是0,是不是编译器有问题!
liangbch:     1703 ms
BigCarrot:    2329 ms
题目标准算法:  830 ms[/color]

我宣布次数比赛的冠军是 [color=800000]neverPE 兄[/color],请neverPE 准备第40次编程比赛。

[color=000080]赠送题回复得人不多,且都使用了相似得算法,题目的标准算法也和大家的几乎一样。[/color]
P.S.测了一天了,几乎要崩溃了!如果测试结果有令大家不满意的地方,请多多见谅!

回复列表 (共29个回复)

21 楼

呵呵  老哥 辛苦了 喝口茶 :)

这次第一题没做 想法是和老哥一致的也是先用qsort排下后遍历一次

感觉都是qsort再做事 自己没写什么 就没去实现 别的高效的又没想到

只做了下赠送题 思路也是一致的 - -

还是比较对neverPE兄的第一题感兴趣 回头研究下[em1]
(没学过也没研究过概率算法  这下晕了)

22 楼

好题目,又学到了!

23 楼

Monte Carlo方法主要用于计算科学中的误差分析、多重积分、以及统计学科的计算中!

24 楼

看了neverPE的程序,有个问题想问:

程序中的 m=511 是根据理论推算出来的,还是通过实践检验出来的。。。

25 楼

先用qsort排一遍以后,就不用遍历了
假设存在一个超过半数的数的话,则vote[n/2]一定就是那个数
因为是顺序排好的,所以超过半数的数不管从哪边排一定能排到中间
然后可以用分治法向前找到第一个这个数,向后找到最后一个这个数
下标差加一就是这个数的个数,再判断和n/2的大小

26 楼

To szh:m次取样,元素出现频率成二项式分布(当m不太小,近似看成正态分布,比较好算),通过概率论的知识可以算出出错的概率。m=255时,用最可能出错的数据测试,错误率大约1e-3,所以我当时认为m=511时1e-6的错误率可以接受。用m=500,m=1000之类的也可以,但我比较喜欢2^n

To wlass:你的算法分为2部分,qsort时间复杂度为O(nlogn),后面一部分为O(n)。你的优化方法对后一部分非常有效,降到了O(logn),但对整体没影响。

27 楼

快排复杂度就是O(nlogn)了,其余部分不管怎么优化,整体复杂度不会小于O(nlogn)。

28 楼

不错不错,学习ing。

29 楼

标准算法的确厉害啊,这段代码收藏了

我来回复

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