第36次编程比赛第1题结果 — 编程爱好者社区

主题：第36次编程比赛第1题结果

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

// 所有测试时间的单位为毫秒。测试环境:winxp+vc6, release版本，PIII 1.13G
// 第1轮测试：
// 数据：n从2循环到100
ITER@第1楼：
    正确。总耗时: 280
    说明：n＝1时错误，其他情况最后多了个.号

joekings@第2楼：
    正确。总耗时: 3084
    说明：最后多了个.号

ccpp@第3楼：
    正确。总耗时: 140
    说明：使用递归实现，程序非常简洁，速度也名列前茅。

gz80@第5楼：
    出现错误，错误处 i=10
    正确：0/1,1/10,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/10,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/10,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/10,1/1
    错误：0/1,1/:,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/:,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/:,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/:,1/1
    说明：没有考虑n大于等于10的情况
    总耗时: 0

asddg67@第6楼：
    出现错误，错误处 i=6
    正确：0/1,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,1/1
    错误：0/1,1/6,1/5,1/4,1/3,2/5,1/2,3/5,4/6,2/3,3/4,4/5,5/6,1/1
    说明：没有考虑4/6这种可约分的情况。
    总耗时: 0

neverPE @ 9:
    正确。总耗时: 130
    说明：时间复杂度应为O(n^2)，但速度仍然显得较快，有点奇怪。

czarwind @ 10:
    出现错误，错误处 i=2
    正确：0/1,1/2,1/1
    错误：无结果

    总耗时: 0

瞬间移动 @ 11:
    出现错误，错误处 i=10
    正确：0/1,1/10,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/10,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/10,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/10,1/1
    错误：0/1,1/:,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/:,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/:,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/:,1/1
    说明：没有考虑n大于等于10的情况。
    总耗时: 0

火海时代 @ 12:
    出现错误，错误处 i=9
    正确：0/1,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,1/1
    错误：0/1,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,6/9,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,1/1
    说明：没有考虑6/9这种可约分的情况。
    总耗时: 0

liangbch @ 13-15:
    正确。总耗时: 80

zheni @ 16:
    出现错误，错误处 i=10
    正确：0/1,1/10,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/10,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/10,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/10,1/1
    错误：0/1,1/:,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,3/:,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,7/:,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,9/:,1/1
    说明：没有考虑n大于等于10的情况。
    总耗时: 0

hyerty @ 20:
    正确。总耗时: 583

xyhx @ 25:
    正确。总耗时: 210

szh @ 26:
    正确。总耗时: 2293

neverPE @ 27:
    正确。总耗时: 80

euc @ 28:
    正确。总耗时: 2294

liangbch @ 29-32:
    正确。总耗时: 180
    虽然有所改进，但由于程序更复杂，所以总的速度反而不如13楼的程序了。

// 第2轮测试：
// 数据：n从2循环到200
liangbch @ 13-15:（200）
    正确。总耗时: 971

neverPE @ 27:（200）
    正确。总耗时: 930

ccpp@第3楼：（200）
    正确。总耗时: 1192

neverPE @ 9:（200）
    正确。总耗时: 1242

xyhx @ 25:（200）
    正确。总耗时: 1591

liangbch @ 29-32:（200）
    正确。总耗时: 2234

ITER@第1楼：(200)
    正确。总耗时: 3456

hyerty @ 20:(200)
    出现错误，错误处 i=131
    错误：无结果

    总耗时: 940

joekings@第2楼：(200)
    出现错误，错误处 i=102
    错误：最后出现 100/101,}}}?101/102,101/102,1/1

    总耗时: 3344

euc @ 28:(200)
    正确。总耗时: 80403

// 第3轮测试：
// 数据：n从2循环到300
neverPE @ 27:（300）
    正确。总耗时: 3133

liangbch @ 13-15:（300）
    正确。总耗时: 4057

ccpp@第3楼：(300)
    正确。总耗时: 4418

neverPE @ 9：（300）
    正确。总耗时: 4576

xyhx @ 25:（300）
    正确。总耗时: 5587

liangbch @ 29-32:
    正确。总耗时: 7779

ITER@第1楼：（300）
    正确。总耗时: 46498

总的说明：
由于随着n的增加，时间复杂度递增非常快，所以本测试最多进行到n为300。
4楼、7楼、8楼和21楼由于与我给出的接口不一致，改起来太费事就没有测试，抱歉。

从上面的测试结果看，27楼neverPE的速度是最快的。因此，我宣布本次大赛的冠军为：[color=FF0000]neverPE[/color]。
另外，ccpp的程序速度与neverPE的也很接近，而且程序非常简洁，所以宣布ccpp获得优胜奖。

本帖地址： http://bbs.pfan.cn/post/185736.html

回复列表（共24个回复）

沙发

hyerty [专家分：1110] 发布于 2006-08-07 08:07:00

倒，没想到你会这样测试，我以为是单个数的测试，我那程序我自己测试时可以在TC2.0下输入3800通过。在WinXP+Dev-C++下输入10000测试通过（再大的没测试了）。
还有，我那个在Farey串长度大于32627时就不输出结果了，不是没结果啊。不过总的来说我的程序不太规范，而且效率也跟不上，对结果没有意见。下次我会继续努力的，呵呵。
我想问一下，你算程序执行时间怎么精确到毫秒的？

板凳

neverPE [专家分：1620] 发布于 2006-08-07 09:22:00

早上起来看到结果，没想到第一次参加就可以获得不错的成绩，有点意外：）多谢boxertony抬举。
确实没想到测试数据只到300，我自己都是用1000以上的数据测的。记得在n=4000时我比ccpp多花了一倍的时间。实际上他生成序列的速度比我快很多，但是转换成字符串保存到farey[]中比较慢。所以在规模比较小的时候体现不出优势，但n很大的时候优势就很明显了。如果能先将n以内的数都转成字符串，n>2000时他的程序甚至可以只花现在1/10的时间（我的机器Duron1.1G)。

3 楼

boxertony [专家分：23030] 发布于 2006-08-07 09:28:00

呵呵，单个数测试是没有问题，问题是我测试哪个数合适呢？所以干脆就通过循环测试某个范围内的所有数据了。

关于hyerty测试没有结果的问题，抱歉了，没有注意到你的程序的范围限制。

至于测试时间精确到毫秒的问题，使用clock函数即可。

4 楼

瞬间移动 [专家分：320] 发布于 2006-08-07 20:20:00

呵呵不是吧楼主我有特地处理过10以上的数字的我自己通过了10的测试啊
你那里通不过吗？

5 楼

ITER [专家分：680] 发布于 2006-08-07 20:47:00

[em2]

6 楼

ITER [专家分：680] 发布于 2006-08-07 20:50:00

呵呵　　忘了考虑１的情况了　应该特殊处理下的　
[em8]　　　　boxertony兄真是好认真好有效率　　赞赞
同时又得研究下优秀作品　学习学习　　[em11]

7 楼

ITER [专家分：680] 发布于 2006-08-07 21:11:00

问个问题哦
pf += sprintf(farey,"%d/%d,",0,1);
这是ccpp老兄用的一个函数  请问sprintf具体什么功能呀?
还有字符pf可以直接"+=" ?  意思是pf=pf+sprintf返回的东西?
真的看不动   还望ccpp等一辈高人指教  [em12]

8 楼

ccpp [专家分：9360] 发布于 2006-08-07 22:49:00

函数名: sprintf
功  能: 送格式化字符串到字符型数组（缓存区）
用  法: int sprintf(char *string, char *farmat [,argument,...]);
        函数返回格式化字符串个数。
#include <stdio.h>
int main(void)
{
   char buffer[80];
   float f = 3.141592;
   sprintf(buffer, "Pi is %f\n", f);
   puts(buffer);
   return 0;
}

相对于sprintf，
printf 是送格式化字符串到标准输出缓冲区（然后在屏幕输出）

9 楼

liangbch [专家分：1270] 发布于 2006-08-08 12:04:00

作为参与者，我为此投入为巨大的热情和精力，为了向同行学习，也想知道自己也别人的差距，在昨晚对所有程序进行分析和测试。下面是我的分析结果，说的不对处，请大家指正。
   标有“性能：待测”一般情况下，在n值较大时，速度还可以接受，具体量化指标，不久我将会给出。

aqua123:
　　1.接口不符合要求
    2.从数据结构Node("char cdata[7];")可以看出，n的值不能大于999
　　3.从代码中看以看出n的范围不能大于99("else if(i>=10&&i<100)")
    4.性能：待测

asddg67：结果中包4/6，程序错误
bloodybg: 结果中包含4/6,程序错误

ccpp：
　　采用法雷数列的性质，直接生成每个元素，时间复杂度，速度快，无需快序。
　　采用递归设计，代码极为简略，递归程序的典范之作
　　除了递归调用栈外，占用空间为零
　
czarwind:
    1.生成的字符串格式不正确，改正一些错误后，仍只能计算到9,改正方法如下：

  // 保存序列
     farey[0] = '0';     // 加上0/1
     farey[1] = '/';
     farey[2] = '1';    farey[3] = ',';

     for ( i = 1; i <= index; i++)
     {
         int search = dptr[i - 1].index;
         farey[4 * i] = fareyseq[2 * search]+'0';
         farey[4 * i + 1] = '/';
         farey[4 * i + 2] = fareyseq[2 * search + 1]+'0';
         farey[4 * i + 3] = ',';
     }
     index++;
     farey[4 * index] = '1';   // 加上1/1
     farey[4 * index + 1] = '/';  farey[4 * index + 2] = '1';
     farey[4 * index + 3] = 0;
ecu:
算法：穷举所有分数，剔除可约分数(算法没看明白）
　　　数据存储采用动态数组，一次分配n^2/2个元素
　　　性能较差

gz80: 由于数转化为字符串的算法局限性，只能算到9

火海时代：由于数转化为字符串的算法局限性，只能算到9

hyerty:
　　　算法.利用法雷序列的性质，直接得到法雷序列。
　　　去除程序中的一些限制后，n的上限仅限于硬盘空间，
      性能：待测

iter: 算法：穷举所有分数，剔除可约分数，数据采用链表存储
　　　算法优缺点:
      1.算法效率不高。
      2.占用空间较大

joekings: 1。
　　　算法：穷举所有分数，剔除可约分数，数据存储在固定大小数组中，适应性不强
　　　算法优缺点：.算法效率不高.　　　
      bug:1.当n>=102,输出的字符串有乱码
　　　    2.当n>180以上时，对数组Moden的访问将越界
liyanguestc:
    算法：穷举所有分数，剔除可约分数，数据采用动态分配，一次性分配n^2个结点
    接口不符合要求，输出的字符串格式不符合要求.
　  算法优缺点：占用空间稍大
　　性能：待测

magicalking: 结果完全不符合要求。

newpe:1
    算法：穷举所有分数，剔除可约分数(采用经典的辗转相除法求公约数），
数据采用动态分配，先预估所需空间，一次性分配n^2/3个结点,
　　　　每个结点占用空间20byte
　  算法优缺点：num2str写得不错，比我的更简略，gcd效率较高。
　　性能：待测

newpe:2
  算法：穷举所有分数，剔除可约分数(采用经典的辗转相除法求公约数），
  数据采用动态分配，一次性分配少量空间，创造性的采用堆存储数据
  算法优缺点：num2str写得不错，比我的更简略，gcd效率较高，占用空间很少
　性能：待测

瞬间移动：
　　由于数转化为字符串的算法局限性，只能算到9，大于9则结果不正确。
　　数据采用静态分配，当n>17，数组越界
szh:
   数组定义错误( int Farey[n]),无法通过编译，且无法通过简单的修改以通过编译。

xyhx:   算法：根据法雷序列的性质，直接得到每个分数，采用插入排序
　　　数据采用链表存储，每个结点占用空间：12byte
　　　性能：待测

zheni:   字符串没有结束符'\0',当n>9时，结果不正确

10 楼

szh [专家分：380] 发布于 2006-08-08 13:24:00

to liangbch

C99中支持可变长数组，你的编译器也许不支持，请换用DEV-C++来编译.

我来回复

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

主题：第36次编程比赛第1题结果

回复列表（共24个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第36次编程比赛第1题结果

回复列表 （共24个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共24个回复）