第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个回复）

21 楼

int0x080 [专家分：90] 发布于 2006-06-19 00:21:00

本来用vector，到28<=step时，就会分不到内存了，
用了list,却慢死。

明天好好看看你们的算法 -.-

22 楼

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

// 第2楼“太没劲了”的程序采用的是从后往前倒退方式进行宽度优先搜索。

// 我利用队列，仿照“太没劲了”的函数，采用从前往后方式写了一个函数
// 在同样的阈值下，速度比“太没劲了”函数略快一点。

// 同时也发现了“太没劲了”的函数对于1000组数据测试中有三组数据的结果不对。
// 1. n=590 m= 70. 结果: 21(gfggfffgggfgfgfgggggg),
//                 应为: 16(gggggggggfggffff).
// 2. n= 32 m=773. 结果: 47(ggggfgfgffggggfgfgfffggggfgffggffgffgfgfffggggg),
//                 应为: 29(ggggggffggfgffffgfggggggfffff).
// 3. n=145 m=929. 结果: 36(ggggfggfgfgffgggfgfgffffgfggffgfgggg),
//                 应为: 18(ggggggggffgfgfffff).
// 造成的原因还是阈值的问题，阈值到262144比较合适（但速度降低不少），
// 太没劲了只设置到32768

#define MAXBUFFSIZE1  262144

#define MAXBUFFSIZE2  32768

int transform(int n, int m, char *fs)
{
    static int parent[MAXBUFFSIZE1];
    static int q[MAXBUFFSIZE2];
    int   curv;
    int   temp;
    int   f, r;

    memset((void*)parent, 0, sizeof(int)*MAXBUFFSIZE1);
    f = r = 0;
    q[r++] = n;

    parent[n] = INT_MAX;
    while(f != r)
    {
        temp = q[f++];
        f = (f == MAXBUFFSIZE2)?0:f;

        curv = temp >> 1;
        if(curv == m)
            break;

        if(curv > 0 && !parent[curv])
        {
            parent[curv] = temp;
            q[r++] = curv;
            r = (r == MAXBUFFSIZE2)?0:r;
        }

        curv = temp * 3;
        if(curv == m)
            break;
        if( curv < MAXBUFFSIZE1 && !parent[curv] )
        {
            parent[curv] = temp;
            q[r++] = curv;
            r = (r == MAXBUFFSIZE2)?0:r;
        }
    }

    int  i = 0;
    fs[i++] = 'f' + (temp>m);
    while(temp != n)
    {
        m = temp;
        temp = parent[temp];
        fs[i++] = 'f' + (temp>m);
    }
    fs[i] = 0;
    return(i);
}

23 楼

cooket [专家分：0] 发布于 2006-06-20 09:43:00

我在比赛那天看了题目，想到了一种数学的方法，但由于我本人没电脑（我使用别人机子看得），所以就没将程序写出来，我的那个算法我简单的测了一下，结果是正确的，但不知道时间上如何，我将算法大意写下，希望有电脑的高手将它完成，看看这个算法如何，谢谢了
算法大意如下：先比较n与m的大小，如果n〉m就执行分支一，n〈m就执行分支二；
分支一：将n/2再于m比较，如果大于m就继续/2，如果小于就*3，如此循环，直到等于m，如果循环步数大于65就跳出（因为刚才看到有人测试说最大好像是62步吧？:-P）
分支二：将n*3再于m比较，如果小于就继续*3，如果大于就/2，如此循环，直到等于m,如果循环步数大于65就跳出

24 楼

太没劲了 [专家分：2050] 发布于 2006-06-20 09:57:00

谢谢 @boxertony 第 22 楼所做的工作，让俺知道俺那是错的，看来这个“广度遍历”方法的合理数值范围是个大问题。楼主真是好耐心。

第 23 楼 @cooket 明显有问题，你只需要拿楼主提供的数据结果验证一下就明白了，如下数据：

[quote]
1. n=590 m= 70. 结果: 21(gfggfffgggfgfgfgggggg),
应为: 16(gggggggggfggffff).
[/quote]

按你那流程第一个会 /2，就应该是 g，而上面最后是 4 个 f，即正确的是开始 *3。你这个法子的问题是局部最优不一定是全局最优（贪婪法不一定能得到最优解）。

25 楼

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

[quote]看来这个“广度遍历”方法的合理数值范围是个大问题。[/quote]
是啊，就是设置到262144，我也不敢保证所有的情况都是正确的。我最高设置到1048576试了一下，我测试的这1000组数据暂时没有发现其他问题。

26 楼

cooket [专家分：0] 发布于 2006-06-20 22:07:00

谢谢24楼的

我来回复

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

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

回复列表（共26个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共26个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共26个回复）