回 帖 发 新 帖 刷新版面

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

21 楼

好多高手啊~~~~~~

请问楼主怎么计算程序的执行时间精确到ms?

一直不知道怎么做到的~

22 楼

确实算法太差了,我这里新写了一个,如果不麻烦的话帮忙测测,谢谢!
int NumberOfValid(const char* number, const char* validwords[] )
{
      char lib[26] = {'2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','7',0,'7','7','8','8','8','9','9','9',0};
      int sum = 0;
      int i = 0;
      while (validwords[i])//遍历单词库
      {
            int j = 0, k = 0;
            while (validwords[i][j] && number[k] && lib[validwords[i][j]-'a']==number[k])//判断字符串是否匹配
            {
                  j++;
                  k++;
            }
            if (!(validwords[i][j] || number[k]))//若字符串是否匹配,记数加1
                  sum++;
            i++;
      }
      return sum;
}

23 楼

确实高手很多啊,程序比我写的简洁多了。

24 楼

确实高手很多啊,程序比我写的简洁多了。

25 楼

[quote]好
我用你的发过来的编译了还是没有错!!!怀凝是你的编译器问题!!!
你把你那里出错的信息发过来!!![/quote]
我这里测试环境 winxp(sp2),AMD Athlon(64bit)2800+,cpu硬件支持sp2补丁提供的DEP技术(数据执行保护功能),程序如果有有内存越界将无法正常运行。
问题找到了,你的代码有内存的越界行为!
for(i=0;i<table_row;i++)//对单词表排序
    {
        for(j=0;j<table_row;j++)//这应该是 j = i+1;
        {
            if(strcmp(wordtable[i],wordtable[j])<0)//从小到大排序
            {                
                strcpy(space,wordtable[i]);
                strcpy(wordtable[i],wordtable[j]);
                strcpy(wordtable[j],space);            
            }
        }
    }

由于条件是strcmp(wordtable[i],wordtable[j]) < 0,即表明前面的单词(字典序)小于后面的时后,就进行交换,把字典序大的单词放在前面,这其实从大到小排序。
在看看我提供的数据。
 const char* words[] ={
  "adgjmptwaaaaaaaaaaaaa",//无法跳过这个长单词,
 "cfilosvx",             //来处理第二个单词
   NULL
  };
由于"cfilosvx"字典序大于 "adgjmptwaaaaaaaaaaaaa",
所以发生了字符串交换,但问题也因此而产生,很明显交换后,
word[1]指向的内存空间是不够容纳长单词 "adgjmptwaaaaaaaaaaaaa"的
而用word[0]指向的内存空间来保存"cfilosvx"却很充裕!

此处的数组(内存)越界行为,编译器并没有作出检测,这也是c\c++编译器的特性。
所以你的程序运行起来好像没有问题。[color=008000]如果把两个单词的次序调换一下,在我的机器上也能正常运行,因为没有发生交换。[/color]
在xp(sp2)下,我的CPU硬件支持DEP,可以检测到到内存越界行为!所以你的程序在我的机器上无法正常运行。

26 楼

[quote]确实算法太差了,我这里新写了一个,如果不麻烦的话帮忙测测,谢谢!
[/quote]
优秀!
最大数据运行1000次, 耗时250ms.

27 楼

[quote]好多高手啊~~~~~~

请问楼主怎么计算程序的执行时间精确到ms?

一直不知道怎么做到的~[/quote]

调用C++的标准库函数,clock() 可以返回毫秒。
网上有很多相关的文章。

28 楼

俺不知道怎么出题,就找个简单点的题目,周末发上来。

29 楼

太没劲了,是高手啊!
你的简单题,我看起来也不会简单的,呵呵。
期待....

30 楼

[quote]太没劲了,是高手啊!
你的简单题,我看起来也不会简单的[/quote]

别这么说,俺的水平真的蛮差。俺所说的简单题也就跟 @ccpp 出的这个差不多,很简单的,只是供感兴趣的活动活动手脚而已。

我来回复

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