文档介绍：信息学奥林匹克竞赛指导丛书
吴文虎主编
信息学奥林匹克竞赛指导
———1997— 1998 竞赛试题解析
吴文虎王建德著
清华大学出版社
内容简介
本书收集了 1997 年—1998 年国际国内信息学( 计算机) 奥林匹克竞赛试题, 重点分析解题思路和方
法,其中包括如何根据题意构建数学模型与相应算法, 以及如何编写程序等,可供大学、中学的电脑爱好
者学****和参考。
版权所有,翻印必究。
本书封面贴有清华大学出版社激光防伪标签, 无标签者不得销售。
书名: 信息学奥林匹克竞赛指导
———1997—1998 竞赛试题解析
作者: 吴文虎王建德著
出版者: 清华大学出版社( 北京清华大学学研大厦, 邮编 100084)
http:/ / ww w .tup .tsingh ua .edu .cn
印刷者: 北京密云胶印厂
发行者: 新华书店总店北京发行所
开本: 787× 1092 1/ 16 印张: 22 .75 字数: 523 千字
版次: 2001 年 1 月第 1 版 2001 年 1 月第 1 次印刷
书号: ISBN 7302040559/ T P· 2496
印数: 0001~5000
定价: 26 .00 元
前言
国际信息学奥林匹克( International Olympiad in Informatics , IOI) 从 1989 年到 1999
年,11 年赛事的健康发展得益于联合国教科文组织( U NESCO) 为这项赛事所做的准确定
位: 通过竞赛形式对有才华的青少年起到激励作用, 促其能力得以发展; 让青少年彼此建
立联系, 推动经验交流, 给学校这一类课程增加活力; 建立起教育工作者与专家档次上的
国际联系, 推进学术思想的交流。概括起来说, 就是启迪思路, 激励英才, 发展学科, 促进
交流。
学科奥林匹克是智力与能力的竞赛, 注重考查全面素质与创造能力。从这个意义
上讲, 信息学奥林匹克活动是素质教育的一个大课堂。在我国, 每年国家集训队都要将
“怎样做人, 怎样做事, 怎样求知和怎样健体”的指导思想纳入培训计划。这 11 年中国队
共派出参赛选手 43 人次, 累计获金牌 23 块、银牌 11 块、铜牌 9 块, 届届名列前茅, 正是因
为坚持了全面素质教育的指导思想, 把造就高素质有创造精神的人才作为活动的定位
目标。
回顾 11 年的竞赛可以看出, 参加高手云集的这种世界大赛是有相当难度的, 第一, 没
有大纲, 赛题范围没有界定, 谁也无法去猜测每年的主办国会出什么类型的难题; 第二, 计
算机科学与技术发展很快, 层出不穷的新思路和新成果会反映到试题中来; 第三, 所要
解决的试题往往涉及图论、组合数学、人工智能等大学开设的课程知识; 第四, 比较短的
给定解题时间与刁难的测试数据让选手必须拿出高超和精巧的解法, 无论在时间上还是
空间上都是优化的解法才能取得高分。有许多赛题没有固定的现成的解法, 选手要在比
赛现场凭借实力, 理出思路, 构建数学模型, 写出算法, 编出程序, 运行并验证整个构思是
否正确, 出解的时间是否能达到题目的要求, 等等。可以看出, 在这一过程中最重要的是
要有创造能力。为激发创新精神, 培养创造能力, 就需要树立新的教育观念和教学方法,
还要利用现代化的教学手段。引导学生学用电脑, 在使用中帮助开发人脑, 这可能是信息
学奥林匹克活动的最重要的一个特点。我认为在这项活动中应该培养学生的四种能力:
自学能力; 实践动手能力; 创新能力; 上网获取信息, 并能区分有用信息和无用信息的能
力。这样做的结果使许多选手不但有能力在世界赛场上拿金牌, 也有能力在学校的学****br/> 中名列前茅。
信息学奥林匹克十余年涌现出一大批出类拔萃的计算机后备人才, 在他们的带动下,
我国的青少年在普及计算机的大潮中阔步前进, 取得了可喜的成绩。历史已雄辩地证明:
计算机的普及就是要从娃娃做起, 这是“科教兴国”、中华崛起的需要。为了提高普及的层
次, 编写竞赛辅导教材是十分必要的, 也是广大青少年电脑爱好者所盼望的。这里我们将
1997—1998 国际国内大赛的试题集中起来进行剖析, 重点讲解题思路与方法。但是必须
· Ⅰ·
说明, 书中的解法仅起抛砖引玉的作用。
青少年是国家的希望, 不断提高青少年的科学素养是中华民族永远昂首屹立在世界
东方的根基所在。“精心育桃李, 切望青胜蓝”是我和王建德老师的共同心愿。
国际信息学奥林匹克中国队总教练
清华大学计算机系