回 帖 发 新 帖 刷新版面

主题:[讨论]第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个回复)

沙发

题目标准算法:
/*
 *把个数可能超过半数的自然数,称为候选数。
 *用 个数抵消,但数目相对多的自然数一定能存活下来 的思想: 
 *按顺序遍历数组,并选定第一个数为候选数,如果下一个自然数等于候选数,那个其个数
 *加1,否则其个数减 1(个数抵消)。当候选数当前个数为0时,
 *我们就选定下一数为候选数,这样遍历结束时,如果最后那个候选数的个数不为0, 
 *那么我们可以相信倘若数组的确存在超过半数的自然数,
 *那么它一定是最后的那个候选数。 
 * 
 *第一次遍历数组,可找出候选数(若个数大于半数,不管怎么抵消,一定能活下来)。 
 *第二次遍历数组,计算候选数的个数,确定是否超过半数。 
 */
int majority(int vote[], int n)
{
     int  candidate;          // 当前候选自然数 i        
     int  vote_count;         // 当前候选数 i 的当前个数         
     int  count;              // 最后确定的候选数 i的实际个数
     int  i;

     candidate  = vote[0];    // 选定数组第一个元素为候选数 
     vote_count = 1;          // 候选数的当前个数为 1个      
     for (i = 1; i < n; i++){ // 遍历数组元素
         if (vote_count == 0) {// 如果候选数当前个数为 0个 
              candidate  = vote[i]; // 那么选定下一个数为候选数
            vote_count = 1;   // 
           }
        else if (candidate == vote[i]) //如果下一个数等于当前候选数
            vote_count++;     // 那么候选数当前个数加 1     
        else
            vote_count--;     // 如果不等于,那么当前个数减 1  
     }
     if (vote_count == 0)     // 如果最后候选数当前个数为零,
          return 0;           // 那么它的个数一定小于半数
          
     for (i = 0, count = 0; i < n; i++) 
          if (vote[i] == candidate)
                    count++;  //计算候选数的实际个数          
     return count > n/2 ? count : 0;
}
[color=000080]赠送题标准算法:[/color]
/*
 *当比较f[i]和g[j]时,不外乎有三种情况: 
 *1。f[i] < g[j], 如果f[]中有与g[j]相等的元素,那么一定在f[i]的后面, 
 *   亦即是f[i+1],f[i+2],...之一,所以下一次应该比较f[i+1]与g[j]。 
 *  (注意题目已知条件,两数组都已经从小到大排好,且数组内元素不相同) 
 *2。f[i] > g[j], 同以上类似分析,下一次应该比较f[i]与g[j+1]。  
 *3。f[i]等于g[j],count计数加 1, 下一次比较f[i+1]与g[j+1]。
 *
 *当其中一个数组比较完所以元素后,即可结束循环 。 
 */
int coincidence_count(int f[], int g[], int m, int n)
{
     int  index_f, index_g;     //数组f[]和g[]的脚码(下标) 
     int  count;                //相同元素的个数   

     count = index_f = index_g = 0;
     while (index_f < m && index_g < n)   //循环结束条件 
          if (f[index_f] < g[index_g])    //如果小于 
               index_f++;                 //增加f的脚码 
          else if(f[index_f] > g[index_g])//如过大于 
               index_g++;                 //增加g的脚码 
          else{                //如果相等
               count++; index_f++; index_g++;
              } 
     return count;
}

板凳

ccpp兄效率真高,辛苦了
哎,,算法又有问题,好慢

3 楼

neverPE牛人一个!!!

4 楼

[quote]ccpp兄效率真高,辛苦了
哎,,算法又有问题,好慢,可以给出1千万和一亿的测试数据马?[/quote]

测试数据是随机生成的,
 int n = 100000000,step = 10;
 int *vote = new int[n];//分配空间
 for(int i = 0; i < n; i++){ //生成测试数据 
        vote[i] = rand() % step + 1;
 } 

5 楼

写得少未必写得好啊。我以为我那样简洁是不错的,没想到......[em6]
ccpp兄,你不是说碰到我这样的热血少年会感动吗?[em21]


呵呵,输得确实心服口服,以前从没考虑过效率,都是写出来能跑就完事了。也不会用这么大的数组来测。
我的代码中排序部分如果用qsort()代替sort()是不是会快一些呢?
ccpp兄,能不能帮忙再测一下效率?我只是想看看那样有多快。

请教一下,
运行时间用time()测的吗?
学会了我自己测......

向冠军同志致敬!向ccpp兄致敬!!

6 楼

效率测试:
当数组的大小为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(左右)以下。
------------------------------

强烈支持。。。ccpp
程序 速度慢 是 意料之中的事。。

7 楼

[quote]
运行时间用time()测的吗?
学会了我自己测......
[/quote]
用C++编译器提供的clock函数。

#include<ctime>
using namespace std;
//include<time.h>

int t1,t2;

t1 = clock();//clock()返回程序运行的时间,毫秒
fun();//测试函数
t2 = clock();
cout << t2-t1 <<"ms"<<endl;//运行时间差,是函数fun运行的时间

8 楼

没想到晚上结果就出来了,人气越来越高,ccpp兄的效率也高。

另外,关于我程序运行时间的问题,数据是这样生成的vote[i] = rand() % 10 + 1;所以我的程序看起来比较快。但如果生成这样的数据vote[i] = i % 2 + 1,就需要1s左右的时间,此时且当n为偶数的时候,我的程序会比标准算法要慢一点。

9 楼

gohan_f28:
        =>Wrong,right is 6,but you get 0
       array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};

不是就是输出0吗?只有2个自然数嘛。ft,难道没读懂题目??

10 楼

neverpe太厉害了

我来回复

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