第31次编程比赛结果 — 编程爱好者社区

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

boxertony [专家分：23030] 发布于 2006-06-18 15:57:00

第二题结果：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
iAkiak:@4
    Correct. Total time cost: 8992ms for 10 data groups.
    好像重复运算太多，如果能去掉冗余运算，速度应该还会有提升。

fenix124:@5
    Correct. Total time cost: 10ms for 10 data groups.
    事先计算出范围内所有的数据，所以速度最快，空间耗费也是够大的，但对于本题来说还是值得的。

fantasyzzz:@7
    栈溢出。递归层次太深。

KelSat(kcalf):@8
    本来对于转换步数不大于10的数据结果是正确的，但由于静态变量k造成一旦对于某组数据没有得出正确结果，后面的所有数据结果就全部错误。

太没劲了:@9
    Correct. Total time cost: 2313ms for 10 data groups.

int0x080:@11
    Correct. Total time cost: 87295ms for 10 data groups.

天国龙:@12
    Wrong at n=  1 m=563. Your answer: 2147483647(), should be:   27(gggfffggggfffffggffggggffff).
    Wrong at n=193 m=808. Your answer: 2147483647(), should be:   34(gfgggggfffffgggfggffgffgfgffgggggg).
    Wrong at n=585 m=479. Your answer: 2147483647(), should be:   26(ggfffgggfggffgffgfgfgggggg).
    Wrong at n=350 m=895. Your answer: 2147483647(), should be:   27(gffgfgfgggfggggggffffffgggg).
    Wrong at n=822 m=746. Your answer: 2147483647(), should be:   31(ggggfggfgfgffgffgfffgffgggggggg).
    Wrong at n=174 m=858. Your answer: 2147483647(), should be:   23(fgfggffgffgfgfffggggggg).
    Total time cost: 1311ms for 10 data groups.
    在限定的范围内结果都正确。

bvor:@13
    在步数比较少的时候正确。在步数比较大的时候因为太慢没有计算最终结果。

goal00001111:@14
    Wrong at n=  1 m=563. Your answer: 2147483647(), should be:   27(gggfffggggfffffggffggggffff).
    Wrong at n=193 m=808. Your answer: 2147483647(), should be:   34(gfgggggfffffgggfggffgffgfgffgggggg).
    Wrong at n=585 m=479. Your answer: 2147483647(), should be:   26(ggfffgggfggffgffgfgfgggggg).
    Wrong at n=350 m=895. Your answer: 2147483647(), should be:   27(gffgfgfgggfggggggffffffgggg).
    Wrong at n=822 m=746. Your answer: 2147483647(), should be:   31(ggggfggfgfgffgffgfffgffgggggggg).
    Wrong at n=174 m=858. Your answer: 2147483647(), should be:   23(fgfggffgffgfgfffggggggg).
    Total time cost: 1892ms for 10 data groups.
        在限定的步数范围内结果均正确。

pigeonoo:@15
    栈溢出。递归层次太深。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

我宣布本次比赛的冠军为fenix124。请fenix124安排下次比赛事宜。

本帖地址： http://bbs.pfan.cn/post/175897.html

回复列表（共26个回复）

11 楼

boxertony [专家分：23030] 发布于 2006-06-18 20:09:00

[quote]
我这个压根没有做缓冲，@fenix124 那样的方式在大数据量时理应快些的。能达到一个数量级估摸跟你那测试数据还有关系，他说总共也就几秒遍历整个，俺这个可不成。具体算法我明天简单说说，其实我的两个代码里都有一个 bug，不过在你这个输入范围内暴露不出来，为了快点俺就没改，:P[/quote]
与我的测试数据应该没有关系,我的数据是随机生成的.fenix124的速度之所以没有显得比你的快很多，那是因为它的主要时间花在calc函数上，而calc函数与n值相关，这样每次计算(n->m）都需要重新calc。当然，如果每次保持n值不变，这样不需要每次重新调用calc函数的话，速度上肯定会比你的程序快的很多。

你说的bug指的是parent[curv]的curv可能越界吗？这到确实有此可能，呵呵。

12 楼

goal00001111 [专家分：4030] 发布于 2006-06-18 20:48:00

那楼主看看我的8楼的程序速度如何?
我仿照fenix124的,但感觉比他的简洁,而且我的MAXSIZE取30000,可以处理大于1000的数据,当然对速度有影响,如果是比较速度,你可以把MAXSIZE改成20000看看.

13 楼

boxertony [专家分：23030] 发布于 2006-06-18 20:57:00

我把太没劲了的2楼的程序稍作修改后，速度略快语fenix124的程序。
int transform(int n, int m, char *fs)
{
    static short ref[32768], parent[32768];
    short lnuml[256],lnum_cur,refcur=0;
    char getflag;
    int num=INT_MAX;

    memset(parent,0,sizeof(parent));
    ref[0] = m, refcur = 1;
    getflag=0, lnum_cur=0;
    lnuml[lnum_cur++] = 0, lnuml[lnum_cur++]=1;
    do
    {
        for(short i=lnuml[lnum_cur-2] ; !getflag && i<lnuml[lnum_cur-1]; ++i)
        {
            int src = ref[i],curv;

            curv = (src<<1);
            if(!getflag && curv>src && !parent[curv])
                ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
            if(!getflag && (++curv)>src && !parent[curv])
                ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);

            curv = src / 3;
            if( !getflag && (curv*3==src) && !parent[curv] )
                ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
        }
        if( getflag )
        {
            short j=refcur-1,cur,prev,k;

            cur = ref[j];
            for(k=0; j>0 && (k+2)<=lnum_cur; ++k)
            {
                prev = parent[cur];
                fs[lnum_cur-k-2] = 'f'+(cur>prev), cur = parent[cur];
            }

            fs[k] = 0, num = k;
        }
        else lnuml[lnum_cur++] = refcur;
    } while(!getflag && lnum_cur<250);

    return(num);
}

14 楼

boxertony [专家分：23030] 发布于 2006-06-18 21:04:00

[quote]那楼主看看我的8楼的程序速度如何?
我仿照fenix124的,但感觉比他的简洁,而且我的MAXSIZE取3000,可以处理大于1000的数据,当然对速度有影响,如果是比较速度,你可以把MAXSIZE改成2000看看.

[/img]http://www.cppblog.com/goal00001111/gallery/image/753.html[/img][/quote]
出现栈溢出。

15 楼

fenix124 [专家分：70] 发布于 2006-06-18 21:32:00

我的那个算法的确是可以证明的.
每到一个数时可以由他直接产生两个数，如果得到的数没有出现过，那么路径一定是最短的。

顺便说一下，某个回帖的数据的测试情况：
#include <stdio.h>

int main()
{
    char ch[] = "gggggfggfgfggfff";
    int a,p;
    a = 916;
    p = 0;
    while(ch[p])
    {
        if(ch[p] == 'g') a = a/2;
        else a = a*3;
        printf("%d\n",a);
        p++;
    }
    return 0;
}

//运行结果
458
229
114
57
28
84
42
21
63
31
93
46
23
69
207
621
Press any key to continue

16 楼

boxertony [专家分：23030] 发布于 2006-06-18 21:52:00

to fenix124:
你的测试过程不对。函数计算是从右侧开始进行的，你从左侧开始了。
916
2748
8244
24732
12366
6183
18549
9274
27822
13911
6955
20865
10432
5216
2608
1304
652

17 楼

boxertony [专家分：23030] 发布于 2006-06-18 21:56:00

这个题你的程序出现错误的原因估计是因为你的程序限制最大值不能超过20000造成的，从上面的数据可以看到数据完全可以超出20000的。

18 楼

fenix124 [专家分：70] 发布于 2006-06-18 22:10:00

看出来了,最先设上限的时候看20000的时候所有的结果能算出来，就没有继续管了。
如果上限设大些，速度慢很多了。
但是实际上小了,郁闷...
没有水过去...

既然我的程序有错,那么下一次出题的人换一个吧

19 楼

sllone [专家分：150] 发布于 2006-06-18 22:22:00

[quote]大家帮忙看看这个为什么不对.
/*
仿照fenix124的算法，用空间换时间。
算法介绍；
先制作一个表（用结构数组表示），里面存储了由待转换正整数n所能转换到的MAXSIZE个正整数（MAXSIZE取10000）。
结构包含三个成员变量：int step;  //由n转换到该元素所需的最小步数
      int prior; //该元素的前驱
      char tag; //由该元素的前驱转换到该元素采取的方法，f（）或g（）。
然后从元素vf[m]开始，遍历其前驱，提取字符f或g，存储到fs[]中。
最后返回 vf[m].step.
*/
[/quote]
我觉得可以吧,虽然我没做出来但我也是想用递归广度搜索,后来发现数据溢出了
等大侠来点评一下

20 楼

boxertony [专家分：23030] 发布于 2006-06-18 22:44:00

[quote]
既然我的程序有错,那么下一次出题的人换一个吧
[/quote]
1。你的错误是在很特殊情况下才出的，只要修改一下20000还是可以得出正确结果的
2。这个是我在宣布冠军以后，为了对比"太没劲了"后来的程序才发现的

所以，冠军还是属于你，还是有你主持下次比赛吧。

我来回复

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

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

回复列表（共26个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共26个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共26个回复）