本篇小结

本篇既是程序设计语言课程的复习，也是数据结构实验课程的入门。我们引领读者进行简单计算、简单模拟和简单递归的编程实验。

所谓简单计算指的是在“输入–处理–输出”的编程模式中，计算处理过程相对简单，重心放在提高程序可读性并按照格式和效率要求输入/输出上。本篇通过编程解简单计算题的实验，引导读者初步实现“四个学会”。

1）学会如何编写结构清晰、可读性强的程序。

2）学会如何正确处理多组测试数据，例如根据输入结束标志和组内数据结束标志设计循环结构；在所有测试数据采用同一运算且运算结果的数据范围已知的情况下，采用离线计算方法提高计算时效。

3）学会如何通过设定和使用精度常量来减少实数运算的精度误差。

4）学会通过使用二分法来避免蛮力计算，例如采用减半递推计算求解问题，在数据有序的情况下进行二分查找。

要提高编程能力，需要从熟练掌握基本的编程方法做起。

所谓模拟法（simulation）指的是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，展开算法设计。本篇所述的简单模拟，指的是问题描述详细地给出了完成某一过程的步骤或规则，程序只需严格按照题意要求模拟过程即可。模拟形式一般有随机模拟和过程模拟，由于随机模拟的效果有不确定因素，不适合在线测试，因此本篇侧重于结果无二义性的过程模拟，通过实例演示了过程模拟的3种基本方法——直叙式模拟、筛选法模拟和构造式模拟。

所谓递归（recursion）指的是子程序在其定义或说明中直接或间接调用自身，是程序调用自身的一种编程技巧。本篇主要讲解了计算递归形式的函数值、按递归算法求问题解和按数据结构形式的递归定义编写程序的基本方法，特别介绍了递归算法的经典应用——回溯法。在第三篇和第四篇中将详述树的遍历规则、图的深度优先搜索的遍历规则，其数据的结构形式就是按照递归定义的。

本篇中涉及二分法、递归、模拟等基础算法。所谓算法就是编程解决实际问题的步骤和方法。Pascal语言之父、结构化程序设计的先驱Niklaus Wirth写过一本非常著名的书——《算法+数据结构=程序》。从书名就可以看出，算法和数据结构有着千丝万缕的联系：算法表述了程序解决问题的行为特性；数据结构表述了程序中数据对象的结构特性；简捷高效的算法很大程度上出于对数据结构的正确选取，而施于数据的逻辑结构和物理结构上的操作也属算法之列。因此掌握数据结构的设计方法是编程解题的基础。

数据结构有三种表示形式：线性表、非线性的树和图。我们将在第二篇、第三篇和第四篇中分别展开这三类数据结构的编程实验。