大学生程序设计acm辅导教程完整但版 word.doc
《大学生程序设计acm辅导教程完整但版 word.doc》由会员分享,可在线阅读,更多相关《大学生程序设计acm辅导教程完整但版 word.doc(389页珍藏版)》请在三一文库上搜索。
1、国际大学生程序设计竞赛辅导教程国际大学生程序设计竞赛辅导教程郭嵩山 崔昊 吴汉荣 陈明睿 著北京大学出版社1前言ACM 国际大学生程序设计竞赛(ACMInternational Collegiate Programming Contest, 简称 ACM/ICPC)是由国际计算机界历史最悠久、颇具权威性的组织 ACM 学会(Association for Computer Machinery)主办,是世界上公认的规模最大、水平最高的国际大学生程序设计 竞赛,其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。该项竞 赛从 1970 年举办至今已历 25 届,因历届竞赛都荟萃了世
2、界各大洲的精英,云集了计算机界 的“希望之星”,而受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关 注,成为世界各国大学生最具影响力的国际级计算机类的赛事,ACM 所颁发的获奖证书也 为世界各著名计算机公司、各知名大学所认可。该项竞赛分区域预赛和世界决赛两个阶段进 行,各预赛区第一名自动获得参加世界决赛的资格,世界决赛安排在每年的 34 月举行,而 区域预赛安排在上一年的 9 月12 月在各大洲举行。ACM/ICPC 的区域预赛是规模很大,范 围很广的赛事,近几年,全世界有 1000 多所大学,近 2000 支参赛队在六大洲的 2830 个赛 站中争夺世界决赛的 60 个名额,其
3、激烈程度可想而知。与其他编程竞赛相比,ACM/ICPC 题目难度更大,更强调算法的高效性,不仅要解决 一个指定的命题,而且必需要以最佳的方式解决指定的命题;它涉及知识面广,与大学计算 机系本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关 课程直接关联,对数学要求更高,由于采用英文命题,对英语要求较高,ACM/ICPC 采用 3 人合作、共用一台电脑,所以它更强调团队协作精神;由于许多题目并无现成的算法,需要 具备创新的精神,ACM/ICPC 不仅强调学科的基础,更强调全面素质和能力的培养;由于 ACM/ICPC 是采用 5 小时全封闭式竞赛,参赛队员与外界完全隔离,
4、完全独立完成,没有任 何水份,是其实际能力的真实表露,其成绩可信度甚高;但 ACM/ICPC 又是一种“开卷考 试”,可以带任何书籍、资料甚至源程序代码清单(但不能带软盘),不需要去死背算法,而 强调的是算法的灵活运用;与其它计算机竞赛(如软件设计,网站设计等)相比,ACM/ICPC 有严谨而客观的评判规则(严格的数据测试),排除了因评委的主观因素而造成评审不公平 的现象,所以,ACM/ICPC 对成绩的争议较少,大家比较心服口服。综观近三年(19982000)中山大学共参加了 6 次地区预赛,成绩全部在三甲之列:连 续三年夺得上海站季军(19992000 年还连续两年夺得上海站第四名)、夺得
5、台北站冠军、i香港站亚军和日本站亚军;并连续三年争得了世界决赛权。并在第 24 届(2000 年)在美国佛罗里达州奥兰多市举行世界决赛中夺得了第 11 名的好成绩,在第 25 届(2001)在加拿大 温哥华市举行的世界决赛中首获铜牌(世界第 14 名)。为了帮助高等院校的大学生们备战国际大学生程序设计竞赛,帮助他们提高程序设计水 平和培养更强的分析问题和解决问题的能力,我们编写了这本辅导教材。本书所用的语言是 Pascal(Delphi)。全书共分六章,第 1 章先介绍 Delphi 的运行环境,以便于读者能更好地读 通后面各章的程序;第 2 章采用精讲的方式,简明扼要、深入浅出地介绍了在国际
6、大学生程 序设计竞赛中经常用到的各种典型算法;而在第 3 章中,我们着重介绍了寻找最优解的算法, 诸如图论中的搜索算法和如何运用动态规划的思维来解决实际问题等方法;在第 4 章中,我 们从 ACM/ICPC 世界决赛和区域预赛试题中精选了有代表性的 10 道例题,通过对例题的详 细分析,力图让读者能更深刻地理解第 2、3 章中所介绍的基本算法;在第 5 章中,我们精 选了一批有代表性的试题作为习题,并为这些习题设计了严格的、有梯度的测试数据,以便 于读者检验自己编程的正确性;而在第 6 章中,我们给出了这些习题的详细分析和解答。为 便于读者们学习和理解,本书的全部例题和习题都给出了我们自己编写
7、的参考程序,而所有 参考程序都有详细的注释。参加编写本书的 4 位作者,第一位是国际大学生程序设计竞赛中山大学队的教练,其余3 位都是参加过多次世界决赛和亚洲多个赛站区域预赛的中山大学队的主力队员。他们都是 在校的研究生,我们期望能将自己的知识、经验、心得和体会,奉献给广大的程序设计爱好 者,以便与大家共同探讨和交流。本书可以作为高等院校大学生和研究生们准备参加各级国际大学生程序设计竞赛活动 的辅导教材和试题集,也可以作为高等院校研究生和本科高年级学生学习相关课程的参考 书,也可以作为省级及以上信息学奥林匹克优秀选手准备高层次程序设计竞赛的参考用书。中山大学计算机科学系 97 级孔颖同学(也是
8、参加过两次世界决赛和亚洲多个赛站区域 预赛的中山大学队的主力队员)曾参与过本书的一些程序的编写工作,在此表示衷心的感谢。由于我们水平所限,书中难免有不足之处,欢迎读者批评指正,谢谢!作者2001 年 10 月ii第一章 Delphi 简介第一节 Delphi 的运行环境1.1.1 Delphi 简介Delphi 是著名的 Borland 公司开发的可视化软件开发工具。“真正的程序员用 c,聪明 的程序员用 Delphi”,这句话是对 Delphi 最经典、最实在的描述。Delphi 被称为第四代编程 语言,它具有简单、高效、功能强大的特点。和 VC 相比,Delphi 更简单、更易于掌握,而
9、在功能上却丝毫不逊色;和 VB 相比,Delphi 则功能更强大、更实用。可以说 Delphi 同时 兼备了 VC 强大的功能和 VB 简单易学的特点。因此,它一直是程序员至爱的编程工具。Delphi 具有以下的特性:基于窗体和面向对象的方法,高速的编译器,强大的数据库 支持,与 Windows 编程紧密结合,强大而成熟的组件技术。但最重要的还是 Object Pascal语言,它才是一切的根本。Object Pascal 语言是在 Pascal 语言的基础上发展起来的,简单易 学。Delphi 提供了各种开发工具,包括集成环境、图像编辑(Image Editor),以及各种开发数据库的应用程
10、序,如 Desktop DataBase Expert 等。除此之外,还允许用户挂接其它的应 用程序开发工具,如 Borland 公司的资源编辑器(Resourse Workshop)。在 Delphi 众多的优势当中,它在数据库方面的特长显得尤为突出:适应于多种数据库结构,从客户机服务机模式到多层数据结构模式;包括高效率的数据库管理系统和新一代 更先进的数据库引擎;具备最新的数据分析手段和提供大量的企业组件。Delphi 发展至今,从 Delphi、Delphi到现在的 Delphi6,不断添加和改进各种特性,功能越来越强大。本书将以 Delphi6 为基础,介绍 Delphi 的开发环境、
11、基本概念,让读者能 在 Delphi 环境下编写竞赛程序。1.1.2 Delphi 的 IDE 环境启动 Delphi 后,屏幕上会出现如图 1.1 所示的界面,这是使用 Delphi 开发 Windows 应 用程序和 Internet 应用程序常见的界面。188第 页图 1.1与上面两种应用不用,编写竞赛程序常常是使用控制台应用程序(Console Application), 创建一个新的控制台应用程序可以使用如下的步骤:(1)使用菜单 File - New - Other,如图 1. 2 所示图 1. 2(2)在 New Items 对话框中选择新建“Console Applicatio
12、n”( 图 1. 3)图 1. 3新建的控制台应用程序界面如图 1. 4 所示:菜单和工具栏代码编辑窗口图 1. 4下面将开始我们的第一个程序:Hello 程序,并且在 Delphi 环境中运行这个程序。 程序在代码编辑窗口中编辑,例如可以在代码编辑窗口中输入 Hello 程序:program Hello;$APPTYPE CONSOLEusesSysUtils;begin TODO -oUser -cConsole Main : Insert code here WriteLn(Hello World.);ReadLn;end.其 中 , 只 有 下 划 线 部 分 是 手 工 输 入 的
13、, 其 他 部 分 是 Delphi 产 生 的 代 码 。 语 句“WriteLn(Hello World.)”是输出“Hello World.”的字样;语句“ReadLn”是等待输入一个 回车符号,以便观察程序输出结果。然后选择菜单”Run-Run”运行程序。这时,屏幕中会出现“Hello World.”的字样,如图 1. 5 所示。图 1. 51.1.3 Delphi 程序的编译、运行和调试下表列出了编译、运行和调试 Delphi 程序的常用命令:功能菜单命令快捷方式 编译(Compile)Project - CompliteCtrl + F9 运行(Run)Run - RunF9 单步
14、跟踪(Trace Into)Run - Trace IntoF7 单步执行(Step Over)Run - Step OverF8执行到光标所在位置(Run to Cursor)Run - Run to CursorF4设置(Breakpoint)Run - Add Breakpoint鼠标单击代码行左边的蓝点 观察窗口(Watch)Run - Add WatchCtrl + F5更多的命令请参考 Delphi 的联机帮助。第二节 Delphi 常量标识符是 Delphi 应用程序中一些量的名称,这些量包括变量(var)、常量(const)、类型 (type)、过程(procedure)、方法
15、(Method)及其他,Object Pascal 在应用标识符时,必须首先说 明它们。Object Pascal 是强类型语言,它的编译器可以检查确保赋给变量或属性的值是正确 的类型,以便于您改正错误。由于 Object Pascal 是编译语言,所以 Delphi 的执行速度要比 使用解释语言快得多。在使用标识符前说明它们,可以减少程序错误并增加代码的效率。有 一点需要特别说明的是 Object Pascal 中的标识符是不区分大小写的,这和 C/C+语言有很大 的区别。例如:Delphi 和 delphi 被看成是同一个标识符。常量说明是为一个标识符赋予一个值,在程序执行过程中是不可改变
16、的。常量说明使用保留 字“const”作为开头。格式为:const 常量名=常量值;下面的例子声明了三个常量:constPi = 3.14159; Age = 34;ProductName = Delphi;上文的三个常量分别是实型、整型和字符串型常量。常量用“= 表示两边的值是相等的。和 C/C+语言不同,Object Pascal 的字符串常量是使用单引号()作为定界符的,例如上面 的Delphi,而不是使用双引号(”)。第三节 Delphi 变量变量是程序代码中代表一个内存地址的标识符,而该地址的内存内容在程序代码执行时 可以被改变。在使用变量前必须对它进行说明,即对它进行命名,并说明它
17、的类型。在所有 变量说明以前加上保留字 var。变量说明左边是变量的名称,右边则是该变量的类型,中间 用(:)隔开。即格式为:var 变量名:变量类型;例如:varValue ,Sum : Integer; Name : String;在 Delphi 中,可以在变量声明同时赋初始值,格式为:const 变量名:变量类型=变量初始值;注意,此时是使用 const 保留字开头,而不是 var。 例如:constValue: Integer:=10; Name : String=Gates;第四节 Delphi 类型Delphi 有两大数据类型,一类是系统已经预定义的,另一类是用户自定义的。 Ob
18、ject Pascal 有一些系统预定义的数据类型,这些类型包括有:整型、实型、布尔型、字符型、指 针型;而用户自定义的数据类型有枚举型、子界型、数组型、集合型、记录型、对象型等, 您可以利用这些用户预定义的数据类型来构造新的数据类型以满足程序的特定需要。1.4.1 Delphi 预定义类型Object Pascal 有多个预定义的数据类型,您可以说明任何这些类型的变量:1整型:与 CPU 和操作系统相关的整型包括 Integer 和 Cardinal,在当前 32 位编译器下,取值范 围如下:类型范围格式IntegerCardinal-2147483648.21474836470.42949
19、67295signed 32-bitunsigned 32-bit与 CPU 和操作系统无关的整型如下:类型范围格式Shortint-128.127signed 8-bitSmallintLongint-32768.32767-2147483648.2147483647signed 16-bitsigned 32-bitInt64Byte-263.263-10.255signed 64-bitunsigned 8-bitWord0.65535unsigned 16-bitLongword0.4294967295unsigned 32-bit2实型:下表列出了实型的范围和存储格式:类型范围有效位
20、占用字节(bytes)Real482.9 x 10-39.1.7 x 103811-126Single1.5 x 10-45.3.4 x 10387-84Double5.0 x 10-324.1.7 x 1030815-168Extended3.6 x 10-4951.1.1 x 10493219-2010Comp-263+1 . 263-119-208Currency-222337203685477.5808.922337203685477.580719-208通用类型 Rea 在当前的解释下,等价于 Double。类型范围有效位占用字节(bytes)Real5.0 x 10-324.1.7
21、 x 1030815-1683布尔型:Boolean,只包含 true 或 False 两个值,占用 1 字节内存。4字符型:Char,一个 ASCII 字符;字符型的常量形式上和字符串型常量一样,都是使用单引号() 作为定界符,例如:A。5字符串类型:String 一串最长可达 2G 个 ASCII 字符。6指针型:Pointer,可以指向任何特定类型。相当与 C/C+中的“void*”。类型的兼容性: 整型类别和实型类别都各有五种类型,同一类别中,所有的类型与其他同类别的都相容,您可以将一种类型的值赋给相同类别中不同类型的变量或属性,而只需要这个值的范围在被赋值的变量或属性的可能值范围内。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学生程序设计acm辅导教程完整但版 word 大学生 程序设计 acm 辅导 教程 完整
链接地址:https://www.31doc.com/p-2102479.html