回 帖 发 新 帖 刷新版面

主题:第29次编程比赛第2题比赛结果

//第一页
arfi@7         通过测试。  [url=http://upload.programfan.com/upfile/200606060854155.rar]最大数据[/url]运行1000次, 耗时250ms
cmlzyh@5       通过测试。  最大数据运行1000次, 耗时781ms
goal00001111@9 通过测试。  算法不合适,运行最大数据超时
ITER@8         有错误。    是不是贴错了代码。"234"与"adg"就有问题。
wellerweldon@4 通过测试。  最大数据运行1000次, 耗时 265ms
天国龙@10      通过测试。  最大数据运行1000次, 耗时 750ms
//第一页优秀   arfi 和 wellerweldon

//第二页
bvor@16       有错误。 你没有按题目要求编写函数接口。
              出错数据如下,编译后无法正常运行。
              char* num = "23456789";
              const char* words[] ={
              "adgjmptwaaaaaaaaaaaaa",//无法跳过这个长单词,
              "cfilosvx",             //来处理第二个单词
              NULL};
fenix124@14   你的解法真是清晰明了啊!但题目已注明,只提供小写字母的单词。把
其中的validwords[i][j]-'A'修改为 validwords[i][j]-'a'就好了.修改后最大数据运行1000次,耗时235ms
subchap@11    通过测试。  最大数据运行1000次, 耗时 312ms
太没劲了@18   通过测试。  此题被你看透了!最大数据运行1000次, 耗时188ms
//第二页优秀  subchap 和 太没劲了

//第三页
HeroSong@24   有错误。 你没有有效排除字母Q。"23456789"和"adgjmqtw"应该是不匹配的。
HeroSong@25   有错误同上。
hustliux@26   有错误。你没有有效排除字母Q和Z. "23456789" 和 "adgjmqtw", "adgjmptz", "adgjmqtz"应该都是不匹配的。
johnywoo@29   通过测试。  最大数据运行1000次, 耗时219ms
yunzhou008@22 通过测试。  最大数据运行1000次, 耗时203ms
火海时代@30   有错误。 "23456789"和"adgjmptwa"应该是不匹配的,你的程序没有检测到单词末尾多了一个a。
//第三页优秀  johnywoo 和 yunzhou008

//第四页
ht1441@34       通过测试。使用数组来保存每个单词的长度,在时间和空间上产生额外的开销。当单词数目很多是势必会影响运行速度。请参看本题示例解法。
scyangbo@31     通过测试。  最大数据运行1000次, 耗时828ms

singlemanlqs@33 有错误。 "7"和"s"应该是匹配的。
w01fdawn35      有错误。 你没有有效排除字母Q。"23456789"和"adgjmqtw"应该是不匹配的。
//第四页优秀    无

[color=008000]借用了fenix124@14的代码[/color]^_^,作为推荐算法样板!如下:

int p[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,-1,7,7,8,8,8,9,9,9,-1};
int NumberOfValid(const char* number,const char* validwords[])
{
    int i,j,temp;
    temp = 0;
    for(i = 0;validwords[i];i++)
    {
        for(j = 0; number[j]&&validwords[i][j];j++)
            if(p[validwords[i][j]-'a'] != number[j]-'0')  break;
        if(number[j]== 0 && validwords[i][j] == 0)   temp++;
    }
    return temp;
}

废话就不多说了,[color=0000FF]我宣布此题比赛的冠军是 太没劲了[/color]。
请 太没劲了 兄负责出下周的第30次比赛第2题。

p.s.对于通过测试的参赛者,回复此贴加30分专家分

回复列表 (共36个回复)

31 楼

溜进来领点分儿

顺便“鄙视”一下 太没劲了 的代码,哈哈,开个玩笑

32 楼


我希望能够把测试代码给出来。

太没劲了的代码对于关键的比较操作没有作什么的优化,而且算法对于数字长度和字典词长度接近的数据耗时会很长。

用大概2K个长单词 和2K个数字(长度和单词相近)进行测试的话,稍微进行过优化的代码能比太没劲的少一半的时间。

我不是来吵吵 或者 踢场。我只是希望测试代码能给出来,或者也征集一次测试代码,因为测试也是一门手艺。

33 楼

[quote]而且算法对于数字长度和字典词长度接近的数据耗时会很长[/quote]

这个更准确的说法应该是“数字和字典词前面多半匹配或者全匹配时耗时很长,前者可以简称'尾部失配'”。

[quote]稍微进行过优化的代码能比太没劲的少一半的时间。[/quote]

说说你对于上面那种导致速度偏慢情况的具体优化算法(代码或描述),俺有兴趣。

34 楼

[quote][quote]而且算法对于数字长度和字典词长度接近的数据耗时会很长[/quote]

这个更准确的说法应该是“数字和字典词前面多半匹配或者全匹配时耗时很长,前者可以简称'尾部失配'”。

[quote]稍微进行过优化的代码能比太没劲的少一半的时间。[/quote]

说说你对于上面那种导致速度偏慢情况的具体优化算法(代码或描述),俺有兴趣。
[/quote]

往前瞅了瞅,好像那个模版84太没劲的 ^_^ 冒犯了。。 我优化的方法只是先做一个初始化操作,对字典作了个按词长进行了整理. 然后逐字符比较,改成逐词比较。(把词转化为2进制(编码方式类同),利用memcmp比较节省时间,因为整理词长) 

35 楼

[quote]往前瞅了瞅,好像那个模版84太没劲的 ^_^ 冒犯了。。 我优化的方法只是先做一个初始化操作,对字典作了个按词长进行了整理. 然后逐字符比较,改成逐词比较[/quote]

我的法子和那个模版挺类似的,只是在细节、写法上有点点不同。你这个法子可以自己先做出来试试看,我感觉不见得和你估计的一样,你可以找 @ccpp 要他的全部测试数据试。

36 楼

[quote][quote]往前瞅了瞅,好像那个模版84太没劲的 ^_^ 冒犯了。。 我优化的方法只是先做一个初始化操作,对字典作了个按词长进行了整理. 然后逐字符比较,改成逐词比较[/quote]

我的法子和那个模版挺类似的,只是在细节、写法上有点点不同。你这个法子可以自己先做出来试试看,我感觉不见得和你估计的一样,你可以找 @ccpp 要他的全部测试数据试。
[/quote]

这个我测过了,不过测试数据是专门针对这种比较方法的,我在出题的当天下午,偷偷的写了一下,不过没有看清楚,按键上少了两字母。。我的编码不对,写完后 就没有管了。 我用 cygwin下的time 命令测的。 因为是偷偷写的,所以代码健壮性很糟糕。。哈哈。。况且编码也错了 就没有贴出来。。
这类数据 重复计算3K次 就差不多了
char* num2037 = "22037203722";
 "dinndpfgsdrb",

我来回复

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