《从问题到程序》第5章习题的讨论

（《从问题到程序》，裘宗燕著，机械工业出版社，2005年9月）

习题题目和讨论

3 一对实数可以表示平面上的一个点的坐标。一系列的实数对，当这些数对里的第一个数为递增时，把它们表示的平面点连接起来，可以得到一条与 x轴同方向的折线。由一条这种折线、该折线两端引向x轴的垂线、以及x轴本身，能够形成一个封闭区域的边界。请写一个程序，它接受一系列由标准输入得到的数对，最后计算出这些数对所确定的区域的面积。规定用一对零（两个0.0）表示输入结束。这里假定输入的数对中的x值总是递增的，y的值均不为负。进一步说，如果y值可以为负，你能修改自己的程序，使它在这种情况下也能计算正确吗？
提示和讨论：本题与第4章练习的21题类似，请参考那里的提示。

4 请定义函数判断一个点与坐标原点的距离是否小于1，是否在单位圆内。借助这一函数写一个通过蒙特卡罗方法计算圆周率值的程序：每次计算随机生成两个0与1之间的实数（利用标准库的随机数生成函数产生这种实数），看这两个值形成的点是否在单位圆内。生成一系列随机点，统计位于单位圆内的点数与总点数，看它们之比的4倍是否趋向值。请生成100、200、…、1000个数据点做试验。
提示和讨论：
考虑定义一个函数 gpair，其中生成一对 [0,1] 区间的随机数，而后计算它是否在单位圆内部。在内部时返回 1，不在时返回 0。
基本程序是一个计数循环，其中统计 gpair 返回 1 的次数。

7 请设计一些程序，设法检查5.4.5节定义的random函数的随机性是否令人满意。
提示和讨论：举几个例子，基本工作都是反复生成一系列随机数，做一些统计：

将生成的数取模2，统计偶数和奇数的个数。
取个中间值，统计大于它和小于它的随机数个数
还可以想出许多其他方法，请自己考虑。

10 牛顿迭代法和二分法求根。
提示和讨论：
定义牛顿迭代法的求根函数，可以用两个参数。也可以考虑用差分代替微分。

11-14 都是处理输入文件和统计的程序。请参考本章的上一章正文的例子，以及上一章最后的程序模式。14题是第4章练习24的升级版。

19 HTML网页中有一部分是真正的网页信息内容，另外有大量的形式是由一对 "<" 和 ">" 括起的 HTML 标注。

请写一个程序，它能删除由输入得到的HTML网页里的所有标注，只留下基本信息。
请设法留下原页面里的段落信息，使得到的结果更容易读。

提示和讨论：
为完成这个作业，你需要去了解一下 HTML 文档的结构。

这里的基本工作仍然是从一个文件读入，把结果写入另一个文件。可以用 getchar 和 putchar 作为基本输入输出手段，基本的程序框架就是一个标准的输入循环
下面的问题是碰到 HTML 标注时的处理。

本页由裘宗燕建立和维护。这里的材料可自由用于个人学习和教学活动。其他使用必须得到裘宗燕书面许可

EMAIL：qzy@math.pku.edu.cn

通讯地址：100871，北京大学数学学院信息科学系

习题	题目和讨论
3	一对实数可以表示平面上的一个点的坐标。一系列的实数对，当这些数对里的第一个数为递增时，把它们表示的平面点连接起来，可以得到一条与 x轴同方向的折线。由一条这种折线、该折线两端引向x轴的垂线、以及x轴本身，能够形成一个封闭区域的边界。请写一个程序，它接受一系列由标准输入得到的数对，最后计算出这些数对所确定的区域的面积。规定用一对零（两个0.0）表示输入结束。这里假定输入的数对中的x值总是递增的，y的值均不为负。进一步说，如果y值可以为负，你能修改自己的程序，使它在这种情况下也能计算正确吗？提示和讨论：本题与第4章练习的21题类似，请参考那里的提示。
4	请定义函数判断一个点与坐标原点的距离是否小于1，是否在单位圆内。借助这一函数写一个通过蒙特卡罗方法计算圆周率值的程序：每次计算随机生成两个0与1之间的实数（利用标准库的随机数生成函数产生这种实数），看这两个值形成的点是否在单位圆内。生成一系列随机点，统计位于单位圆内的点数与总点数，看它们之比的4倍是否趋向值。请生成100、200、…、1000个数据点做试验。提示和讨论：考虑定义一个函数 gpair，其中生成一对 [0,1] 区间的随机数，而后计算它是否在单位圆内部。在内部时返回 1，不在时返回 0。基本程序是一个计数循环，其中统计 gpair 返回 1 的次数。
7	请设计一些程序，设法检查5.4.5节定义的random函数的随机性是否令人满意。提示和讨论：举几个例子，基本工作都是反复生成一系列随机数，做一些统计：将生成的数取模2，统计偶数和奇数的个数。取个中间值，统计大于它和小于它的随机数个数还可以想出许多其他方法，请自己考虑。
10	牛顿迭代法和二分法求根。提示和讨论：定义牛顿迭代法的求根函数，可以用两个参数。也可以考虑用差分代替微分。
11-14	都是处理输入文件和统计的程序。请参考本章的上一章正文的例子，以及上一章最后的程序模式。14题是第4章练习24的升级版。
19	HTML网页中有一部分是真正的网页信息内容，另外有大量的形式是由一对 "<" 和 ">" 括起的 HTML 标注。请写一个程序，它能删除由输入得到的HTML网页里的所有标注，只留下基本信息。请设法留下原页面里的段落信息，使得到的结果更容易读。提示和讨论：为完成这个作业，你需要去了解一下 HTML 文档的结构。这里的基本工作仍然是从一个文件读入，把结果写入另一个文件。可以用 getchar 和 putchar 作为基本输入输出手段，基本的程序框架就是一个标准的输入循环下面的问题是碰到 HTML 标注时的处理。