C语言程序设计——《从问题到程序》资源-CSDN文库

共11个文件

pdf：11个

程序设计

4星 · 超过85%的资源需积分: 35 22 浏览量 2010-08-25 14:11:14 上传评论收藏 4.53MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

从问题到程序.rar （11个子文件）

ch07.pdf 409KB

ch04.pdf 849KB

ch01.pdf 327KB

ch06.pdf 687KB

ch09.pdf 353KB

ch08.pdf 508KB

ch05.pdf 782KB

ch03.pdf 366KB

ch02.pdf 320KB

ch11.pdf 714KB

ch10.pdf 758KB

裘宗燕从问题到程序（2003 年修订），第四章，基本程序设计技术

第四章基本程序设计技术

读者在学习中应已试验了一些程序示例，做了些练习。写程序的过程中确实要处理许多

琐碎细节，但它又是很有趣的工作，是对智力的挑战。为完成一个程序，首先要分析问题、

寻找解决方案，需要聪明才智和想象力，各种相关领域的知识和技术都可能得到应用。要把

设计变成现实，变成可执行的程序，则既需要智力发挥，又需要有条有理的工作，还需要极

端细心。一个小错就可能使程序无法编译或不能正确执行。当然，高度精确性也是现代社会

的特征，写程序的过程能给读者许多有价值的体验。

学习程序设计都需要经历类似的熟悉过程，但并不是说这里的学习就是简单经验积累，

也不意味着程序做多了就一定能做好。多年实践使人认识到程序设计的许多规律性，总结出

许多模式、方法和技术，也进一步研究了许多理论问题。

学习程序设计，一开始就应该注意程序设计中的规律性。正确的好的程序不可能随随便

便写出来，也不应该是修修补补改出来的。只有注意写好小程序，弄明白最基本的道理，才

能进一步写出更大更复杂的程序。这些都是本书各章中特别强调的问题。

在进一步了解 C 语言的其他功能之前，我们应学会把已知的东西应用于实际程序设计，

这就是本章的目的。前面讨论了三种结构化流程模式和相关语言结构。顺序模式最简单，很

容易用复合语句实现。选择模式的最重要问题就是正确描述条件，考虑不同条件下应完成的

动作，用条件语句实现也不困难。学习程序设计初期的主要难点是重复执行模式，它比较复

杂，用循环实现时牵涉到的问题较多，这是本章讨论的重点。此外本章还要讨论基本输入输

出，采用递归的方式编程，并介绍 C 语言的其他控制结构和控制语句。

4.1 循环程序设计

写出写好循环首先要发现计算过程中可能需要（应该用）循环。在分析问题时，应注意

识别计算过程中需要重复执行的类似动作，这常常是重要线索，说明可能需要引进一个循环，

统一描述和处理这些重复性动作。常见如：需要一批可以按统一规律计算的数据；需要反复

从一个结果算出另一结果；需要对一系列类似数据做同样处理等等。这些情况都可看着重复

性计算，如果重复次数多，或次数无法确定，就应考虑用循环结构描述。

从发现重复性动作到建立起一个循环结构，还需考虑和解决许多具体问题。通常包括：

循环中涉及哪些变量？循环开始前应给它们什么初值？循环中这些变量应如何改变？在什

么情况下应该继续（或应该终止）循环？循环终止后如何得到所需结果？如此等等。具体问

题还包括使用语言里的哪种结构实现循环等。

本节将讨论一批程序设计实例，描述的各种典型循环程序设计问题。对于许多实例都采

用了首先分析问题，发掘完成程序的线索，最终完成能解决问题的程序的叙述方式。这样讨

论是为使读者能看到“从问题到程序”的思维过程。对许多例子给出了多个能解决问题的不

同程序，并着重说明其差异或优缺点。这样做是希望读者能理解：程序设计不是教条，即使

对一个典型问题，也没有需要背的标准解答。非极端简单的问题总有许多种解决方法，可以

写出出许多有着或多或少形式的或实质的差异程序。许多程序往往各有长短。当然，能写出

多个程序，并不说明这些程序都有同等价值。实际上，“正确的”程序也常有优劣之分。下

面讨论里也会提出一些看法。

4.1.1 基本循环方式

假设现在要求出从 13 到 315 的所有整数之和。显然的解法是写一个循环，这时需要用

裘宗燕从问题到程序（2003 年修订），第四章，基本程序设计技术

一个变量保存求出的和，计算过程中用它保存部分和。循环中顺序将各个数加上去，直至所

有的数加完了，部分和就变成了完全和。为此实现这一循环，还就需要一个变量保存应加入

的数的轨迹，每次重复时将这个变量加 1。这正好是 for 语句的循环形式。

假定已经定义了名为 sum 总和变量和名为 n 的循环变量。n 的取值应包括 [13, 213] 范

围中所有的整数。一种典型实现方式称为向上循环，即让循环变量 n 从最小值开始逐步增加，

直至达到取值范围的最大值。这样写出的循环具有如下形式：

for (sum = 0, n = 13; n <= 315; ++n)

sum += n;

对于这个问题，同样可以采用向下循环的方式：

for (sum = 0, n = 315; n >= 13; --n)

sum += n;

对于这个具体问题而言，采用向上或者向下循环的效果完全一样。许多其他循环的情况与此

类似，都可以自由选择向上或者向下的方式。在这种情况下，人们一般采用向上循环的方式，

因为这种方式似乎更符合人的习惯。也确实存在一些循环，对它们必须采用某种特定循环方

式，否则就会导致程序错误。今后读者会遇到这样的例子。

完全可以用 while 语句重写上述循环。实际上，while 语句和 for 语句具有同样表

达能力，用 for 循环表述的代码都可等价地翻译为用 while 语句写的代码，反之亦然。

有时我们需要的不是一个范围内的所有整数值，而是具有同等间隔的值。例如，需要求

出 [13, 315] 间每隔 7 的各个整数之和。写出相应数学公式并不难（上例也一样），采用循环

语句写也很简单：

for (sum = 0, n = 13; n <= 315; n += 7)

sum += n;

在写循环时，人们一般不赞成采用浮点数控制循环的次数，尤其是在增量为小数或者包

含小数时。例如，假设我们需要求从 0 到 100，每隔 0.2 的各数的平方和：

double sum, x;

for (sum = 0.0, x = 0.2; x <= 100.0; x += 0.2)

sum += x * x;

因为浮点数运算有误差，我们不能保证这一循环恰好重复了 500 次，因此就不能保证它一定

得到所需结果。这一循环的正确写法是：

int n;

double sum, x;

for (sum = 0.0, n = 1; n <= 500; ++n) {

x = 0.2 * n;

sum += x * x;

}

关于浮点误差的问题，下面还有更详细的讨论。

4.1.2 求出一系列完全平方数

问题：写一个程序，打印出 1 到 200 之间的所有完全平方数，即那些是另一个数的平方

的数。通过分析可以发现，这样一个简单问题也有许多不同解法。

第一种方法

一种最显然的方法是逐个检查 1 到 200 的所有整数，遇到完全平方数时就打印。这一计

算过程中有一系列重复动作（每次检查一个数），可以用循环描述。循环中用一个变量，顺

序取被检查的那些值，从 1 开始每次加 1。这样就可以得到所需循环的基本框架：

for (n = 1; n <= 200; ++n)

if (n 是完全平方数) 打印 n;

这里假设 n 是已有定义的整型变量，循环中它遍历从 1 到 200 的各个值。这种循环特别适合

用 for 语句描述。

上面只是一个程序框架，其中有些部分还不是用程序语言精确描述的，需要在随后的工

裘宗燕从问题到程序（2003 年修订），第四章，基本程序设计技术

作中填充。显然打印语句很容易，剩下的问题就是条件语句中的判断。由于 C 语言没有直

接判断一个数是否为完全平方数的手段，这个问题还需要做进一步分析。

假设被考查的整数是 n，一种可能方式是从 1 开始检查各个整数，看是否有一个数的平

方正好为 n。如果有，n 就是完全平方数；否则 n 就不是完全平方数。这个过程又构成一个

循环（循环里的循环），需要用另一变量（例如 m）记录检查中所用的值。这就又产生了问

题：m 取值从那里开始，什么条件下应当继续（或结束）。显然 m 应从 1 开始取值，而一旦

其平方大于 n 就没有必要继续检查了，因为更大的数不会是 n 的平方根。

这样可以写出内部循环如下：

for (m = 1; m * m <= n; ++m)

if (m * m == n) 打印 n;

循环中至多只有一个值的平方等于 n。如果 n 是完全平方数，这个值就会打印一次，且仅仅

一次。把这些代码组合起来，就可以得到下面的程序：

#include <stdio.h>

main () {

int m, n;

for (n = 1; n <= 200; ++n)

for (m = 1; m * m <= n; ++m)

if (m * m == n)

printf("%d ", n);

printf("\n"); /* 最后换一行 */

}

第二种方法

这里要求打印 1 到 200 间的所有完全平方数，它们一定是从 1 开始的一些整数的平方。

由这个想法可以得到另一种解决方案：用一个循环计数变量 n，从 1 开始逐个打印 n 值的平

方，直到 n 的平方大于 200 为止。最后这句话也就是循环结束条件。按这种想法写出的程

序更简单，只需一层循环。用 for 语句写出的程序主要部分如下：

for (n = 1; n * n <= 200; ++n)

printf("%d ", n * n); /* 注意应当打印什么 */

不难将以它为基础写出一个程序，这件事留给读者完成。

还有一种可能的方法是递推。不难发现，平方数序列具有如下递推关系：

++=

αα

利用这个公式可以写出另一程序，还可以写出只用加法的程序。这些也请读者考虑。

从这个例子可以看到：即使是很简单的问题，也可能有许多不同的求解途径，写出的程

序大相径庭。如果对问题做细致深入的分析，就可能发现许多解决问题的线索。

4.1.3 判断素数（谓词函数）

问题：写一个函数，判断一个整数（参数）是否为素数。

判断只有成立和不成立两种情况，完成判断的函数是一类特殊函数（也称为谓词），它

们的返回值被作为逻辑值使用，通常用来控制程序流程，或放在条件表达式的控制部分。人

们通常令判断函数返回 0 或 1，用 1 表示判断成立（在这里表示是素数），0 表示判断不成立

（不是素数）。这样，要定义的函数的类型特征可以取定为：

int isprime(int)

判断一个数（例如 n）是否素数有许多高级的数学方法，这里只考虑最直接而简单的方

法，就是设法确定它有无真因子。m 整除 n 可以用条件(n%m == 0)描述，如果 m<n 而且

m 不是 1，那它就是真因子了。这样，检查素数的最简单方法就是令变量 m 由 2 开始递增取

裘宗燕从问题到程序（2003 年修订），第四章，基本程序设计技术

值，一个个试除 n。这可以通过一个循环完成。

下一个问题是 m 试除到什么时候结束。显然，试完所有小于 n 的值能保证不会漏掉任

何可能性。稍加分析不难看出，只要试到 m*m>n 就够了，继续试下去已经没有意义（这一

论断的合理性请读者考虑）。有了上述分析，写出下面定义已经很自然了：

int isprime (int n) { /* 判断一个数是否素数 */

int m = 2;

for ( ; m * m <= n; ++m)

if (n % m == 0) return 0; /* 发现因子，不是素数 */

return 1; /* 可能性均考虑过，没有因子，是素数 */

}

发现 n 的一个因子已经可以做出结论，不必继续循环了。代码中的 return 语句导致函数

结束，也使函数体里的循环结束。这是一种从循环中退出的方式。

这个函数定义还有不完善之处，例如，它对 1 将给出“是素数”的判断。对 0 和负数也

会给出不合理结果。解决这些问题并不难，只要在循环前加上特殊情况处理。例如：

if (n <= 1) return 0;

在写一个程序（或一个函数）之前，首先应该仔细分析需要考虑的情况。完成之后还应该仔

细检查，看看是否有什么遗漏。如果事先分析周全，应该能看到这些问题。

4.1.4 艰难旅程（浮点误差）

问题：假定有一只乌龟决心去做环球旅行。出发时它踌躇满志，第一秒四脚飞奔，爬了

1 米。随着体力和毅力的下降，它第二秒钟爬了 1/2 米，第三秒钟爬了 1/3 米，第四秒钟爬

了 1/4 米，如此等等。现在问这只乌龟一小时能爬出多远？爬出 20 米需要多少时间？

显然，要计算的是无穷和式

∑

∞

前面的有限一段之和。由数学知识有

∞

=∞

∑

，也

就是说，只要乌龟坚持爬下去，它不但能完成环球旅行，也能爬到宇宙的尽头。我们想用这

个例子研究一下浮点数的误差问题，并对 float 和 double 类型的情况做些比较。这里先

定义两个采用 float 类型的函数：

float distf (long n) {

long i;

float x = 0.0;

for (i = 1; i <= n; ++i) x += 1/(float)i;

return x;

}

long secondsf (float d) {

long i;

float x = 0.0;

for (i = 1; x < d; ++i) x += 1/(float)i;

return i - 1;

}

其中 distf 计算出乌龟 n 秒爬出的距离，而 secondsf 计算出它爬 d 米所用的秒数。注

意 secondsf 在返回值时减一，因为循环最后的变量更新已经将 i 多加了一次。

现在就很容易写出完成题目的主函数了，其中有如下函数调用：

printf("%ld seconds, %f meters\n", 3600, distf(3600));

printf("%ld seconds, %f meters\n", secondsf(20.0), 20.0);

在作者所用的系统上，程序打印出：

3600 seconds, 8.766049 meters

也就是说，乌龟一小时爬出了 8 米多。但此后程序再也没有输出了，运行了很长时间也不停

止。仔细检查程序没有发现错误，修改主函数放入如下语句：

裘宗燕从问题到程序（2003 年修订），第四章，基本程序设计技术

for (x = 10.0; x <= 20.5; x += 1.0)

printf("%ld seconds, %f meters\n", secondsf(x), x);

程序输出了下面几行：

12367 seconds, 10.000000 meters

33617 seconds, 11.000000 meters

91328 seconds, 12.000000 meters

248695 seconds, 13.000000 meters

662167 seconds, 14.000000 meters

1673859 seconds, 15.000000 meters

乌龟 4 个多小时爬到 10 米远，19 天多才爬到 15 米，而后程序再也没有反应了。这使我们怀

疑问题出在变量的表示范围或者精度方面。我们想到考虑如下的测试函数：

void test_float () {

long i;

float sum = 0.0, sum0 = -1.0;

for (i = 1; sum != sum0; ++i) {

sum0 = sum;

sum += 1 / (float)i;

}

printf ("float: %ld terms at %f\n", i-1, sum);

}

循环的结束条件是变量 sum 的部分和不再变化。在同一系统里，函数很快就输出了一行：

float: 2097152 terms at 15.403683

这就是说，在加入 200 多万项之后，以后所加的数值很小的项已经不再起作用了。由此可见，

我们对乌龟活动情况的模拟受到了数据表示精度和范围的限制。

为了进一步弄清不同数据类型带来的变化，我们采用 double 类型写出同样程序，结

果发现，在 20 亿秒时和数还在增长，当时的输出值是：

double: 2000000000 seconds, 21.993629 meters

也就是说，经过大约 63 年半，乌龟爬出了 21 米。在大约 2 亿 5 千万秒，也就是大约 8 年的

时候爬过了 20 米，这是题目第二部分的答案。由于我们所用系统中的 long 类型用 32 位二

进制表示，在其范围内无法找到采用 double 类型的增长结束点。可以保证的一点是，这

个结束点一定出现在比采用 float 类型大得多的地方。

那么，在精度允许的范围内，采用 float 和 double 类型会产生不同结果吗？我们又

写出下面的比较代码：

int i;

float sumf = 0.0;

double sumd = 0.0;

for (i = 1; i <= 2000000; ++i) {

sumf += 1 / (float)i;

sumd += 1 / (double)i;

}

printf ("float: %d terms at %14.10f\n", i-1, sumf);

printf ("double: %d terms at %14.10f\n", i-1, sumd);

得到的结果确实不同：

float: 2000000 terms at 15.3110322952

double: 2000000 terms at 15.0858736534

精确到小数点后 10 位的正确值应该是：15.0858736534。到这时为止，采用 double 类型的

计算结果在 10 位精度内还没有产生误差，而用 float 计算已经产生了明显的误差，只剩下

两位正确数字了。通过这些试验，我们可以看到多次浮点数运算确实可能带来明显的误差。

在解决实际问题时，运算的次数可能远远多于这个小试验，累计误差的情况更复杂。由此可

以看到选择适当浮点数的需要。人们建议，如果没有特殊原因，就应选用 double 类型。

float 表示范围和精度不能满足许多常规浮点运算的需要，而 long double 类型有可能

影响程序效率。它们应该只用于特殊场合。

上面的试验展示了浮点数运算的误差问题。在某些特殊情况下，浮点数运算的误差积累

评论收藏

内容反馈

l2296366867

2013-11-05

还可以吧，深入学习可以看！

urhero

粉丝: 28
资源: 94

C语言程序设计——《从问题到程序》

从问题到程序（c语言）

从问题到程序

从问题到程序-程序设计与C语言引论

从问题到程序-程序设计和C语言.pdf

原版从问题到程序设计与C语言引论.

从问题到程序.pdf

从问题到程序——程序设计与C语言引论_裘宗燕 PDF清晰版

程序设计基础答案

从问题到程序——程序设计与C语言引论_裘宗燕

c语言程序设计——谭浩强

C语言程序设计——学籍管理系统.zip

C语言程序设计——学生信息管理系统.doc

C语言程序设计——答案.pdf

C++基础教程——从问题分析到程序设计（第2版）.rar

裘宗燕. 从问题到程序

裘宗燕--从问题到程序电子版

程序设计基础第二版 吴文虎

C语言程序设计——备忘录.txt

C语言程序设计——职工管理系统（链表）.zip

C语言程序设计——开机密码

C语言程序设计——学生成绩管理系统（链表）.zip

C语言程序设计——学生成绩管理系统（非链表）.zip

C语言程序设计——答案[文].pdf

C语言程序设计——循环结构PPT学习教案.pptx

C语言程序设计——职工档案管理系统

最新资源

程序设计基础第二版吴文虎