回 帖 发 新 帖 刷新版面

主题:第49次编程比赛结果

这次的题目,难度没有掌握好,解法太单调了,大家的算法都差不多。是我的责任。 不过幸运的是有很多人参加,谢谢各位捧场。
    本来是一个贴近编译原理的题。考虑到比赛刚恢复就碰上春节延迟一周,为了更多人参加,题目被我简化了好几次,然后加上“<>”后就成了现在这个样子。
    关于同级括号嵌套没有说明,我的本意(())是合法的,可是没有说清楚, 导致很多人误会了。 于是修改了测试数据,不会出现同级括号的嵌套,两种理解都正确。测试结果:

第一轮用20组数据测试(数据附后),28位参加的朋友中,有12位通过。很多朋友没考虑单边括号,很可惜。3楼的redraiment返回值全反,修改后通过。
10    SonicLing    6组数据出错
11    我不太会    7组数据出错
13    dongdong123    运行期错误
14    55560380    9组数据出错
15    bloodybg    7组数据出错
16    iAkiak        2组出错(第12、15组,单边括号)
18    hj36277        栈溢出
23    hazf2008    7
24    独行者        6
25    szh        单边括号
26    笑十三狼    7
27    songfei        6
28    freeeerf    单边括号?
29    ldb2741        9
30    雪光风剑    运行期错误
31    ghbxx2004    6

第二轮:将第一轮的前10组数据连接再重复64次,重复运行1000次,得到的运算时间。
5    euc        297
9    codedog        297
20    crossbow    297
    以上3位似乎用模版比较吃亏。运行时间相差5%内,考虑到clock()和运行时可能有后台程序的误差,可以认为速度是相同的。

4     skybtone    65
3    redraiment    47(那个全局变量实在没必要。应该放到函数里并且初始化,否则重复运行会错。)
*7    bpttc        45
*12    eastcowboy    47
17    rj1985        47
19    xchbcahz    47
21    rickone        45
22    merry05        31
32    ITER        31
    以上9位速度接近,除了4楼之外速度差距都在30%以内,很难取舍。考虑到7楼的bpttc有足够多的说明和注释,并且效率也不错(肯写注释的人太少了,要鼓励)。第49次编程比赛的冠军是:[color=FF0000]bpttc[/color]。大家恭喜他。请 bpttc准备第50次编程比赛。  

    运行环境是AthlonXP2.2G(133*16.5)+1G+VC6 Release。(Debug模式下,以上大部分程序运行时间大约是10倍)。如果对测试和结果有任何异议,请跟帖说明。我会尽快回复。


附:第一轮的测试数据
()
{[(<>)]}
[<>]
[()(<>)]
{}[]()<>
{}{}{[]}<>[()<>(<>)]
<><><><><><><>()()()(){<><><><><><><>()()()()}{[()<>(<>)]}
(<>){}[]()<>{()[()<>]()}
(){(<>)[]()<>}(<>){}[]()<>
{<><><><><><><>()()()()}{[()<>(<>)]}(<>){}[]()<>{()[()<>]()}(){(<>)[]()<>}(<>){}[]()<>

}
{
{([])}
<()>
{}{}{}[](
}[](<>)
{}{}{[]}<>[(()<>){}(<>)]
(){(<>){}[]()<>}[(<>){}[]()<>]
(){(<>){}[]()<>}{(<>)[]()<>}()[(<>)()[](){}}{(<>)[]()<>]
<><><><><><><>()()()()(<><><><><><><>()[]()){[()<>(<>)]}

回复列表 (共29个回复)

21 楼


首先恭喜bpttc![em2]
然后再勉励自己一下![em12]

22 楼

唉,失算了。
末了return s.empty();就对了...

还要继续努力:)

23 楼

我的栈容量是20,以为不会出很长的字符串!

24 楼

恭喜bpttc
<><><><><><><>()()()(){<><><><><><><>()()()()}{[()<>(<>)]}
原来这样的括号也可以啊
我以为只能嵌套括号呢,哈哈

25 楼

我不太懂栈溢出  是什么地方溢出了?请说一下 谢谢了!!

26 楼

其实我觉得这题为了栈来动态开辟空间好像有点不必要。
一个malloc和free在大量的循环运行中要占用多少时间!

27 楼

我无悔对stl的选择!!!

28 楼

恭喜bpttc,又学到东西了

29 楼


呼呼    neverPE兄辛苦辛苦   呼呼

恭喜第一名那哥们哈

说实话真的好高兴编程比赛又在进行了

前阵子好久都没写代码   手都僵快了...

我来回复

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