亲，您未登录哦！ 登录 | 注册
首页  |  社区  |  工具箱  |  代码库  |  博客  |  招聘  |  文章  |  新闻  |  下载  |  读书
回 帖 发 新 帖 刷新版面

主题：第50次编程比赛结果

bpttc [专家分：8790] 发布于 2007-03-13 01:04:00

我首先谢谢大家的捧场和支持，重在参与，相信大家都很有收获。

第一轮先测试所有代码的正确性，筛走结果不正确的，有溢出现象的，不符合函数接口的，死循环的等等

后面的第二轮则是测试所以正确代码的运行速度。
丑媳妇总要见公婆，我的测试代码很简陋:(，请大家多多包涵

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX_SIZE     ( 50 )
#define N            ( 5 )
#define TEST_COUNT   ( 1e6 )

typedef long long INT64;

void HeroNeedThree(INT64* subset, unsigned int n);

int main(int argc, char *argv[])
{
        INT64 subset[MAX_SIZE];
        clock_t start, end;
        int test_data[] = { 1, 1e3, 1e6, 2221+1, 4999999+1,
                            0x100000, 0x1000000, 0x10000000, 0xFFFFFFFF, 0 };
        int i, j, k;
        

        for (i = 0; test_data[i] > 0; ++i)
        {
                printf( "%d\t", i );
                for ( j = 0; j < N; ++j)
                {
                        start = clock();
                        for ( k = 0; k < TEST_COUNT; ++k )
                        {
                                HeroNeedThree( subset, test_data[i] );
                        }
                        end = clock();
                        printf( "%d\t", (int)(end - start) );
                }
                printf( "\n" );
        }
        system( "pause" );
        return 0;
}

下面是每个人的测试结果：

3楼 雨中飞燕
0       0       15      16      15      16
1       203     203     219     203     203
2       359     360     359     359     375
3       219     203     219     203     219
4       406     422     438     437     406
5       453     438     453     438     453
6       531     531     547     531     532
7       625     625     625     625     625
请按任意键继续. . .

8楼 renew
0       15      16      15      16      16
1       140     125     141     125     141
2       250     250     250     234     250
3       125     125     125     109     125
4       282     265     266     281     266
5       281     297     297     281     297
6       328     344     328     344     343
7       391     406     406     391     406
请按任意键继续. . .

12楼 poorb
0       15      31      16      16      31
1       531     531     516     516     531
2       1391    1375    1390    1391    1390
3       469     469     469     468     469
4       1485    1500    1484    1484    1485
5       1765    1750    1797    1735    1734
6       2609    2610    2625    2609    2625
7       3641    3672    3656    3640    3672
请按任意键继续. . .

15楼 euc
0       250     234     250     234     250
1       282     265     281     282     265
2       297     297     313     296     297
3       250     266     266     265     266
4       281     297     281     297     281
5       344     344     344     328     343
6       344     344     344     359     344
7       375     359     360     359     359
请按任意键继续. . .

16楼 ghbxx2004
0       31      15      32      15      16
1       234     219     234     204     218
2       391     375     391     375     390
3       203     219     203     203     203
4       438     422     422     437     406
5       500     500     485     515     485
6       594     578     593     579     593
7       672     688     672     687     688
请按任意键继续. . .

19楼 eastcowboy
0       31      31      31      32      15
1       219     219     218     204     234
2       391     390     406     391     391
3       203     203     203     203     203
4       438     437     438     422     437
5       500     485     484     500     484
6       578     579     562     578     578
7       672     672     672     672     656
请按任意键继续. . .

20楼 iAkiak
0       359     344     359     359     360
1       750     750     750     765     750
2       954     953     937     953     953
3       672     657     671     672     672
4       1016    1031    1016    1000    1031
5       1422    1422    1422    1437    1406
6       1610    1625    1625    1609    1609
7       1829    1812    1813    1828    1812
请按任意键继续. . .

21楼 rickone
0       125     140     141     125     125
1       234     203     203     204     218
2       250     250     250     250     266
3       187     188     187     203     188
4       265     250     235     265     266
5       281     297     281     282     281
6       297     312     313     297     297
7       313     312     313     312     313
请按任意键继续. . .

22楼 medie2005
0       218     203     204     187     203
1       563     562     578     563     562
2       1422    1406    1438    1406    1406
3       485     484     469     484     469
4       1484    1469    1485    1500    1468
5       2094    2109    2094    2094    2094
6       2937    2953    2953    2922    2938
7       3969    3953    3968    3938    3984
请按任意键继续. . .

24楼 Kummerwu
0       125     125     110     125     109
1       250     250     250     234     250
2       297     297     297     297     312
3       203     204     187     203     203
4       313     281     313     296     297
5       360     375     359     375     375
6       406     407     406     437     407
7       437     422     422     437     422
请按任意键继续. . .

26楼 xchbcahz
0       15      0       16      15      32
1       1609    1625    1609    1594    1610
2       4328    4359    4328    4328    4328
3       1141    1109    1125    1125    1125
4       4704    4703    4718    4704    4718
5       7719    7688    7718    7703    7750
6       11110   11062   11032   11062   11078
7       14985   14984   14953   14984   15016

29楼 wuchengwei
0       15      0       16      15      32
1       2047    2062    2047    2031    2047
2       3078    3078    3063    3078    3047
3       1656    1672    1672    1672    1672
4       3250    3250    3250    3250    3250
5       4890    4891    4890    4907    4906
6       5766    5781    5781    5797    5781
7       6688    6687    6688    6687    6703


34楼 forjane
0       125     125     109     125     125
1       203     203     203     203     204
2       265     250     266     265     266
3       188     171     172     188     172
4       234     250     266     250     250
5       297     296     297     297     297
6       297     312     313     312     313
7       312     313     312     313     312
请按任意键继续. . .

39楼 BigCarrot
0       16      15      32      15      16
1       219     203     219     203     203
2       375     375     375     375     375
3       219     203     218     204     218
4       422     422     438     421     422
5       453     469     453     453     438
6       531     531     547     532     531
7       625     609     625     610     625
请按任意键继续. . .

41楼 wangfangbob
0       215     216     215     200     232
1       340     325     341     325     341
2       434     403     419     419     418
3       310     309     325     309     325
4       466     434     435     434     435
5       512     497     497     497     497
6       559     559     560     543     560
7       606     606     622     606     607
请按任意键继续. . .

43楼 szh
0       15      0       16      15      16
1       344     328     344     343     344
2       641     640     641     625     625
3       281     282     281     265     282
4       687     688     703     672     687
5       1110    1109    1109    1110    1109
6       1438    1468    1469    1438    1468
7       1844    1828    1844    1828    1844
请按任意键继续. . .

45 楼天边蓝
0       125     125     140     110     140
1       2047    2063    2062    2047    2062
2       3032    3015    3032    3000    3031
3       1672    1656    1672    1656    1656
4       3219    3547    3234    3235    3218
5       4672    4672    4641    4656    4656
6       5516    5516    5531    5531    5516
7       6406    6406    6391    6406    6422
请按任意键继续. . .

比较突出的就是8楼，15楼，21楼 24楼 34楼
其中8楼不仅对大N速度很快，当N较小时效率也很快，并且位移的手法很巧妙，所以第50次编程比赛的冠军就是[color=FF0000][size=3]renew[/size][/color]，大家祝贺一下他。
第51次编程比赛由renew来主持，请大家多多支持。
本帖地址：  http://bbs.pfan.cn/post/220708.html

回复列表 （共33个回复）

11 楼

Kummerwu [专家分：0] 发布于 2007-03-13 10:48:00

/********************************************************
*我把楼主的测试代码整合重测了一下，发现测试结果与楼主有很大的出入，
*是否是因为机器的不同导致的？
*下面是完整的测试代码，大伙可以拷贝到本地测试看看。
*

*感觉大数时15楼比较有优势，小数时8楼比较有优势
*而且测试数据中，大部分比特位都是0，正好比较适合8楼的口味:). [for (t = 0; m; m&=m-1) t++;循环次数比较少]
*所以测试结果比较好看.
*

*测试条件： VC6，Release版本（关闭系统的优化开关）
*           Win2k,SP4   CPU(2.6GHZ)
*测试结果：


8楼
0       16      16      0       15      16
1       78      125     94      94      93
2       203     188     187     204     203
3       109     109     94      109     110
4       218     204     234     203     219
5       203     219     234     203     219
6       266     265     266     250     266
7       297     281     265     282     281
8       297     297     297     297     296
请按任意键继续 . . .


15楼
0       219     218     235     218     235
1       250     234     250     250     235
2       265     266     266     281     265
3       219     235     218     250     235
4       266     266     265     235     281
5       250     266     250     265     266
6       250     250     266     265     250
7       235     265     250     250     282
8       265     250     266     250     266
请按任意键继续 . . .


21楼
0       125     140     141     141     140
1       250     235     234     266     250
2       344     343     328     329     343
3       250     235     265     250     250
4       329     343     344     344     344
5       422     406     422     422     406
6       438     453     453     422     437
7       484     500     500     485     500
8       532     562     610     531     562
请按任意键继续 . . .


24楼
0       188     219     250     203     187
1       203     219     234     250     203
2       250     266     281     266     234
3       219     188     203     203     187
4       266     250     250     250     250
5       297     266     297     281     297
6       265     297     297     266     281
7       297     297     281     297     281
8       297     313     297     281     281
请按任意键继续 . . .


34楼
0       204     187     219     187     204
1       281     297     297     281     266
2       375     375     359     375     375
3       266     234     266     250     265
4       375     391     406     375     391
5       421     422     438     437     454
6       484     500     500     484     501
7       562     563     578     562     563
8       547     547     578     547     562
请按任意键继续 . . .
************************************************************/

12 楼

Kummerwu [专家分：0] 发布于 2007-03-13 10:49:00

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef __int64 INT64;
typedef __int64 BIGINT;


#define MAX_SIZE     ( 50 )
#define N            ( 5 )
#define TEST_COUNT   ( 1e6 )

static INT64 ThreePower[] = 
    {
        1,              3,              9,              27,
        81,             243,            729,            2187,
        6561,           19683,          59049,          177147,
        531441,         1594323,        4782969,        14348907,
        43046721,       129140163,      387420489,      1162261467,
        3486784401,     10460353203,    31381059609,    94143178827,
        282429536481,   847288609443,   2541865828329,  7625597484987,
        22876792454961, 68630377364883, 205891132094649,617673396283947,
    };


/////////////8楼////////////////////////////
void HeroNeedThree_8(BIGINT* subset, unsigned int n)
{
    int t, p;
    unsigned int m;
    m = n-1;
    for (t = 0; m; m&=m-1) t++;
    p = 0; m = n-1; subset[0] = t;
    while (t)
    {
        if (m & 1) subset[t--] = ThreePower[p];
        p++;
        m >>= 1;
    }
}
//////////////  15 楼/////////////////// 
void HeroNeedThree_15 (INT64* subset, unsigned int n)
{
    static INT64 three[41];
    static bool ini = false;

    if (ini == false) {
        INT64 a = 1;
        for (int i = 0; i < 41; ++i, a*=3) {
            three[i] = a;
        }
        ini = true;
    }

    int bitn = 31;
    unsigned int mask = (1 << 31);

    for (; bitn >= 0 && ((mask&n)==0); --bitn, mask >>= 1);

    int amount = 0;
    for (int i = 1; bitn >= 0; mask>>=1, --bitn) {
        if (n > mask) {
            subset[i] = three[bitn];
            amount++;
            n -= mask;
            i++;
        }
    }
    subset[0] = amount;
}


//////////////// 21 楼//////////////////////////////
void HeroNeedThree_21(INT64* subset, unsigned int n)
{
    // base3[k]=3^k
    static INT64 base3[32]=
    {
        0x1,0x3,0x9,0x1b,0x51,0xf3,0x2d9,0x88b,
        0x19a1,0x4ce3,0xe6a9,0x2b3fb,0x81bf1,0x1853d3,0x48fb79,0xdaf26b,
        0x290d741,0x7b285c3,0x17179149,0x4546b3db,0xcfd41b91,0x26f7c52b3,0x74e74f819,0x15eb5ee84b,
        0x41c21cb8e1,0xc546562aa3,0x24fd3027fe9,0x6ef79077fbb,0x14ce6b167f31,0x3e6b41437d93,0xbb41c3ca78b9,0x231c54b5f6a2b
    };
    // base2[k]=2^k
    static unsigned int base2[32]=
    {
        0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,
        0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
        0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
        0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000
    };
    INT64 num=0;
    n--;
    for(int i=31;i>=0;--i)
    {
        if(n & base2[i]) // 计算n的第i位上是否是1
        {
            subset[++num]=base3[i];
        }
    }
    subset[0]=num;
}

13 楼

Kummerwu [专家分：0] 发布于 2007-03-13 10:50:00


//////////// 24楼 /////////////////////////////////////////
void HeroNeedThree_24(INT64* subset, unsigned int n)
{
    static INT64 s_HelperCount[] = 
    {
        1,              3,              9,              27,
        81,             243,            729,            2187,
        6561,           19683,          59049,          177147,
        531441,         1594323,        4782969,        14348907,
        43046721,       129140163,      387420489,      1162261467,
        3486784401,     10460353203,    31381059609,    94143178827,
        282429536481,   847288609443,   2541865828329,  7625597484987,
        22876792454961, 68630377364883, 205891132094649,617673396283947,
    };


    int idx = 32;
    int cnt = 0;

    n--;
    while(idx>0)
    {
        idx--;
        if(((n)&(1<<(idx))))
        {
            cnt++;
            subset[cnt] = s_HelperCount[idx];
        }
        
        
    }
    subset[0] = cnt;
}

/////////////////////34 楼///////////////////////////////////////////
void HeroNeedThree_34(INT64* subset, unsigned int n)
{
    static INT64 powof3[32];
    static int initialized=0;
    int i;
    if(!initialized)
    {
        //你也可以在定义时直接初始化这个数组,如果你有耐心写一堆数字的话^_^
        for(i=1,powof3[0]=1;i<32;i++)
        {
            powof3[i]=powof3[i-1]*3;
        }
        initialized=1;
    }

    for(i=31,subset[0]=0,n--;i>=0;i--)
    {
        if(n&(1<<i)) //检查对应2进制位是否为1
        {
            subset[++subset[0]]=powof3[i];
        }
    }
}

//////////////////////////////////////////////////////
#define Test(FUNC,Info) \
do{\
    printf("\n\n%s\n",Info);\
for (i = 0; test_data[i] !=0; ++i)\
        {\
                printf( "%d\t", i );\
                for ( j = 0; j < N; ++j)\
                {\
                        start = clock();\
                        for ( k = 0; k < TEST_COUNT; ++k )\
                        {\
                                FUNC( subset, test_data[i] );\
                        }\
                        end = clock();\
                        printf( "%d\t", (int)(end - start) );\
                }\
                printf( "\n" );\
        }\
        system( "pause" );\
}while(0)


int main(int argc, char *argv[])
{
        INT64 subset[MAX_SIZE];
        clock_t start, end;
        int test_data[] = { 1, 1e3, 1e6, 2221+1, 4999999+1,
                            0x100000, 0x1000000, 0x10000000, 0xFFFFFFFF, 0 };
        int i, j, k;
        
        Test(HeroNeedThree_8,  "8楼");
        Test(HeroNeedThree_15, "15楼");
        Test(HeroNeedThree_21, "21楼");
        Test(HeroNeedThree_24, "24楼");
        Test(HeroNeedThree_34, "34楼");
        
        return 0;
}

14 楼

bpttc [专家分：8790] 发布于 2007-03-13 10:59:00

[quote][quote][quote]貌似少测试了一组... 0xffffffff[/quote]

int test_data[] = { 1, 1e3, 1e6, 2221+1, 4999999+1,
                            0x100000, 0x1000000, 0x10000000, 0xFFFFFFFF, 0 };

有啊[/quote]

嗯，判断条件写错了,没有测试0xFFFFFFFF[/quote]

呵呵 忘记了test_data有符号的 原先是!=0的，居然改错了，罪过 罪过

15 楼

wuchengwei [专家分：1650] 发布于 2007-03-13 11:02:00

没建表就是吃亏

16 楼

ccpp [专家分：9360] 发布于 2007-03-13 11:27:00

不但忘了定义成INT64，
还忘了考虑1的情况。
顶[em3]。

17 楼

wuchengwei [专家分：1650] 发布于 2007-03-13 12:11:00

我的建了表后会快很多，

冠军的代码若改成
void HeroNeedThree(INT64* subset, unsigned int n)
{
    int i,pos=31;

    for(--n, i=0; n; pos--)
    {
        if(n&(1<<pos))
        {
            subset[++i]=ThreePower[pos];
            n&=~(1<<pos);
        }
    }
    subset[0]=i;    
}
不知道会不会更快些

18 楼

Kummerwu [专家分：0] 发布于 2007-03-13 12:20:00


wuchengwei的测试结果(Release 关闭优化开关）
0       15      16      15      16      16
1       593     579     593     579     578
2       765     782     750     781     797
3       578     594     562     563     562
4       844     844     860     843     829
5       844     875     891     859     860
6       968     969     969     1000    984
7       1079    1078    1078    1078    1032
8       1109    1094    1125    1125    1109
请按任意键继续 . . .

19 楼

wuchengwei [专家分：1650] 发布于 2007-03-13 12:24:00

我的上面测试的没超过400的

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

#define MAX_SIZE     ( 50 )
#define N            ( 5 )
#define TEST_COUNT   ( 1e6 )
typedef long long INT64;

INT64 ThreePower[32]={1};
void HeroNeedThree(INT64* subset, unsigned int n)
{
    int i,pos=31;

    for(--n, i=0; n; pos--)
    {
        if(n&(1<<pos))
        {
            subset[++i]=ThreePower[pos];
            n&=~(1<<pos);
        }
    }
    subset[0]=i;    
}

int main(int argc, char *argv[])
{
        INT64 subset[MAX_SIZE];
        clock_t start, end;
        int test_data[] = { 1, 1e3, 1e6, 2221+1, 4999999+1,
                            0x100000, 0x1000000, 0x10000000, 0xFFFFFFFF, 0 };
        int i, j, k;
        for(i=1; i<32;i++)
        {
                 ThreePower[i]=ThreePower[i-1]*3;
        }

        for (i = 0; test_data[i]; ++i)
        {
                printf( "%d\t", i );
                for ( j = 0; j < N; ++j)
                {
                        start = clock();
                        for ( k = 0; k < TEST_COUNT; ++k )
                        {
                                HeroNeedThree( subset, test_data[i] );
                        }
                        end = clock();
                        printf( "%d\t", (int)(end - start) );
                }
                printf( "\n" );
        }
        system( "pause" );
        return 0;
}

20 楼

Kummerwu [专家分：0] 发布于 2007-03-13 12:50:00

[quote]我的上面测试的没超过400的[/quote]
呵呵，不好意思，代码拷贝错误。
wuchengwei
0       15      0       16      15      16
1       250     266     234     328     235
2       312     328     344     359     313
3       234     235     281     219     219
4       312     328     344     297     297
5       375     390     375     391     375
6       406     391     422     406     391
7       437     438     422     437     438
8       437     454     453     469     453
请按任意键继续 . . .
这时在我机器上的测试结果，因为机器不同，测试结果可能不同，与前面我测试时使用的是同一个环境，具有可比性

我来回复

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

程序员工具箱 new

  • 通用文本转换
  • 域名whois查询
  • XML格式化压缩
  • Meta标签生成工具
  • 文本转图片
  • useragent工具
  • JavaScript库CDN服务
  • UNIX时间戳转换
  • PHP手册
  • 在线抽奖
  • 更多工具

    • 代码片段

  • 模拟键盘（不可按）
  • 碰撞的唐三
  • 精彩奥运热点赛事的实时采集
  • 获取天气动态信息
  • 文件查找
  • python大数据抓取京东电脑销量数据
  • 爬虫技术不仅仅支持数据采集
  • 抓取脉脉APP上的职业信息
  • 爬虫中多线程的运用
  • 四则运算以及一元二次方程
  • 欢迎来共享你的NB代码

    • 本版新帖

  • 以前写的一个String类
  • 产生哈夫曼编码的源代码
  • 两极大数运算，源程序示例
  • 冰玉的原代码在这里，主要参考《电脑爱好者》及《c游戏编程从入门到精通》，没有时间，你可以参考！哈哈。
  • 那位高手指教如何用Turbo c调用.pcx图象文件
  • 24点中的不可能组合
  • 求任意多个整数的公倍数
  • 算24点全集之程序
  • TURBO C 2.0的汉化文件！
  • 10点半游戏
  • 高手心得（转载）！
  • 有没人会二叉树的生成啊?????十万火急
  • 广义表类
  • 树类
  • 一些有关递归回溯的程序