22“自顶向下,逐步求精”的程序设计方法 在上面介绍的顺序、选择和循环三种基本程序结构中的程序模块又可以是由这三种基本 程序结构抽象而成的新程序模块,因此可以通过组合、嵌套这些基本程序结构来构造更复杂 的程序。已经证明,一个合理的程序,总可以化为顺序、选择和循环这三种基本程序结构的 某种组合。 结构化程序设计支持“自顶向下,逐步求精”的程序设计方法。自顶向下的程序设计方 法从问题本身开始,经过逐步求精,将解决问题的步骤分解为由基本程序结构模块组成的结 构化程序框图,据此就很容易编写出结构良好、易于调试的程序来。 「例2-1“验证”哥德巴赫猜想。哥德巴赫猜想是数论中的一个著名难题,是由法国数学 爱好者克里斯蒂安·德巴赫于1742年在给著名数学家欧拉的一封信中提出的。“哥德巴赫 猜想”可以表述为:任何一个大于等于4的偶数均可以表示为两个素数之和。尽管这个问题 看来如此简明清晰,但二百多年来虽有无数数学家为其呕心沥血、绞尽脑汁,却始终无人 能够证明或者证伪这个猜想2。 我们将这个问题作为一个练习,在有限的范围内验证哥德巴赫猜想:编写一段程序,验 证大于4,小于某一上限M的所有偶数是否都能被分解为两个素数之和。如果一但发现某个 偶数不能被分解为两个素数之和,则证实了哥德巴赫猜想是错误的(果真如此,则可称是数 学史上的一大发现!):否则证实哥德巴赫猜想在所给的范围内成立 算法:首先画出代表解决该问题的程序模块,见图2-7 然后根据题意对图27中的程序模块进行初步 分解,其思路如下:逐个生成由4到M之间的所有 偶数,一一验证其是否能够被分解为两个素数之和。 验证哥德巴赫猜想 具体方法是声明一个变量x,令其初值等于4,然后 每次在x上加2,以产生各偶数并验证x是否可以被 分解为两个素数之和直到x不小于M为止。显然,图2-7验证哥德巴赫猜想 这是一个循环结构,其分解图见图2-8。 在图2-8中的初步分解中用粗线框表示了基本程序结构的嵌套组合情况。从图中可以 看出,最内层的粗线框中是两个顺序排列的程序模块,它们一起构成了循环结构的内嵌程序 模块。循环模块又和最前面的语句模块构成了顺序结构 1如果一个程序满足下列条件,就是一个合理的程序 1.整个程序只有一个入口和一个出口 2.从程序的入口到所有模块都至少有一条路径可达。 这些条件是非常容易满足的。通过合并那些不止一个的入口和出口,以及删除那些不可到达的模块(这些模 块对程序的功能没有任何影响,任何程序都可以化为一个合理的程序。 260-70年代,我国数学家陈景润证明了一个条件略宽的定理,即“任何一个大于4的偶数,均可以分解为 一个素数与两个素数的积之和”,从而向最终解决哥德巴赫猜想又迈进了一步第 2 单元 控制结构 - 20 - 2.2 “自顶向下, 逐步求精”的程序设计方法 在上面介绍的顺序、选择和循环三种基本程序结构中的程序模块又可以是由这三种基本 程序结构抽象而成的新程序模块, 因此可以通过组合、嵌套这些基本程序结构来构造更复杂 的程序。已经证明, 一个合理的程序1 , 总可以化为顺序、选择和循环这三种基本程序结构的 某种组合。 结构化程序设计支持“自顶向下, 逐步求精”的程序设计方法。自顶向下的程序设计方 法从问题本身开始,经过逐步求精,将解决问题的步骤分解为由基本程序结构模块组成的结 构化程序框图,据此就很容易编写出结构良好、易于调试的程序来。 [例 2-1]“验证”哥德巴赫猜想。哥德巴赫猜想是数论中的一个著名难题, 是由法国数学 爱好者克里斯蒂安·哥德巴赫于 1742 年在给著名数学家欧拉的一封信中提出的。“哥德巴赫 猜想”可以表述为:任何一个大于等于 4 的偶数均可以表示为两个素数之和。尽管这个问题 看来如此简明清晰, 但二百多年来, 虽有无数数学家为其呕心沥血、绞尽脑汁, 却始终无人 能够证明或者证伪这个猜想2。 我们将这个问题作为一个练习, 在有限的范围内验证哥德巴赫猜想:编写一段程序, 验 证大于 4, 小于某一上限 M 的所有偶数是否都能被分解为两个素数之和。如果一但发现某个 偶数不能被分解为两个素数之和, 则证实了哥德巴赫猜想是错误的 (果真如此, 则可称是数 学史上的一大发现!);否则证实哥德巴赫猜想在所给的范围内成立。 算 法: 首先画出代表解决该问题的程序模块, 见图 2-7。 然后根据题意对图 2-7 中的程序模块进行初步 分解, 其思路如下:逐个生成由 4 到 M 之间的所有 偶数,一一验证其是否能够被分解为两个素数之和。 具体方法是声明一个变量 x, 令其初值等于 4, 然后 每次在 x 上加 2, 以产生各偶数并验证 x 是否可以被 分解为两个素数之和, 直到 x 不小于 M 为止。显然, 这是一个循环结构, 其分解图见图 2-8。 在图 2-8 中的初步分解中用粗线框表示了基本程序结构的嵌套组合情况。 从图中可以 看出, 最内层的粗线框中是两个顺序排列的程序模块, 它们一起构成了循环结构的内嵌程序 模块。循环模块又和最前面的语句模块构成了顺序结构。 1 如果一个程序满足下列条件, 就是一个合理的程序: 1. 整个程序只有一个入口和一个出口; 2. 从程序的入口到所有模块都至少有一条路径可达。 这些条件是非常容易满足的。通过合并那些不止一个的入口和出口, 以及删除那些不可到达的模块(这些模 块对程序的功能没有任何影响), 任何程序都可以化为一个合理的程序。 2 60-70 年代, 我国数学家陈景润证明了一个条件略宽的定理, 即“任何一个大于 4 的偶数, 均可以分解为 一个素数与两个素数的积之和”, 从而向最终解决哥德巴赫猜想又迈进了一步。 验证哥德巴赫猜想 图2-7验证哥德巴赫猜想