《程序设计导引及在线实践》

http://www.tup.com.cn

fengmian

作者简介

李文新,1986年以辽宁省抚顺市理科高考第一名的成绩考入北京大学计算机科学技术系,1993年获北京大学硕士学位留校任教,2001年获北京大学博士学位,2004年获香港理工大学博士学位。现为北京大学信息科学技术学院教授,基础教育部副主任,北京大学计算机实验教学中心主任。主要研究领域为人.....等等。

郭炜,曾讲授《操作系统》(辅修),《Java程序设计》(辅修),《计算机专业英语》;正在讲授《程序设计实习》、《Windows程序设计》。讲授《程序设计实习》已经至少6个学年。 从2004年起担任北京大学ACM国际大学生程序设计竞赛队教练,和李文新老师一起率队进入全球总决.......等等。

余华山,北京大学信息科学技术学院副教授。2001年获得北京大学计算机系软件与理论专业博士学位,留校任教,研究方向是并行处理、网格分布式计算。在教学方面,先后承担了本科生课程《面向对象技术概论》和《程序设计实习》、研究生课程《并行程序设计》。 目前承担《程序设计实习.........等等。

一、本书序

本书是一本与众不同的程序设计入门教材,实践性以一种特殊的方式被提高到了十分重要的地位,不论对计算机专业的学生,还是非计算机专业的学生,都非常适用。
目前许多程序设计入门教材的主要内容就是详细介绍一门程序设计语言。对于计算机专业的学生,这远远不够;对于非计算机专业的学生,也略显肤浅。许多大学的本科计算机专业程序设计课程的教法,重语法规则,缺算法概念,这就容易导致学生由于基本技能缺失而在学习数据结构时产生困难,或难以学精。对于非计算机专业的学生来说,仅掌握一门程序设计语言的语法规则,写几个打印由星号组成的三角形之类的“玩具”程序,而对计算机科学的基础与灵魂 -- 算法一无所知,不明白计算机到底是怎么解决问题的,那么在日后的工作中,不但不可能自己编写实用程序,甚至会无法敏感地及时意识到,哪些问题很适合用计算机处理,可以交给计算机专业人员来做。本书将程序设计语言和最基本的算法思想相结合,是避免上述现象的一个有益尝试。
本书的最大特点是和“北京大学程序在线评测系统"紧密结合,因而把实践性摆到了一个特殊的地位。“北京大学程序在线评测系统”(简称“POJ”)是一个免费的公益性网上程序设计题库,网址为http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计竞赛,很多题目就反映工作和生活中的实际问题。用户可以针对某个题目编写程序并提交,让POJ自动判定程序的对错,几秒之内即可知道对还是错。作为教学支持,每个学生在POJ上可以建立自己的账号,教师在POJ上一眼就能看到布置的习题学生是否已经完成,这几乎将教师评判学生作业的工作量减少到零。POJ对于程序的正确性评判是极为严格的,不仅逻辑要对,而且数据的格式也要对。这对于培养严谨、周密的程序设计作风极为有效,学生必须考虑到每一个细节和特殊边界条件,而不是大体上正确就能通过。传统的人工评判是难以做到这一点的。
本书的另一特点是在叙述中穿插了许多精心编制的思考题,特别适合教师进行启发式教学。思考题没有答案,以便教师提问,引发讨论。
本书还有一个亮点,就是在许多例题后都会总结学生在完成该题时容易犯的典型错误,让学生少走弯路。这些错误都总结自学生在POJ上提交的程序,因而具有典型性。

本书中代码的风格也很值得一提,它来自作者们丰富的教学与软件开发经验。李文新教授是国内第一个自主研制的地理信息系统开发环境Geo-Union的主要设计者和核心代码编写者之一,曾经担任过图原空间信息技术有限公司和长天科技有限公司的总工程师。她目前是中国计算机学会信息学奥赛科学委员会的科学委员,ACM竞赛北京大学代表队的原任教练和现任领队。余华山副教授多年来从事支持高性能计算的程序开发与运行环境的研究工作,主持开发了计算网格协同平台 Harmonia系统。在ChinaGrid公共软件支撑平台CGSP的研制过程中,他是总体设计的主要骨干之一,并负责CGSP信息服务系统的设计和实现。郭炜老师的专业方向是计算机辅助教学,他是《我爱背单词》等系列著名英语学习软件的唯一作者。因而本书中的例子程序代码风格优美,注释完备,可读性强。以此作为范例,对培养良好的程序设计风格,日后在团队开发中赢得同事的信任和喜爱十分有益。
在这呼吁创新的年代,本书是富有创意的,希望并相信读者能喜欢。

qianming

二、前言

计算机程序是通过在计算机内存中开辟一块存储空间,并用一个语句序列不断修改这块存储空间上的内容,最终得到问题的解答来解决实际问题的。计算机程序一般需要用一种具体的程序设计语言表达出来。一种计算机语言通过定义变量的形式给出了申请内存的方式,并通过表达式和赋值语句给出了对内存中的数据进行运算和修改的方法。通过分支和循环语句提供了用不同方式安排语句序列的能力。大部分计算机语言还提供了基础函数库完成一些常用的计算和数据处理的功能。

使用计算机程序解决实际问题,首先要能够将一个具体问题抽象成一个可计算的问题,并找出可行的计算过程;其次是掌握一门程序设计语言,将设计的计算过程写成具体的代码在机器上运行。

作者总结了多年计算机程序设计类的课程教学经验,认为在程序设计课程的教学中应该把握五个基本的教学环节:第一,让学生充分理解计算机程序在内存中的运行原理和过程。在程序运行过程中任意时刻都清楚语句运行到哪里了,当前存储数据的内存区的内容是什么。只有清楚这些,才能在程序调试过程中及时地找到出错位置,并修改错误,最终让程序按照设计者的意图执行。第二,以一门高级程序设计语言为例,让学生了解该设计语言使用哪些语句定义变量,哪些语句修改变量,变量有哪些基本类型,每种类型的变量占多大的存储空间,不同类型的变量可以进行哪些运算,哪些语句用来控制语句序列的分支和循环,如何用简单变量组合出复杂变量(例如数组或结构体),如何控制复杂的计算过程(例如通过函数实现分而制之),有哪些库函数是可用的,等等。第三,讲授一些常用的基本的计算过程,使得学生在解决复杂问题之前,手上是有一些基本方法可用的。例如:如何通过分支和循环语句模拟一个手工计算的过程,进行不同数制转换时,可以选定一个共同得基数进行转换,字符串处理的问题应该多使用库函数,处理日期问题时可以用一个数组来存储每个月的天数,这样可以很方便地处理不规则的数据,等等。第四,围绕一些具体的问题实例,让学生学会通过分析问题,抽象出数学模型,从而设计出计算过程和中间数据的存储方式,最终实现代码并调试成功。学生只有通过这样一个完整的程序设计过程的训练,才能充分理解写程序是要干什么,并且学会判断什么样的问题是适合用计算机来解决的。第五,学生学习效果的检验方式直接决定了最终的教学效果。如果想让学生真正学会独立动手写出正确的程序,就必须采取上机考查的方式,要求学生针对实际问题写出最终可以正确运行并能解决问题的程序。

本书的内容安排充分体现了上述的教学理念。为了方便理解例题中的代码,本书先用三分之一的篇幅简明扼要地介绍了C/C++语言的基本语法,包括变量的定义,变量的值的修改,基本的变量类型,用基本类型的变量构造数组、结构体等复杂的数据类型,定义表达式,控制语句序列,以及常用的C语言标准库函数。?

之后所有的内容都采用以问题为中心的讲述方式。首先用近三分之一的篇幅讲述面对不同类型的常见问题,应该如何抽象计算过程,并将计算过程写成具体代码。这些问题包括简单计算题、数制转换问题、字符串处理问题、日期和时间处理问题、计算过程模拟问题等等。

接着用近四分之一的篇幅讲述了计算机程序设计中常用的但是不同于数学计算方法的三种算法思想:枚举、递归和动态规划。

在本书中的最后两章,讲述了如何用基本的数据类型构造一些稍微复杂一些的数据结构:链表和二叉树,作为本书向数据结构递进的序曲。

配合这本书的教学,我们使用了北京大学在线评测系统,书中所有的例题和练习题都在该系统上,学生可以在任意时刻针对某一题目编写程序并提交给系统,几秒钟内就可以获得正确与否的回答。我们也利用该系统进行学生的期中期末考试,学生必须现场在给定的时间内完成从问题分析到代码实现的全部过程才能通过考试。为了测试程序在不同数据输入下的正确性,该系统中的题目大部分采用输入多组测试数据的形式。所以我们在书中会看到每个程序都要读入多组数据进行处理。这些测试数据是彼此独立的,可以读入一组,处理一组并输出结果,然后再读入下一组。

本书各位作者分工如下:李文新老师编写第一章、第二章第一节、第二节、第四节、第七节至第九节、第三章、第六章、第十章。郭炜老师编写第二章第三节、第五节、第六节、第十节至第十九节、第七章、第八章、第十一章。余华山老师编写了第四章、第五章、第九章、第十二章、第十三章。

三、目录

第一章 C/C++语言概述

1.1 程序的基本框架
1.2 变量
1.3 C/C++语言的数据类型
1.4 常量
1.5 运算符和表达式
1.6 注释
1.7 分支语句
1.8 循环语句
1.9 函数
1.10 标准输入输出
1.11 全局变量和局部变量
1.12 数组
1.13 字符串
1.14 指针
1.15 结构
1.16 文件读写
1.17 C语言标准库函数
1.18 命令行参数
1.19 C/C++编码规范

第二章 简单计算题

2.1 例题:鸡兔同笼
2.2 例题:棋盘上的距离
2.3 例题:校门外的树
2.4 例题:填词
2.5 例题:装箱问题
练习题

第三章 数制转换问题

3.1 相邻数字的基数等比问题:确定进制
3.2 相邻数字的基数不等比:skew数
练习题

第四章 字符串处理

4.1 简单的字符串操作示例
4.2 例题:统计字符数
4.3 例题:487-3279
4.4 例题:子串
4.5 例题:Caesar密码
练习题

第五章 日期和时间处理

5.1 例题:判断闰年
5.2 例题:细菌繁殖
5.3 例题:玛雅历
5.5 例题:时区间时间的转换
练习题

第六章 模拟

6.1 例题:约瑟夫问题
6.2 例题:花生问题
6.3 例题:显示器
6.4 例题:排列
练习题

第七章 高精度计算

7.1 例题:大整数加法
7.2 例题:大整数乘法
7.3 例题:大整数除法
7.4 例题:麦森数
练习题

第八章 枚举

8.1 枚举的基本思想
8.2 简单枚举的例子:生理周期
8.3 数学模型中包括多个变量的例子:称硬币
8.4 搜索空间中解不唯一的例子:完美立方
8.5 遍历搜索空间的例子:熄灯问题
8.6 优化判断条件的例子:讨厌的青蛙
练习题

第九章 递归

9.1 递归的基本思想
9.2 例题:菲波那契数列
9.3 例题:二叉树
9.4 例题:逆波兰表达式
9.5 例题:放苹果
9.6 例题:红与黑
9.7 例题:八皇后问题
9.8 例题:木棍问题
练习题

第十章 动态规划

10.1 什么是动态规则
10.2 动态规则解题的一般思路
10.3 例题:最长上升子序列
10.4 例题:帮助Jimmy
10.5 例题:最长公共子序列
10.6 例题:陪审团的人选
练习题

第十一章 链表

11.1 单向链表、链表结点的插入
11.2 带表头的单向链表、链表的搜索
11.3 双向链表、链表结点的排序
11.4 循环链表、链表结点的删除
11.5 链表的应用:计算每个作业的运行时间
练习题

第十二章 二叉树

12.1 二叉树的建立
12.2 基于递归的二叉树遍历
12.3 平衡二叉树
练习题

附录A 北京大学程序在线评测系统介绍
A.1 POJ的使用情况
A.2 POJ的主要功能
A.3 使用本书结合POJ进行教学时的用法

附录B 本书题目在POJ上的编号

 

Home Page   Go Back  To top


All Rights Reserved 2003-2006 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator