回 帖 发 新 帖 刷新版面

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

11 楼

to 5楼: 7表示你有7个数据错了,具体是什么你自己测一下就知道。测试数据帖出来了 前10组全true,后10组全false。 

to 7楼: 测试代码就是读入数据,调用函数,测试方法我都写了。我测你的程序时候蓝屏了,再启动cpp文件变成全0x00。 结果31楼和32楼全是手工测的。

12 楼

PS:题目出得不错,每次neverPE出题都很多人捧场~

13 楼

因为想不出什么好的算法,所以用了一堆if来这儿丢人了~~~~~~

neverPE出的题目和冬令营的题目几乎是一样的!

14 楼

[quote]空串应该是匹配吧,我的程序是匹配。

不是说是表达式吗,怎么只有括号啊~

我也用的模板啊,为什么速度会吃亏呢?neverPE的标程呢~[/quote]

关于空串,抱歉,写错了,是另一位的代码返回false,那句话我写错地方了。但现在也记不起来是谁的,,,

关于模版,很奇怪,你比其他用模版的快一个数量级,,,,

我的程序,很普通,没什么特别,速度比22楼merry05和32楼ITER慢,就不拿出来丢人了。

15 楼

switch听说是被优化过的,像euc那样舍得一点内存做个表对应我觉得更快,我自己测试的时候是拿像这样的数据测的:

(dkfjsldjgkd<<<<<434kkdj

16 楼

回楼上, 我本来是准备用这样的数据, 但后来为了降低难度, 就用纯括号了。

17 楼

555555,
栈是我自己定义的,没有优化,另外交上程序后发现  忘了malloc后加上free,对内存没有很好的保护(坏习惯).

另外,我的程序 不稳定,有些遗憾!

18 楼

neverPE,为什么用模板会比较吃亏呢?早知道不学STL了,:-(

19 楼

本来想搭个自动机来做的,不过手工把正则表达式转成最小DFA实在是有些麻烦……

20 楼

STL绝对是好东西, 学了大有好处。可以大大减小工作量,增加可读性。 如果不是对性能要求苛刻,并做大量优化,自己写的不一定比模版快多少。

但在有些时候(比如这里),STL可能会牺牲一部分性能。当你了解STL内部算法实现,就会明白。

我来回复

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