第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个回复）

11 楼

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

看来使用strcat的确耗时，修改了一下代码，测试下来速度明显提升
#include <cstdio>
#include <algorithm>
using namespace std;
//采用辗转相除来判断是否可约
    int gcv( int a, int b )
    {
         int big = max( a, b );
        int small = min( a, b );
        int temp;
        while( small > 1 )
        {
               temp = big % small;
              if( temp == 0 )    break;
              big = small;
              small = temp;
        }
        return small > 1 ? 0 : 1;
    }

    //寻找当前最小的不可约分数
    int search( int start, int end, int Farey[] )
    {
         int n = start;
         int s = start, m = Farey[start];
         for( int i = start + 1; i <= end; i++ )
         {
              if( (i*m - s*Farey[i])<0 )
             {
                      s = i;
                      m = Farey[i];
                      n = i;
             }
        }
        return n;
    }

    void FareySequence( int n, char farey[] )
    {
          int Farey[n];    //建立一个数组来表示所有分数
         int cnum, i;
         int start = 1, end = 1;

         farey += sprintf( farey, "0/1," );
          for( i = 1; i < n; i++ )    Farey[i] = n;
         while( Farey[n-1] != n-1 )
         {
              cnum = search( start, end, Farey );
              if( !gcv( cnum , Farey[cnum] ))
              {
                     do {
                               Farey[cnum] = max( Farey[cnum]-1, cnum );
                       }while( !gcv(cnum, Farey[cnum]) );

                       continue;
              }
              farey += sprintf( farey, "%d/%d,", cnum, Farey[cnum] );
              Farey[cnum] = max( Farey[cnum]-1, cnum );
              if( cnum == Farey[cnum] )    start++;
              for( i = end; i < n && Farey[i]!=n; i++ );
              end = i;
         }
         sprintf( farey, "1/1" );
    }

12 楼

ITER [专家分：680] 发布于 2006-08-08 14:28:00

[quote]函数名:
．．．．．

相对于sprintf，
printf 是送格式化字符串到标准输出缓冲区（然后在屏幕输出）[/quote]
哦　　就和那个fprintf（输到文件）类似的东东　：）
总算看明白了　　呵呵　　谢谢ccpp兄～
居然把算法直接抽离出来了　　看来数学功底也非同一般
感叹啊．．．　　　　差距．．．

同时也赞一下liangbch兄的热情　　呵呵
[em1]

13 楼

ccpp [专家分：9360] 发布于 2006-08-08 17:32:00

呵呵，
是那个sprintf很强，
算法是抄袭别人的，修改后加了sprintf

14 楼

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

sorry,我一直用vc++6.0,不知道最新的c标准，我下载个dev-c++今试试。

15 楼

neverPE [专家分：1620] 发布于 2006-08-08 19:15:00

多谢liangbch兄对所有程序的分析，受益匪浅。看这么多没什么注释的程序，辛苦了。
我真的很喜欢ccpp写的这个程序，简短，时间和空间都非常优秀。pf+=sprintf这一段稍微优化下，n比较大的时候，速度可以提升十倍以上。

PS：I'm neverPE... not newpe... :)

16 楼

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

向liangbch同志致敬。先说声辛苦了，你很用心啊，我只大致看了一下大家的程序，没你这样去仔细分析。
其实我自己在写程序时，开始在同学的机子上写，他只装了turbo c/c++ 3.0，我把内存调成紧凑模式编译器总有问题，所以只好用默认的small模式，也只是我只有64K的内存。这个问题使我很头痛，n的上限很受限制，我测试通过的最大值好象就180吧，后来才想到把已经计算出来的前面的数字保存到文件，以释放内存空间。其实我的程序仍然受内存限制的，但相对要小的多了。还有，我查了一下malloc函数，发现它的参数只能是整形，fread读的字节数也只能是整形，所以我又给程序加上字节超过32626时返回NULL的限制。我想过改用calloc函数和多次读文件来解除这个限制，但我觉得此时返回的串也没什么意义了，所以就没弄了。
来答题时我在网吧输完程序后顺便下载Dev-C++来测试了下，输入10000，测试成功，我觉得很满意了，没多想就发上去了。
看到 boxertony 的测试方式才知道我读写文件浪费时间吃大亏了。不过我觉得 boxertony 的这种方式很是公平合理，所以也没什么抱怨的。
ccpp等高手写的程序确实是出手不凡啊，很值得学习。

下一比赛什么时候开始啊，很期待啊。呵呵。

17 楼

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

各个性能较优的程序在大数据量下的测试结果.
  表中的数值为运行时间，单位（秒）"---"部分表示因时间太长没有测试或者运行出错。
　运行环境：迅驰1.7G,256M RAM,windows XP。
　1.总体性能： neverPE:2＞ ccpp＞ liangbch:2＞ liangbch:1＞ xyhz＞  neverPE:1＞ liyanguestc
  2.liangbch:1在n值较小时，稍慢于neverPE,但n较大时占优，xyhz与neverPE互在胜负，但当n值很大时比neverPE快出很多。
　
n       neverPE:2  ccpp  liangbch:2 liangbch:1 xyhz  neverPE:1  liyanguestc
128    0.00174  0.00250  0.00260  0.00258  0.00309  0.00261  0.004098
256    0.00758  0.01104  0.01169  0.01174  0.01338  0.01154  0.020350
512    0.03429  0.04755  0.05229  0.05513  0.05756  0.05211  0.083610
1024    0.14618  0.20243  0.23351  0.24253  0.22759  0.24063  0.373746
2048    0.64737  0.85534  1.04836  1.08395  1.01068  1.10630  4.501416
3072    1.51352  1.97616  2.60008  2.70145  2.38531  2.67880  76.72441
4096    2.77951  3.58681  4.58768  4.87220  20.2621  5.05234  --------
5120    4.50988  5.69242  7.55854  25.7822  32.5234  91.5530  --------
6144    6.71775  8.24302  11.3690  65.5938  -------  ------   --------
7168    9.19652  14.1351  17.2442  ------   -------  -------  --------

   szh在vc下不能编译通过，下面给出的数值是在devc++编译后的运行结果，从速度下讲，这个程序应该是第二梯队的。
n   seconds
128  0.05007
256  0.86879
512  13.7767
1024 234.566

18 楼

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

对一些选手的程序改进后的结果：
  ccpp 程序的瓶颈在sprintf,将sprintf改为我写的函数后，速后提高5倍左右，这将超过第一名的程序很多。下面的具体的数值
n=128,    t=0.00045313 s
n=256,    t=0.00200081 s
n=512,    t=0.00885476 s
n=1024,    t=0.04332199 s
n=2048,    t=0.17296975 s
n=3072,    t=0.40179241 s
n=4096,    t=0.73753452 s
n=5120,    t=1.18138227 s
n=6144,    t=1.79169196 s
n=7168,    t=2.49714475 s

　xyhz的程序仍有优化空间，将sprintf改为我自己编的函数后（又一个sprintf性能不佳的例子，在我的程序中提到了自编程序能够比sprintf快,不知大家注意没有），再并将struct fare　的成员变量memr,demo改为shor后，当n较小时，速度提高3倍多。(说明，将int改为short后，占用内存空间将减少，这样，在某些原来需使用页交换的情况，而现在不需使用页交换，从而提高了速度。
n=128,  t=0.00108924 s
n=256,  t=0.00453298 s
n=512,  t=0.01903678 s
n=1024, t=0.07680473 s
n=2048, t=0.3306250 s
n=3072, t=0.7559296 s
n=4096, t=12.7455364 s
n=5120, t=30.7433696 s

19 楼

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

算法讨论：

　1.xyzh程序的特点：
　1）.利用法雷序列的特点，直接得到每一个分数，不需判断是否是最简分数，从而提高了速度。
　2）.一般说来，链表的速度不如数组，但链表的插入速度比数组快，且在本例中，在插入时，平均查找路径很短，这使得比同类排序算法（快速排序）更快。　

  2.我的程序的特点：和许多人的程序一样，分3步：
   1）枚举每一个分数，滤掉非最简分数，将最简分数存入数组。最大公约数的算法我是知道的，但我没有用，而用用了很复杂但很有效的筛法。这是代码量大的主要原因。
滤掉非最简分数
   2）对分数进行排序。和许多人一样，用qsort来做，这们我的程序中最耗时的部分。我的第二个程序对此进行改时，将数据分为几个连续的片段，后一个片段的数据比前一个片段大。qsort只在每个片段内进行。采用分段排序的方法，速度快了很多。
   3）转化为字符串，自己写的函数，比sprintf函数快。

  3.综述：经过分析大家的程序（仅限于性能较好者），我发现，这些程序的复杂度均为O(n^2),一些程序的的复杂度是n*(n-1),而另一些程序是利用法雷序列的特点，直接得到大约n*n*0.3个分数。当n较大时，这个差别不是影响最终速度的根本因素。起决定作用的是数据量的大小，因为当n很大时，数据项的数目将非常大，这使得L2cache和物理内存的命中率大大除低，使得数据访问密集而数据地址不连续的程序段（如qsort）很慢。而速度快的程序，或者不访大量数据（ccpp)，或者数据量很少(neverPE:2),或者对数据的访问局部化(xyzh，liangbch:2）.

20 楼

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

感谢梁兄，你帮我做了我想做而没有做的事情。

我来回复

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

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

回复列表（共24个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共24个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共24个回复）