首页
社区
课程
招聘
[结束][第二阶段◇第一题]看雪论坛.腾讯公司2008软件安全技术竞赛
发表于: 2008-10-15 12:10 15725

[结束][第二阶段◇第一题]看雪论坛.腾讯公司2008软件安全技术竞赛

2008-10-15 12:10
15725
收藏
免费 0
支持
分享
最新回复 (165)
雪    币: 2067
活跃值: (82)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
101
应该加5分
否则时间一到, 每个人都有话说了, 评委的任何话都将是错的.
2008-10-16 19:43
0
雪    币: 398
活跃值: (343)
能力值: (RANK:650 )
在线值:
发帖
回帖
粉丝
102
完全不行,看来要放弃了
2008-10-16 20:36
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
103
LS明明已经提交了
2008-10-16 20:37
0
雪    币: 221
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
104
究竟以哪一个为准,文档还是帖子???
2008-10-16 21:00
0
雪    币: 503
活跃值: (80)
能力值: (RANK:280 )
在线值:
发帖
回帖
粉丝
105
我这个粗心的毛病看来是很难改了,哎
不知道完整组合能有多少,1.0看来是遥不可及啊
2008-10-16 21:52
0
雪    币: 111
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
106
强大!。。。。。。。。。。
2008-10-16 22:16
0
雪    币: 497
活跃值: (58)
能力值: ( LV3,RANK:25 )
在线值:
发帖
回帖
粉丝
107
败给 从指针转回二维数组了
2008-10-17 01:40
0
雪    币: 97697
活跃值: (200759)
能力值: (RANK:10 )
在线值:
发帖
回帖
粉丝
108
Which means you respect?
2008-10-17 01:40
0
雪    币: 101
活跃值: (12)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
109
竟然google到了源码
2008-10-17 05:48
0
雪    币: 2067
活跃值: (82)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
110
膜拜GG神.
2008-10-17 08:07
0
雪    币: 231
活跃值: (45)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
qdk
111
太不和谐了,差点得到一个完美的性质
上传的附件:
  • 1.jpg (61.71kb,132次下载)
2008-10-17 10:00
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
112
膜 拜楼上啊
2008-10-17 10:17
0
雪    币: 111
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
113
了解,原来真是所谓的早起的鸟儿有虫吃
2008-10-17 10:38
0
雪    币: 277
活跃值: (106)
能力值: ( LV9,RANK:230 )
在线值:
发帖
回帖
粉丝
114
又提交了一个人。。。哎 强烈建议这种花时间的编程题放周末,都没时间敲代码
2008-10-17 11:46
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
115
告诉我怎么写,我帮你敲代码
我打字还是比较快的
2008-10-17 11:49
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
116
看来楼上系数是1.0了
2008-10-17 11:51
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
117
我写的程序只能算出2种
2008-10-17 12:03
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
118
编程花的时间通常都只占一小部分
2008-10-17 12:07
0
雪    币: 8835
活跃值: (2404)
能力值: ( LV12,RANK:760 )
在线值:
发帖
回帖
粉丝
119
果然...
看了USACO也有这题~~差点喷~~
2008-10-17 12:30
0
雪    币: 328
活跃值: (10)
能力值: ( LV9,RANK:370 )
在线值:
发帖
回帖
粉丝
120
还是两个版本都算的好,万一有人只看附件中的题目呢?评委多累一点吧
2008-10-17 12:54
0
雪    币: 101
活跃值: (88)
能力值: ( LV2,RANK:140 )
在线值:
发帖
回帖
粉丝
121
乌龟大师有成为高德纳的潜力!

 
   
 
------------------

唐纳德·克努特

                              ——经典巨著《计算机程序设计的艺术》的年轻作者

    洋洋数百万言的多卷本《计算机程序设计的艺术》(The Art of Computer Programming)堪称计算机科学理论与技术的经典巨著,有评论认为其作用与地位可与数学史上欧几里得的《几何学原理》相比。本书作者唐纳德·克努特(Donald Ervin Knuth)因而荣获首届计算机先驱奖。

    克努特1938年1月10日生于美国威斯康辛州密歇根湖畔的密尔沃基(Milwaukee)。这是一个山灵水秀、人才辈出的地方,“人工智能之父”、诺贝尔奖获得者西蒙(H.A.Simon)也是在这里出生的,而且是1975年图灵奖的得主。但克努特比西蒙小整整22岁,是一个“小字辈”。克努特的父亲是一个多才多艺的人,有研究生学历,当过小学和中学教师,星期天在教堂演奏风琴,还在自家地下室办了一个小印刷厂。从克努特咿啊学语开始,他父母就给他念儿童故事,给他看卡通读物,使他从小就培养了对学习的兴趣。4岁的时候,他成为密尔沃基公共图书馆一个名为“书迷俱乐部”(Book Worm Club)的最年轻的成员(也许也是全世界最年轻的书迷)。5岁的时候,一次他独自坐电车去图书馆看书,天快黑了也不见回家,他父母打电话到图书馆去,值班员在一个书架前找到克努特时,他正坐在地上津津有味地看书,丝毫没有发觉图书馆已经闭馆,读者已经走光了。克努特上8年级时,当地的Ziegler糖果厂为了促销其称为Giant Bar的一种棒棒糖,在学校中搞了一个比赛,看谁能用Ziegler’s Giant Bar中的字母排列组合出最多的单词。克努特假装胃疼,在家里呆了两个星期,利用一部大字典,得出了4500个单词,比裁判掌握的2 000个单词多出一倍多,一举为他所在的班夺得冠军,赢得一台电视机和每人—块Giant Bar而克努特本人则赢得一付雪撬。

在数学上,克努特也很早就表现出天才。高中一年级时,他发明了一种方法,利用这种方法,对任意画出的2条相交直线,他能立即给出相应的方程。

    1956年,克努特以各科平均97.5的创记录的高分从密尔沃基路德兰高级中学毕业,进入俄亥俄州克利夫兰的开思理工学院(Case Institute of Technology)攻读物理。这一年,他在中学时就创作的一篇出色的科学幻想小说“普茨比度量衡体系”(The Potrzebie System of Weights and Measures)在美国著名的《疯狂》(Mad)杂志上发表,克努特获得了他的第一笔稿费25美元,并因而获得西屋科学天才的提名奖。在这篇小说中,克努特风趣而富于幻想地提出了替代公制的一种新的计量制度,比如以一本流行杂志的厚度为长度单位,虽然滑稽可笑,却设计得严密周到,天衣无缝,其中甚至还包括一种新的历法。文章刊出后大受欢迎,多次重印,1991年还重印过一次,其时作者克努特即将退休。

    大学一年级结束以后的暑假,克努特在学校打工,负责把统计数字画成图表。碰巧他工作室的隔壁就是计算机房,新到了一台IBM 650。当时的计算机体积都很庞大,有供输入和调试的控制台,上面排列着一排排的开关和指示灯,计算机工作时指示灯快速闪烁变化出不同的图案,这引起克努特极大的好奇与兴趣,他接连好几天彻夜不眠地呆在机房,观察它的工作,钻研使用手册,探究计算机的奥秘。一年以后,他终于改学数学,与计算机结缘。这段经历对于克努特是如此重要和关键,以致他在《计算机程序设计的艺术》第一卷的;卷首,不像别的作者那样一般写上“献给自己的父母”或“献给自己的妻子”,而是写着“献给曾经安装在开思理工学院的650型计算机,以纪念那些愉快的夜晚”。他的第一个计算机应用程序也是在650计算机上实现的:他为他所在的校篮球队(克努特人高马大,也喜爱运动)设计了一个复杂的公式,根据球员在每场比赛中的得分、助攻、抢断、篮板球、盖帽等多项统计数字对球员进行综合评估。球队教练根据克努特的程序挑选和使用球员,使开思理工学院在1960年赢得了联赛冠军,克努特的“神奇的公式和程序”也被当地报纸和广播传为美谈。1960年,克努特在开思理工学院毕业,不但被授予学士学位,还被破例同时授予硕士学位。之后他进入加州理工学院研究生院,1963年获得博士学位,留校工作至1968年,然后转入斯坦福大学任教,其间1972—1973年曾经在奥斯陆大学当客座教授。

    克努特至今进行了两大工程,一个已经完成,一个尚未完成。第一个大工程就是《计算机程序设计的艺术》系列,开始于他念博士期间,计划出七卷,第一卷《基本算法》于1968年出版,第二卷《半数字化算法》于1969年出版,第三卷《排序与搜索》于1973年出版,第四卷《组合算法》尚在写作之中。这个工程为什么前紧后松,长期停顿呢?原来,前三卷书出版以后,克努特根据自己在校对清样时的感受,决心对排版技术进行彻底改造,因此中止了第一个工程,而开始其第二个工程。这个工程花费了克努特整整9年的时间和精力,结果就是对整个西文印刷行业带来了革命性变革的TEX排版软件和METAFONT字型设计软件。这两个软件为克努特赢得了ACM的另一个奖项:1986年度的软件系统奖(Software System Award)。但是这两个软件并没有为克努特和斯坦福大学赚过一分钱:克努特把它们作为自由软件无偿提供给用户。这比理查德·斯托尔曼(Richard Stallman,1990年ACM Hopper奖获得者)在1984年发动自由软件运动早了约5-6年。克努特说:“我写这两个程序是出于对书籍的热爱,也想给这个领域以必要的推动。我已经有些名气了,我的书卖得也不错。所以我不需要为我出于热爱而做的事保留专卖权。此外,数学家通常是不为他们发现的定理获取报酬的”。1979年,克努特还创建了TEX用户集团,这个集团10年前的成员数就超过3 000。细心的读者也许会注意到,许多西文书版权页的下部注明“本书用TEX系统排版”。

    克努特的两大工程(虽然其中之一尚未最后完成)都是取得很大成功的。《计算机程序设计的艺术》一书以其内容的丰富和深刻喻为经典,有人甚至称之为“计算机的圣经”,被译为俄、日、西、葡、匈牙利、罗马尼亚等多种文字在世界各国广泛流传,其发行量创造了计算机类图书的最高记录,直至20世纪80年代中期,都一直保持着月销售量每卷达2 000册的势头,成为Addison-Wesley出版社成立以来销路最好的图书。在我国也有译本(可惜书名译为《计算机程序设计技巧》,这是不符合克努特的本意的)。此外,克努特还有许多“小创造”。计算机科学技术中两个最基本的概念:“算法”(Algorithm)和“数据结构”(Data Structure)就是克努特于29岁时提出来的。1973年他首创双向链表。在编译器设计方面,著名的LR(A)文法也是克努特在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上,经过高度概括和集中以后发明的,它表示具有从左(L)到右(R)的分析而向前看A个符号,以确定所要进行的归约和应用何种语法解释。LR(A)文法的识别效率高,在从左至右扫描输入串时,就能发现其中的语法错误,并能准确地指出出错位置,因此被广泛应用。此外,利用LR(A)文法还能正确区分像Flying planes is fun和Flying planes can crash这类句子(前一个句子“开飞机很有趣”中Flying是动名词,而后一个句子“飞行中的飞机可能出事”中Flying是现在分词当形容词)。以著名的巴克斯—诺尔范式为基础的“属性文法”(attribute grammar)也是克努特首先提出来的。属性文法在普通的上下文无关文法(context-free grammar)的基础上,对每一个终结点或非终结点加上一些属性,和对这些属性进行估值的语义规则集,从而形成一种新的、有更强表达与描述能力的文法。其中属性是由<属性名,属性值>的有序偶对组成的。属性的内容则可包括模式标识符表等。

    在算法方面,有他和他的学生共同设计的诸如Knuth-Bendix算法和Knuth—Morris-Pratt算法,前者是为了考察数学公理及其推论是否“完全”而构造标准重写规则集(rewriting rule set)的算法,曾成功地用它解决了群论中的等式的证明问题,是定理机器证明的一个范例。后者是在文本中查找字符串的简单而高效的算法。此外,克努特还设计与实现过最早的随机数发生器(random number generator)。

    20世纪70年代中期,克努特和其他一些计算机科学家曾经设想在未来10年中将产生一种比现有程序设计语言更加强大、更加优美的新型语言,并预先命名它为“乌托邦84”(Utopia 84)语言。乌托邦原是托马斯所著Utopia一书中所描述的人间理想王国,克努特悄用过来代表一种未来的理想语言,希望它有更好的数据结构和控制结构,更符合结构化程序设计的思想,等等。克努特提出Utopia 84已经过去20多年了,虽然程序设计语言在不断地发展与完善之中,但“理想语言”并未出现,可能永远也不会出现。但新一代人会不断进取。克努特在20世纪80年代所倡导的“作文式程序设计”(1iterate programming,国内有人将它译为“文化程序设计”)就是这一努力的又一体现和成果。我们从上小学起不就学做作文吗?作文首先要构思好故事,把事情的来龙去脉交代清楚,这相当于编程时先要把程序逻辑弄好。其次要围绕故事情节尽可能把有关的人物、环境等细节描写得清清楚楚,生动活泼,这相当于在程序中加入必要的注释和说明,以便阅读和理解。所谓作文式程序设计就是要像写作文那样进行编程,从完成的“源程序”中既可提炼出可执行的程序代码,又可生成程序文档,“毕其功于一役”。作文还有一个要点是分段,一篇作文要分成若干段落,以便层次分明,铺陈有序。作文式程序设计也是这样,一个复杂的程序是由若干较简单的片段构成的,较大的片段还可分为更简单的一些小片段。1983年,克努特推出了第一个这样的程序设计系统WEB。WEB包括两个子系统,一个子系统从WEB程序中自动地抽出描述算法的部分,并且加工成PASCAL编译器所能接受的形式,然后据此得到可在计算机上执行的代码。另一个子系统则把WEB程序加工为TEX系统所能接受的形式,并据此得到具有高度可读性的完整的程序文档。显然,WEB就是一个完成“PASCAL作文”的工具。继WEB之后,提姆勃莱比(H.W.Thimbleby)开发出CWEB,和WEB类似,但是一个完成“C作文”的工具。WEB和CWEB都是自由软件,可从因特网上下载。

    为了说明作文式程序设计的特色,下面给出采用这种方法编写的源程序的一个片段。

    @* Insertion sort

This is the standard insertion sort algorithm.

Assumes a sentinel at $a[0]$.

@p

for i:=2 to N do

begin V:=a[I];j:=i;

@<Insert…@>

end

@

@<Insert $V$ in the array@>=

while a[j-1]> v do

a[j]:=v

    这个片段是采用标准的插入排序算法对一个数组中的元素进行排序。片段中的@符号是系统约定,用以引入作文式程序设计中的各种特征。符号$则通知系统交叉引用某段文本作为代码而非注解。片段中有一个“宏”(macro),就是{Insert $ v $ in the array)。宏允许缩写,上述宏就可缩写为{Insert...),因此是很方便和精炼的。上述片段经过处理以后获得的程序代码如下所示。

    for i:=2 tO N do

    begin v:=a[i];j:=i;

    while a[j-1]> v do

    begin a[j]:=a[j-1];

    j:=j-1 end;

    a[j]:=v

    而处理以后获得的可供印刷的文档则如下所示。

31.Insertion sort.This is the standard inseaion son algorithm.Assumes a sentinel at O[0].

  for i=2 tO N dO

  begin

  v:=a[I];j:=i;

  <Insen v in the array.32>

  end

32.<Insen v in the array.32>

  while a[j-1]> v do

  begin a[j]:=a[j-1];j:=j-1 edn

  a[j]:=v;

Used in section 31.

    整个WEB程序还将自动产生目录和索引。大家都知道或有过亲身体验,在软件开发中,文档编写在整个过程中占着相当大的比重,是一件十分重要而又非常烦人的工作。作文式程序设计将大大减轻这方面的负担,并提高文档质量。因此,像我们从小学起就要学习写作文那样,学习并掌握用作文式程序设计进行编程实在是一件非常有意义、非常重要的事。

克努特的著作很多,除了已由Addison-Wesley出版社出版的三卷The Art of Computer Programming(由管纪文、苏运霖等译成中文,国防工业出版社出版),介绍TEX和METAFONT的五卷《计算机与排版》(Computers and Typesetting)早已流传于世外,还有以下一些主要著作:

超现实数》(Surreal Numbers,Addison-Wesley,1974)

《实用数学:计算机科学的基础》(Concrete Mathematics :A Foundation for Computer Science,Addison-Wesley,1989)

  《数学论著集》(Mathematical Writings,MAA,1989)

  《用于算法分析的数学》(Mathematics for the Analysis of Algorithms,Birkhauser,第三版,1990)

  《作文式程序设计》(Literate Programming,CSLI,1992)

  《公理与外壳》(Axioms and Hulls,Springer,1992)

  《斯坦福的GraphBase:组合计算用的平台》(The Stanford GraphBase:a Platform for Combinatorial Computing,ACM Pr.,1993)

    其中,《超现实数》一书介绍了剑桥大学的康韦(J.H.Conway)所发明的一种新的数制,是克努特听了康韦向他作的介绍后,用了一周时间写成的小说体裁的作品。有评论家指出,这是历史上第一次一个重大的数学发现以小说的形式向公众进行介绍。由此可见,克努特的艺术才华同样是非凡的,要不是计算机深深吸引了他,克努特很可能会成为出色的小说家或音乐家(他喜欢音乐,会自己制作管风琴,会创作优美动听的乐曲呢)。

    克努特获得的荣誉与奖励极多。IEEE在1980年授予他计算机先驱奖的同时,还授予他McDowell奖。ACM除了授予他图灵奖和软件系统奖外,还在1971年授予过他以COBOL的发明人、女计算机科学家赫柏(Grace Murray Hopper,也是首届计算机先驱奖获得者)命名的奖项,这个奖项是专门奖励30岁以下的优秀青年计算机科学家的。这样,克努特一人就先后获得ACM的三个奖项,在1999年以前,这是计算机科学家中仅有的一位(1999年,布鲁克斯获得图灵奖,从而也拥有ACM三个奖项,平了克努特的记录)。无独有偶,美国数学会也先后授予克努特三个奖项,即Lester R.Ford奖(1975)、J.B.Priestley奖(1981)和Steele奖(1986)。1979年,当时的美国总统卡特向他颁发了全国科学奖章。1994年,瑞典科学院授予克努特Adelskold奖。1995年他获得冯·诺伊曼奖和Harvey奖。1996年他获得日本INAMORI基金会设立的KYOTO奖,这个奖是专门奖励在高科技领域作出贡献的科学家的。面对这么多荣誉,克努特都以平常心对待,据说,纪念他获得图灵奖的碗现在只是被他用来盛放水果。

    克努特于1992年在斯坦福大学退休。但实际上他“退而不休”,继续辛勤耕耘,做了大量工作。首先是对《计算机程序设计的艺术》前3卷进行了修订充实,其中第一卷在1997年出了第三版,第二卷和第三卷在1998年出了第二版。其次对他过去设计的虚拟机MIX(用在《计算机程序设计的艺术》中)进行了扩充和完善,发展成为面向64bit计算的、具有十分丰富和灵活的指令集的MMIX,并为MMIX开发了一系列软件,使得用MMIX指令编写的程序能在几乎现有的各种计算机上都能高效地运行。此外,MMIX全部采用克努特所倡导的作文式程序设计方法。他的这一成果反映在他1999年出版的专著《MMIXware:用于下一个千年的RISC计算机》一书中(MMIXware:a RISC Computer for the Third Millennium,Springer Verlag)。书名反映了克努特对自己这一工作所追求的目标和期望。惟一的不足是:它缺乏图形用户界面。克努特在本书的前言中坦言自己缺乏足够的时间来完成这一任务,希望能有读者帮助他解决这一缺陷。如同克努特的其他软件成果一样,MMIXware也是免费的自由软件,感兴趣的读者可通过下列网址下载:

    http://www.Cs.faculty.stanford.edu/~knuth/mmix.news.html

    此外,克努特在1999年还出版了《数字印刷术》(Digital Typography,CSLI Pub.)一书。本书实际上是克努特在开发TEX和METAFONT期间就有关桌面出版的方方面面问题所写的论文和所作的报告的汇编,但克努特把字型、版面布局等枯燥的技术问题都同数学联系起来加以深入讨论,读来十分生动有趣。

    克努特是美国两院院士:1975年当选美国科学院院士,1981年当选美国工程院院士。

    应该说明,克努特对中国文化和中国文字都十分感兴趣。他为自己起了个中文名字叫“高德纳”,还为儿子和女儿分别取名“高小强”和“高小珍”。但考虑到《The Art of Computer Programming》的中译者已把他的名字译为“克努特”而广为人知,所以这里也用这个译名而没有用他自己取的中文名。

 
2008-10-17 13:33
0
雪    币: 277
活跃值: (106)
能力值: ( LV9,RANK:230 )
在线值:
发帖
回帖
粉丝
122
真的啊。。。算法我早想好了,程序就是敲不出来
2008-10-17 13:38
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
123
告诉我,我帮你敲
2008-10-17 13:55
0
雪    币: 277
活跃值: (106)
能力值: ( LV9,RANK:230 )
在线值:
发帖
回帖
粉丝
124
那这个答案算谁的呀
一起交就被出局了
2008-10-17 14:00
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
125
算你的,我只是个打字员而已
2008-10-17 14:04
0
游客
登录 | 注册 方可回帖
返回
//