自顶向下
自顶向下是指对设计的系统要有一个全面 的理解，从问题的全局入手，把一个复杂 问题分解成若干个相互独立的子问题，然 后对每个子问题再作进一步的分解，如此 重复，直到每个问题都容易解决为止。
逐步求精
逐步求精是指程序设计的过程是一个渐进 的过程，先把一个子问题用一个程序模块 来描述，再把每个模块的功能逐步分解细 化为一系列的具体步骤，以致能用某种程 序设计语言的基本控制语句来实现。逐步 求精总是和自顶向下结合使用，一般把逐 步求精看作自顶向下设计的具体体现。
例1.3 求两个正整数m和n的最大公约数。
m,n的最大公约数即是所有能同时除尽 m,n的数中的最大数。求两个正整数的最大 公约数常用展转相除法。由于m和n是两个 正整数，因此存在q,r，使m=n×q+r (q≥0,r≥0,r<n)。如果r=0，则n即是m和n的最 大公约数。否则，可以证明n和r的最大公 约数就是m和n的最大公约数。用同样的方 法求n和r的最大公约数。如此继续下去， 直到余数为0。
n
x →max
i+1 →i
输出max
1.3 程序设计方法
1.3.1 结构化程序设计
随着计算机技术的不断发展，人们对程序设 计方法的研究也在不断深入。早期程序设计的好 坏常以运行速度快、占用内存少为主要标准，然 而在计算机的运算速度大大提高，存储容量不断 扩大的情况下，程序具有良好的结构成为第一要 求，一个结构良好的程序虽然在效率上不一定最 好，但结构清晰，易于阅读和理解，便于验证其 正确性。这对传统的程序设计方法提出了严重的 挑战，从而促使了结构化程序设计方法的产生。
例1.4 用一般流程图来描述例1.1的算法。
输入a、b
y
x a2 b2
y ab a b
a<b?
n
x a2 b2 y 4
a b
u x y x y
输出u
例 1.2 的 算 法 。
输入max 1→i
i≤9? y
输入x
x>max? y
x →max
i+1→i
n n输出max源自2. 程序的三种基本结构两数最大公约数为 G，则一级算法如 图所示。
M从2变化到333
N=667-M
求G
求L
L=120*G？
Y
N
输出M、N
求最大公约数及最小公倍数
对参数A和B(A<B)，使K从A开始变化，找 到一个能同时整除A与B的K，K就是最大 公约数。而求最小公倍数是：若干个B之和， 若能被A整除，则该和便是A和B的最小公 倍数。
具体要经过以下四个基本步骤：
(1)分析问题，确定数学模型或方法。 (2)设计算法，画出流程图。 (3)选择编程工具，编写程序。 (4)调试程序，分析输出结果。
1.2 算法及其描述
1.2.1 算法的概念
在日常生活中，我们做任何一件事情，都是 按照一定规则，一步一步地进行的，这些解决问 题的方法和步骤称为算法。比如工厂生产一部机 器，先把零件按一道道工序进行加工，然后，把 各种零件按一定法则组装起来，生产机器的工艺 流程就是算法。同样，我们要编写解决问题的程 序，首先应设计算法，任何一个程序都依赖于特 定的算法，有了算法，再来编写程序是很容易的 事情。
结构化程序设计
自20世纪60年代由荷兰学者E.W.Dijkstra提出 以来，经受了实践的检验，同时也在实践中不断 发展和完善，成为软件开发的重要方法，在程序 设计方法学中已占有十分重要的位置。用这种方 法设计的程序结构清晰，易于阅读和理解，便于 调试和维护。
结构化程序设计采用自顶向下、逐步求精和 模块化的分析方法。
例1.1
求
u xy x y
其中
a 2 b2
x
a
2
b2
ab ab
a b
y
a
4
b
a b
ab ab
这一题的算法并不难，可写成：
(1)从键盘输入a、b的值。
(2)如果a<b，则
， x a2 b2 , y a b ab
否则 。 x a2 b2 , y 4 ab
(3)计算u的值。
(4)输出u的值。
模块化
子模块1
主控模块
子模块2
…
…
子模块n
子模块21
子模块22
…
子模块2m
结构化程序设计的过程就是…将问题求解由抽
象逐步具体化的过程。这种方法符合人们解决复
杂问题的普遍规律，可以显著提高程序设计的质
量和效率。
例1.6 计算 s=1+(1+2!)+(1+2!+3!)+…+(1+2!+…+10!)
这是求若干项之和的问题
1.1 程序与程序设计
计算机解题的“程序”是用计算机能识 别的语言所描述的解决实际问题的方法和 步骤。计算机能直接识别的语言是机器语 言，但机器语言用二进制代码表示机器指 令，且机器指令跟具体的计算机结构有关， 程序直观性差、通用性不强。所以初学者 一般都学习利用一种高级语言来编写程序。 FORTRAN语言便是在科学计算领域应用十 分广泛的一种高级语言。
S=0 I从1~10
求F S=S+F 输出S
F=0 J从1~ I
求F1 F=F+F1
F1=1 K从1~J F1=F1*K
例1.7 两个自然数之和是667，且它们的最 小公倍数与最大公约数之比是120:1，例如 115和552，求这样的自然数。
设两个自然数分别 为M和N=667-M (2<=M<=333)，两 数最小公倍数为L，
K从A变化到1
A和B能同 时被K整除？
Y
N
返回K值
K=B
当K不能被A整除时
K=K+B 返回K值
例1.8 验证哥德巴赫猜想：任何大于2的偶数 都是两个素数之和。
给出每一个偶数N，验证能否表示成两个素数之和， 如果不能，输出No，否则继续验证下一个偶数N。
接下来的的问题是如何把N分解为N1和N2(N=N1+N2) 以及如何判断N1和N2是素数。
(4)结构中无死循环。 结构化定理表明，任何一个复杂问题的程序，
都可以用以上三种基本结构组成。具有单入口单 出口性质的基本结构之间形成顺序执行关系，使 不同基本结构之间的接口关系简单，相互依赖性 少，从而呈现出清晰的结构。
3. N-S图
由于传统流程图的缺点，1973年美国学者 I.Nassi和B.Shneiderman提出了一种新的流程图工 具─N-S图。N-S图以三种基本结构作为构成算法 的基本元素，每一种基本结构用一个矩形框来表 示，而且取消了流程线，各基本结构之间保持顺 序执行关系。N-S图可以保证程序具有良好的结
构，所以N-S图又叫做结构化流程图。
S1
P
当P满足时
S2
YN
S3
S1 S2
S
例1.5 用N-S图来描述例1.1的算法。
输入a、b
Y
a<b?
N
x a2 b2
x a2 b2
y ab a b
y 4 ab
u x y x y
输出u
例1.2的算法。
输入max 1→i
当i≤9时 输入x
x>max?
y
(3) 有效性。算法中的每一步操作必须是可执行 的。
(4) 要有数据输入。算法中操作的对象是数据， 因此应提供有关数据。
(5) 要有结果输出。算法的目的是用来解决一个 给定的问题，因此应提供输出结果，否则算法 就2没有实际意义。
1.2.2 算法的描述
算法的描述有许多方法，常用的有：自 然语言、一般流程图、N－S图等。前面例 1.1~例1.3的算法是用自然语言──汉语描述 的，其优点是通俗易懂，但它不太直观， 描述不够简洁，且容易产生二义性。在实 际应用中常用流程图表示算法。
1966年Bohra和Jacopini提出了组成结构化 算法的三种基本结构，即顺序结构、选择 结构和循环结构。
顺序结构
顺序结构是最简单的一种基本结构，依次 顺序执行不同的程序块。
S1
S2
S3
选择结构
Y
N
P
选择结构根据条件
满足或不满足而去
S1
S2
执行不同的程序块。
当条件P满足时执 行A程序块，否则 执行B程序块。
循环结构
循环结构是指重复执行某 些操作，重复执行的部分称 为循环体。判断条件是否满 足，当条件P满足时反复执 行A程序块，每执行一次测 试一次P，直到P不满足为止， 跳出循环体执行它下面的基 本结构。
N P
Y S
三种基本程序结构的共同特点：
(1)只有一个入口。 (2)只有一个出口。 (3)结构中无死语句，即结构内的每一部分都有机 会被执行。
判断M是否素数的算法
根据素数的定义来判断。素数是大于1，且除了1和它本 身以外，不能被其他任何整数所整除的整数。为了判断 整数M是否为素数，一个最简单的办法用2、3、4、5、...、 M-1这些数逐个去除M，看能否除尽，如果全都除不尽， 则M是素数，否则，只要其中一个数能除尽，则M不是素 数。当M较大时，用这种方法，除的次数太多，可以有许 多改进办法，以减少除的次数，提高运行效率。其中的 一种是：用2、3、4、…、 M 去除，如果都除不尽，则M 是素数，这是因为如果小于等于 M 的数都不能除尽M， 则大于 M 的数也不能除尽M。用反证法证明。设有大 于 M 的数J能除尽M，则它的商K必小于 M ，且K能除 尽M(商为J)。这与原命题矛盾，假设不成立。
把N分解为N1和N2的方法很多，一种方法是，N1从2 变化到N/2，且N2=N-N1。为了判断N1和N2是否素数， 可以分别引入逻辑变量L1和L2，N1是素数时，L1为 真，否则为假，N2是素数时，L2为真，否则为假。二 级算法如图1.13(b)所示，其中判断N1或N2是否素数可 采用子程序技术。