程序设计导引及在线实践（第2版）_李文新、郭炜、余华山_9787302452348

本书是北京大学程序设计实习课程的内容和北京大学程序在线评测系统（POJ）的紧密结合，具有极强的实践性。本书的例题和习题精选自POJ题库，并且在叙述中穿插了许多精心编写的思考题，总结了学生在程序设计中易犯的错误。本书的作者均有丰富的工程软件开发经验和教学经验，因此本书中的程序代码均保持良好的风格。本书可以作为高等学校理工科相关专业程序设计类课程的教材，也可作为以 ACM/ICPC为代表的大学生程序设计竞赛的培训教材，还可供对程序设计感兴趣的读者学习参考。本书封面贴有清华大学出版社防伪标签，无标签者不得销售。

本书的*特点是和北京大学程序在线评测系统紧密结合，具有极强的实践性。北京大学程序在线评测系统(Peking University Online Judge System,POJ)是一个免费的公益性网上程序设计题库，网址为http://acm.pku.edu.cn/JudgeOnline(注意这里的网址区分大小写)。它包含2000多道饶有趣味的程序设计题目，题目大部分来自ACM/ICPC国际大学生程序设计竞赛，很多题目就反映工作和生活中的实际问题。这些题目有易有难，比如*简单的题A B Problem就是给出两个数，输出它们的和。用户可以针对某个题目编写程序并提交，POJ 会自动判定程序的对错。本书的所有例题和课后习题大都精选自POJ题库，难度较低，学生做习题时可以将自己的程序提交给POJ，几秒钟之内即可知道是对还是错。作为教学支持，每位学生在POJ上可以建立自己的账号，教师在POJ上一眼就能看到学生是否已经完成布置的习题，这几乎将教师评判学生作业的工作量减少到零。POJ对于程序的正确性评判是极为严格的，学生的程序根据POJ给出的输入数据进行计算并输出结果，POJ在服务器端编译、运行学生提交的程序，取得输出结果和标准答案对比，必须一个字节都不差，程序才能够通过。这对于培养严谨、周密的程序设计作风极为有效，学生必须考虑到每一个细节和特殊边界条件，而不是大体上正确就能够通过。传统的人工评判是难以做到这一点的。本书的另一特点是在叙述中穿插了许多精心编制的思考题，特别适合教师进行启发式教学。思考题没有答案，以便教师引导学生进行讨论。程序设计导引及在线实践(第2版)本书还有一个亮点，就是在许多例题后都会总结学生在完成该题时容易犯的典型错误，让学生少走弯路。这些错误都总结自学生在POJ上提交的程序，因而具有典型性。

主任：李晓明副主任：蒋宗礼卢先和委员：（按姓氏笔画为序）马华东马殿富王志英王晓东宁洪刘辰孙茂松李仁发李文新杨波吴朝晖何炎祥宋方敏张莉金海周兴社孟祥旭袁晓洁钱乐秋黄国兴曾明廖明宏秘书：张瑞庆

本书主审：李晓明
本书序PREFACE
本书是一本与众不同的程序设计入门教材，实践性极强，不论对于高等学校计算机专业的学生，还是非计算机专业的学生，都非常适用。目前绝大部分程序设计入门教材的主要内容就是详细介绍一门程序设计语言，这对于高等学校计算机专业的学生是远远不够的；对于非计算机专业的学生也略显肤浅。许多大学本科计算机专业的课程设置，在程序设计语言和数据结构这两门课之间，并无空间进行基础算法的教学，这就容易导致学生由于基本技能缺失而在学习数据结构课程时产生困难，或难以学精。对于非计算机专业的学生来说，如果仅掌握一门程序设计语言的语法规则，写几个打印由星号组成的三角形之类的玩具程序，而对计算机科学的基础与灵魂算法一无所知，不明白计算机到底是怎么解决问题的，那么在日后的工作中，不但不可能自己编写实用程序，甚至不能敏感地及时意识到哪些问题适合用计算机处理，可以交给计算机专业人士来做。本书将程序设计语言和最基本的算法思想相结合，能够有效避免上述现象。本书的最大特点是和北京大学程序在线评测系统紧密结合，具有极强的实践性。北京大学程序在线评测系统(Peking University Online Judge System,POJ)是一个免费的公益性网上程序设计题库，网址为http://acm.pku.edu.cn/JudgeOnline(注意这里的网址区分大小写)。它包含2000多道饶有趣味的程序设计题目，题目大部分来自ACM/ICPC国际大学生程序设计竞赛，很多题目就反映工作和生活中的实际问题。这些题目有易有难，比如最简单的题A B Problem就是给出两个数，输出它们的和。用户可以针对某个题目编写程序并提交，POJ 会自动判定程序的对错。本书的所有例题和课后习题大都精选自POJ题库，难度较低，学生做习题时可以将自己的程序提交给POJ，几秒钟之内即可知道是对还是错。作为教学支持，每位学生在POJ上可以建立自己的账号，教师在POJ上一眼就能看到学生是否已经完成布置的习题，这几乎将教师评判学生作业的工作量减少到零。POJ对于程序的正确性评判是极为严格的，学生的程序根据POJ给出的输入数据进行计算并输出结果，POJ在服务器端编译、运行学生提交的程序，取得输出结果和标准答案对比，必须一个字节都不差，程序才能够通过。这对于培养严谨、周密的程序设计作风极为有效，学生必须考虑到每一个细节和特殊边界条件，而不是大体上正确就能够通过。传统的人工评判是难以做到这一点的。本书的另一特点是在叙述中穿插了许多精心编制的思考题，特别适合教师进行启发式教学。思考题没有答案，以便教师引导学生进行讨论。程序设计导引及在线实践(第2版)本书还有一个亮点，就是在许多例题后都会总结学生在完成该题时容易犯的典型错误，让学生少走弯路。这些错误都总结自学生在POJ上提交的程序，因而具有典型性。本书中代码的风格也很值得一提。许多程序设计教程，其编写者虽有丰富的教学经验，但却不一定具有实际的软件开发经历，因而书中的例子程序往往在变量命名、代码效率等程序设计风格方面不是很在意，只求正确即可，教学代码的痕迹明显。而本书的作者除了具有多年的教学经验以外，还从事过多年的软件开发。李文新教授是国内第一个自主研制的地理信息系统开发环境GeoUnion的主要设计者和核心代码编写者之一，曾经担任过图原空间信息技术有限公司和长天科技有限公司的总工程师。她目前是中国计算机学会信息学奥林匹克竞赛科学委员会的科学委员，是ACM/ICPC竞赛北京大学代表队的原任教练和现任领队。余华山副教授多年来一直从事支持高性能计算的程序开发与运行环境的研究工作，是集群并行程序开发与运行平台P_HPF系统的主要研制者之一，主持开发了计算网格协同平台 Harmonia系统。在中国教育科研网格China Grid公共软件支撑平台CGSP的研制过程中，他是总体设计的主要负责人之一，并负责CGSP信息服务系统的设计和实现。郭炜老师的专业研究方向是计算机辅助教学，他独立开发了《我爱背单词》等系列著名英语学习软件，同时还担任教练，和李文新教授一起率领北京大学ACM/ICPC国际大学生程序设计竞赛队在国际竞赛中取得了较好名次。本书中的例子程序的代码风格优美、注释完备、可读性强，以此作为范例，对培养良好的程序设计风格，日后在团队开发中赢得同事的信任和喜爱十分有益。在这个提倡创新的年代，本书是特别富有创意的，希望并相信读者能够喜欢。
2007年8月北京大学教授原教育部高等学校计算机科学与技术教学指导委员会副主任21世纪大学本科计算机专业系列教材编委会主任
前言FOREWORD计算机程序是通过在计算机内存中开辟一块存储空间，并用一个语句序列不断修改这块存储空间上的内容，最终得到问题的答案的方法来解决实际问题的。计算机程序一般需要用一种具体的程序设计语言表达出来。一种计算机语言通过定义变量的形式给出了申请内存的方式，并通过表达式和赋值语句给出了对内存中的数据进行运算和修改的方法，通过分支和循环语句提供了用不同方式安排语句序列的能力。大部分计算机语言还提供了基础函数库来完成一些常用的计算和数据处理的功能。使用计算机程序解决实际问题，首先要能够将一个具体问题抽象成一个可计算的问题，并找出可行的计算过程；其次是掌握一门程序设计语言，将设计的计算过程写成具体的代码在机器上运行。作者总结了多年计算机程序设计类课程的教学经验，认为在程序设计课程的教学中应该把握5个基本的教学环节：第一，让学生充分理解计算机程序在内存中的运行原理和过程。在程序运行过程中任意时刻都清楚语句运行到了哪里，以及当前存储数据的内存区的内容是什么。只有清楚这些，才能在程序调试过程中及时地找到出错位置，并修改错误，最终让程序按照设计者的意图执行。第二，以一门高级程序设计语言为例，让学生了解该设计语言使用哪些语句定义变量，哪些语句修改变量，变量有哪些基本类型，每种类型的变量占多大的存储空间，不同类型的变量可以进行哪些运算，哪些语句用来控制语句序列的分支和循环，如何用简单变量组合出复杂变量（如数组或结构体），如何控制复杂的计算过程（如通过函数实现分而治之），有哪些库函数是可用的，等等。第三，讲授一些常用的、基本的计算过程，使得学生在解决复杂问题之前，手上有一些可用的基本方法。例如，如何通过分支和循环语句模拟一个手工计算的过程，进行不同数制转换时可以选定一个共同的基数进行转换，字符串处理的问题应该多使用库函数，处理日期问题时可以用一个数组来存储每个月的天数，这样可以很方便地处理不规则的数据，等等。第四，围绕一些具体的问题实例，让学生学会通过分析问题抽象出数学模型，从而设计出计算过程和中间数据的存储方式，最终实现代码并调试成功。学生只有通过这样一个完整的程序设计过程的训练，才能充分理解写程序是要干什么，并且学会判断什么样的问题适合用计算机来解决。第五，学生学习效果的检验方式直接决定了最终的教学效果。如果想让学生真正学会独立动手写出正确的程序，就必须采取上机考查的方式，要求学生针对实际问题写出最终可以正确运行并能解决问题的程序。本书的内容安排充分体现了上述的教学理念。为了方便理解例题中的代码，本书先用1/3的篇幅简明扼要地介绍C/C 语言的基本语法，包括变量的定义，变量的值的修改，基本的变量类型，用基本类型的变量构造数组、结构体等复杂的数据类型，定义表达式，控制语句序列，以及常用的C语言标准库函数。程序设计导引及在线实践(第2版)之后所有的内容都采用以问题为中心的讲述方式。首先用近1/3的篇幅讲述面对不同类型的常见问题，应该如何抽象计算过程，并将计算过程写成具体代码。这些问题包括简单计算问题、数制转换问题、字符串处理问题、日期和时间处理问题、计算过程模拟问题等。接着用近1/4的篇幅讲述了计算机程序设计中常用的但不同于数学计算方法的三种算法思想：枚举、递归和动态规划。本书的最后两章讲述了如何用基本的数据类型构造一些稍微复杂的数据结构：链表和二叉树，作为本书向数据结构递进的序曲。配合本书的教学，我们使用了北京大学在线评测系统，书中所有的例题和练习题都在该系统上，学生可以随时针对某一题目编写程序并提交给系统，几秒钟内就可以获得正确与否的回答。我们也利用该系统进行学生的期中、期末考试，学生必须现场在给定的时间内完成从问题分析到代码实现的全部过程才能通过考试。为了测试程序在不同数据输入下的正确性，该系统中的题目大部分采用输入多组测试数据的形式，所以在书中会看到每个程序都要读入多组数据进行处理。这些测试数据是彼此独立的，可以读入一组，处理一组并输出结果，然后再读入下一组。本书作者分工如下：李文新编写第1章中的1.1、1.2、1.4、1.7、1.8、1.9节，第2章，第5章，第9章中的9.3、9.4、9.6、9.10节，以及附录A和附录B。郭炜编写第1章中的1.3、1.5、1.6、1.10～1.19节，第6章，第7章，第9章中的9.1、9.2、9.5、9.7、9.8和9.9节，以及第10章。余华山编写第3章、第4章、第8章、第11章和第12章。由于水平和精力所限，书中难免存在不当之处，恳请专家和读者批评指正。
作者2016年9月于燕园

你还可能感兴趣

我要评论