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

(《从问题到程序》,裘宗燕著,机械工业出版社,2005年9月)


本章的练习主要是写各种循环,包括逻辑控制的循环,计数循环,实现一系列输入的循环等等。后面一些练习是为了帮助读者学习正确写出带有输入的程序。本章最后给出的程序模式都很有用,请注意借鉴。

4.1节讨论了写循环的技术。对具体问题还需注意循环中数据项的计算。有时可能需要写两重或多重循环。这时的思考方式是从全局到局部,先规划好外层循环的过程,把内层循环看作一个抽象操作。外层循环写好后,再考虑抽象操作的实现,有时需要用循环实现,自然就形成了两重或者多重循环。有些题目中的循环项可以递推,利用这一关系可以把两重循环简化为一重循环,提高计算的效率。这种技术也很值得注意。

在学习写循环程序的同时仍要注意函数定义。下面一些题目的提示中提出了相关的建议。在学习基本程序设计的阶段,最重要的问题就是掌握定义函数的技术,学会在不同的抽象层次上考虑如何写程序,如何把复杂的程序工作分解为若干较为简单的工作,通过定义和调用函数完成整个程序。

习题 题目和讨论
4 写函数计算 1! + 2! + ... + k!。用主函数试验函数对一系列k值计算出的结果。你写出的函数对1到10计算结果都正确吗?如果出现错误,弄清楚是什么原因。这个程序能对k = 30得到正确结果吗?(另外,你能只用一重循环完成函数的定义吗?)

提示和讨论:

  • 首先确定函数的参数类型和返回值类型,并为函数取一个适当的名字,写出函数的头部
  • 用一个循环做累加,考虑循环里需要用几个变量,其初值如何确定
  • 可以考虑把阶乘定义为一个辅助函数(可直接用书上的定义,由此也可看到函数的作用),也可以用一个内层循环求阶乘
  • 请检查一下自己所用的C语言系统,看看本题计算中的变量应该用什么类型,注意其表示范围
  • 在按朴素的想法写好程序之后,考虑题目括号提出的问题。请想一想求和过程中的项之间的递推关系,想想这样借助于递推减少计算量,得到更高效的实现
8
  1. 定义函数:void prt_factors(int),对于正的整数实参,这个函数输出其所有的因子。
  2. 定义函数:void prt_pfactors(int),它对正整数实际参数,输出其所有的素因子(多重因子重复输出);对于负参数,首先输出-1,然后输出所有因子。
提示和讨论:
  • m是n的因子,也就是m能整除n。在C语言里可以用条件 n % m == 0 表示
  • 要求输出所有因子,最显然的办法是就是一个个地试
  • 要输出所有素因子,你需要判断一个整数是否素数(书上有完成此事的函数,当然应该用它)
  • 要输出所有素因子(多重因子多次输出),就需要在找到一个个素因子后,从原来的数里除掉它们。这一工作也需要通过循环完成。
10下面序列收敛很快:

请写一个程序,根据这个序列计算 π 的近似值。而后做与上一题类似的试验。

提示和讨论:
最直接的方法是用两重循环计算 π/6,外层循环求和,内循环计算一个个的项。最后将得到的结构乘以 6,得到 π 的值。

如果仔细观察,可以发现从第2项开始的各项可以递推计算:

  • 用一个变量表示项最后的 (1/2) 的指数,如用 k,其初始值取 3,每次循环加 2
  • 用一个 double 类型的变量 t 表示项的基本部分,其初始值取 (1/2) 的 4 次方,每次循环将其值更新为 t * (k-2)/(k-1) / 4
  • 当前项的值是 t / k
  • 根据这套想法,用一重循环就可以完成计算。
在计算中要特别注意整数除法,保证计算都是在 double 类型中进行的。
13 考虑不用函数(例如isprime)直接写出对6~200的偶数验证哥德巴赫猜想的程序(利用循环、条件、break语句等,不使用goto语句)。将这样写出的程序与用定义函数的方式写出的程序比较。例如考察两个函数的行数、字节数,其中各种控制结构的嵌套深度,控制结构使用的个数等。

讨论:这个题目就是为了帮助学生体会函数定义的重要性。

17 对一个整数,如果其所有因子(包括因子1在内)之和正好等于这个数,那么就称它为"完全数"。因子之和小于自身的数称为"亏数";因子之和大于自身的数称为"盈数"。写一个函数,当其参数是亏数时返回负值,是完全数时返回0,是盈数时返回正值。利用这个函数求出1000以内的所有完全数(实际上只有1、6、28、496)。

为这个程序计时:从100开始每隔100做一次计算,写一个循环,输出各次计算花的时间。再从1000开始,每隔1000做一次计算直到10000为止,输出对程序执行计时的值。利用所定义的函数对一段区间的整数做一个分类,输出其中各个数所属的类。

提示和讨论:

  • 请考虑定义一个函数,对于整数n,它从某个整数m开始找出下一个能整除n的整数
  • 请再考虑一个函数,它判断一个数是“亏数”、“完全数”还是“盈数”,在这三种情况下分别返回-1,0和+1。
  • 有了这两个函数,题目要求的函数就很容易完成了。
  • 写一个主程序试验你写出的函数。而后再考虑问题的第二部分,修改你做试验的主程序,调用你定义的函数完成所需工作。
21 假设程序由输入得到的一系列正实数是一条折线在 x 等于 0,1,2,… 的对应值(数据的数目事先并未确定),请求出这一折线与 x 轴之间区域的面积。

提示和讨论:

写一个循环取得一串输入的数。自己规定一种判断输入结束的方法,例如用文件结束符,或者用输入负数表示结束,程序里检查是负数就结束循环。最后输出总和的面积。

注意:要求出由先后两个值界定的区域的面积,必须用一个变量(如 x)接受输入,用另一个辅助变量(如 y)保存前一次输入的数。每次计算完一块面积并加入总和后,将新输入的数存入辅助变量 y 保存起来。

23 改造本章正文中讨论的计算器程序:
  1. 原程序不能正确处理数值与运算符之间的空格等空白字符。如果输入 2 + 3,程序会认为是输入错误。请设法修改这个程序,使之在数值、加号之间出现任意个空格时都能正确计算。
  2. 增加计算一行后的处理,使出现在正确表达式之后的任意字符序列都不会影响下一表达式的计算(抛弃正确表达式之后的字符)。
  3. 修改程序,使之不仅能处理加法,还能处理其他算术运算符(提示:记录运算符,用if或者switch判断、计算和输出)。

提示和讨论:

  1. 一般方法可能比较麻烦。我们可利用 scanf() 的功能。当 scanf 处理到格式描述串里的空格时,它会跳过实际读入中遇到的(所有)空白字符,从空白之后继续匹配。 举个例子,如果写 scanf(" %c", &x),scanf 就会跳过输入中的空格,读入后面第一个非空白字符赋给变量 x。除 %c 之外的转换描述都将自动跳过空白字符,因此这里也可以用格式串 "%1s"。
  2. 完成第二项工作,只需要在完成一个表达式的计算之后,读入并丢掉直至换行符的所有东西。下面程序片段可以完成这件事:
    while ((c = getchar()) != EOF) if (c == '\n') break;
  3. 参考上面题目的提示。记录运算符(是一个字符)和两个运算数,写出一系列判断,根据运算符确定应该做什么。
24 仿照本章正文中的单词统计程序,写一个统计C程序里标识符个数的程序。在程序里可以利用标准库提供的字符分类函数:
int isalpha(int c) 当c是字母的编码时,返回非0值;
int isdigit(int c) 当c是数字的编码时,返回非0值。

使用这两个函数时,应在程序文件前部写 #include

提示和讨论:

  • 注意 C 语言有关标识符的形式的规定:字母开头的字母数字串,下划线看作字母。先根据这一规定画出一个状态转换图,弄清什么情况下标识符开始,什么情况下结束。
  • 根据上述转换图写一个函数 nextid,它不断读入字符,找到下一个标识符并将它读完。在能找到标识符的情况下返回 1,如果找不到就返回 0。
  • 完整的程序就是不断调用 nextid 并记录调用次数。直至函数返回 0 时输出计数值。

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


EMAIL:qzy@math.pku.edu.cn
通讯地址:100871,北京大学数学学院信息科学系