程序的灵魂
—— 算法第二章程序（广义）：
如：某一个会议的程序
宣布全议开始；
奏国歌 ；
校长讲话 ；
宣布获奖者名单；
颁奖；
获奖代表讲话；
宣布会议结束；
再如：做某个菜的程序
洗莱 ；
准备配料 ；
加热锅 ；
锅热后加油 ；
做菜的程序 ；
油热至八成，放入葱、姜、蒜和调料略炒后，加入菜煸炒 ；
加入些许水 ；
菜八成熟时，加入酱油、味精 ；
出锅，并装盘 ；
程序：
用于描述完成某项功能所涉及的对象 和 动作 规则 。
国歌、首长、名单、代表、
话、奖以及菜、锅、油、
水、酱油、味精等奏、颁、讲、宣布、放菜、出锅 动作的先后顺序以及它们能作用的对象，
要遵守一定的规则。
计算机程序：
用于描述计算机完成某项功能所涉及的对象 和 动作 规则 。
数据结构与算法在程序设计的初期 要把精力集中在问题求解的思路上,暂不考虑程序描述的细节。
组织求解对象
制定求解过程的操作步骤和规则数据结构算法数据结构：（ data structure）
描述了问题涉及对象间的联系和组织结构。
指定数据的类型和数据的组织形式。
算法：（ algorithm）
描述了求解问题的步骤或规则。
著名的计算机科学家沃思提出：
数据结构 + 算法 = 程序程序设计的关键是构造程序的数据结构并 描述问题所需要的、施加在这些数据结构上的算法。
2.1算法的概念为解决一个问题而采取的方法和步骤。
原则：
1,保证正确
2,考虑质量例一：求 1× 2× 3× 4× 5的值最原始的方法：
1,1× 2 →p
2,p× 3 →p
3,p× 4 →p
4,p× 5 →p
正确！
But 繁琐！
且不具有通用性！
改进一下！
我发出简单的循环命令，
它重复作同样的事情，
数百成千次，
却只在一瞬间，
有了结果！
1,P?1
2.ｉ? 2
3,P? P × i
4.ｉ?ｉ＋１
5.若ｉ ≤ ５则重复 3,4,5各步 ;否则计算结束。最后的 P值就是 5！。
6.输出ｓ
本算法可推广到求 N!
计算机的拿手好戏：
存储容量大
运算速度快 循环 ★★★
设计具有通用性的循环算法！
闰年的条件：
1.能被 4整除，但不能被 100整除。
2.能被 400整除。 整数
4
例二：判断某一年是否为闰年
1.输入年份 y
2.若 y能被 400整除，输出 y“是闰年,。
3.否则，
若能被 4整除，但不能被 100整除，
输出 y“是闰年,。
4,否则，输出 y“不是闰年,。
100400
例三：判断一个数是否为素数素数：
除了 1和该数本身之外，不能被其它整数整除
1,输入 n
2,i=2
3,n被 i除，得余数 r
4,如果 r=0,打印,n不是素数,,算法结束。
5,i+1=>i
6,如果 i≤n -1，重复 3,4,5步，
否则，打印,n是素数,,算法结束。
改进算法效率
ni?
例四：求正整数 n,m的最大公约数根据若两数能分别被 q整除，则其差也定能被 q整除。
输入 n,m的值
1.若 n>m,则 n? n-m
2.若 m>n,则 m? m-n
3.若 n=m,则计算结束,输出 n。否则,重复
1,2,3各步。
动动脑筋，
改进一下算法！
2.2.1 算法的表示方法
1,用自然语言表示
2,用流程图表示
3,N-S图
4,用伪代码表示算法
2.2 算法的表示及特性
(1)流程图起止框输入输出框判断框处理框流程线连接点开始输入 a,b
a>b
max=a max=b
输出 max
结束求两数最大值的流程图开始
0→s
1→i
s+a→s
i+1→i
i≤5是否结束输入第 i个数给 a
打印 s
输入 5个数求和的流程图三种基本流程结构顺序结构
A
B
P
A B
不成立成立选择结构循环结构
P
不成立
A
成立 P成立
A
不成立当型 (while)循环结构 直到型 (until)循环结构三种基本程序结构：
顺序结构、选择结构、循环结构已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。
由基本结构所构成的算法属于“结构化”算法。
(2)N-S图顺序结构 A
B
成立
A B
P
不成立选择结构循环结构 当 P成立
A
当型 (while)循环结构 直到型 (until)循环结构直到 P成立
A
0→s
1→i
输入第 i个数给 a
s+a→s
i+1→i
直到 i>5为止打印 s的值输入 5个数求和的流程图
有穷性,有限的操作步骤，
在合理的时间内完成。
确定性,每一步必须是确定的，
不能“模棱两可”。
有效性,每一步应当有效执行，
并产生有效和确定的结果。
有零个或多个输入
有一个或多个输出
2.2.2 算法的特性结构化程序设计荷兰学者 E.W.dijkctra提出了结构化程序设计
(structured programming)的理论，成为 70年代后程序设计的主流方法。它提出了一些大家都要遵循的原则，这些原则可以归纳为：
强调程序设计风格和程序结构的规范化，提倡清晰的结构，采用模块化设计,结构化编码自顶向下，逐步细化。
基本结构，组合而成。
清晰第一，效率第二。
书写规范，缩进格式。
工作报告顶层设计 工厂概况 前一阶段工作情况当前遇到的问题今后打算第一点第二点第三点第二层设计第三层设计将问题的求解由抽象逐步具体化！
自顶向下 （将一个任务分为若干层次）
逐步细化 （对各层逐步补充、完善）
模块化设计将一个任务分为若干个相对独立、功能单一的小模块，而每个模块与外部联系只有单一的入口和出口。
结构化编码 （选用结构化的语言）
2.3 算法设计和描述举例以求解全班平均成绩为例来说明怎样制定算法某个班有 10个学生 。 已知他们参加某次考试的成绩 (0到 100之间的整数 ),求全班学生在这次考试中的平均成绩 。
计数器 (counter)控制的循环：
定数循环 （ definite repetition）
total
counter
初始化
Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten
Input the next grade
Add the grade into the total
Add one tothgrade counter
Set the class average to the total divided by ten
Print the class average
main( )
{ int counter,grade,total,average;
/*初始化阶段 */
total=0;
counter=1;
/*处理阶段 */
while(counter<=10)
{ printf("Enter grade:");
scanf("%d",&grade);
total=total+grade;
counter=counter+1;
}
/*终止阶段 */
average=total/10;
printf("Class average is %d,\n",average);
}
用自顶向下、逐步细化的方法制定算法把求全班平均成绩的问题更一般化 。 考虑如下的问题：
开发一个求全班平均成绩的程序,
程序在每次运行时都能够处理任意个数的成绩 。
( top-down,stepwise refinement )
标记值 （ sentinel value）
不定数循环 （ indefinite repetition）
许多程序在逻辑上分为三个阶段：
初始化阶段输入数据值和对程序中的变量作相应调整的处理阶段计算和打印结果的终止阶段
main( )
{ float average;
int counter,grade,total;
total=0;
counter=0;
printf("Enter grade,-1 to end,");
scanf("%d",&grade);
while(grade!=-1)
{ total=total+grade;
counter=counter+1;
printf("Enter grade,-1 to end,");
scanf("%d",&grade);
}
if(counter!=0)
{ average=(float)total/counter;
printf("Class average is %.2f,\n",average);
}
else
printf("No grades were entered.\n");
}
埃拉托色尼筛法：
在纸上写上 1到 1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。
将 1到 1000之间的素数打印出来。
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
(1) 先把 1挖掉
(2) 用 2去除它后面的各个数，把能被 2整除的数挖掉。
(3) 用 3去除它后面的各个数，把能被 3整除的数挖掉。
(4) 分别用 4,5,… 各数作为除数去除这些数后面的各数，直到除数为 为止。
n
算法：（自顶向下，逐步求精）
输入 1到 n
把所有非素数去掉打印全部素数
A
B
C
顶层算法
1、去掉 1；
2、用刚才被去掉的数的下一个数 P去除 P后面的各数，把 P
的倍数去掉；
3、判断 P是否小于 √N 的整数部分，如是，则返回（ 2）继续执行，否则结束；
4、最后只剩素数。
A的细化算法输入 n
1=>i
当 i≤n
A
i=>xi
i+1=>i
回到顶层
B的细化算法
B
将 x1去掉
2=〉 i
如 xi未去掉，则将 xi+1
到 xn间 xi的倍数去掉
i+1=〉 i
当 i< n
D
i+1=〉 i
将能被 xi整除的 xj去掉
D
将 xi+1到 xn间
xi的倍数去掉
xi=0是 否 i+1=〉 j当 j<n
xj=0是 否使 xj=0
是 否
xj能被 xi整除回到顶层
C的细化算法
1=>i
当 i≤n
C
把未挖掉的 xi打印出来
i+1=>i
打印 xi
是 否
xi=0
1,分析
2,设计
(1) 总体设计
(2) 详细设计
3,程序编码以及编辑、编译和连接
4,程序测试
5,编写程序文档程序开发的一般过程为：
总 结
1．分析了解问题相关领域的知识，通过忽略次要方面，而找出解题规律模型。
2．设计设计分为两步：总体设计和详细设计。
当问题较大时,常常要把问题分为一些子问题；当子问题还大时,还应进一步分割 。
这样，一个较大的问题就被分成一些容易求解的子问题，每一个子问题将作为程序的一个模块。这是总体设计的一个任务。
但是，仅仅分解还是不够的，在总体设计时，还要考虑如何组织程序模块。
(1)总体设计
—个教学管理程序的结构图
就是设计每个模块的数据结构和算法 。
(2)详细设计
程序编码
程序的编辑
从源程序到可执行程序 （ exe） 分为两步：
A.编译,（ 编译器 compiler）
将源程序文件翻译成目标程序文件 。
B.连接,（ 连接器 linker）
将目标程序文件中目标程序模块以及程序所需的系统中固有的目标程序模块链接成一个完整的程序 。
3.程序编码以及编辑、编译和连接
(1)程序测试的目的
a.测试是程序的执行过程,目的在于发现错误；
b.一个好的测试实例在于能发现至今末发现的错误；
c.一个成功的测试是发现了至今末发现的错误的测试 。
4．程序测试
(2)测试方法和技术测试是以程序通过编译，没有语法和连接上的错误为前提的。
在此基础上，通过让程序试运行一组数据，来检测程序的逻辑以及程序中的各语句有无错误。
这一组 测试数据 应是以,任何程序都是有错误的,
为前提 精心设计 出来的，而不是随心所欲地乱凑成的。
它不仅应含有被测程序的 输人数据,而且还应包括程序执行它们后 预期的结果 ；每次测试都要把实际的结果与预期的结果相比较，以观察程序是否出错。
(1) 用户拿到程序后会不会使用它?
向用户提供 程序使用说明书 或用户文档 。
(2) 用户在使用过程中,对程序是否满意,永远满意,而不需要做任何修改?
为了便于程序的维护,需提供程序技术说明书 或称程序技术文档 。
5．编写程序文档
—— 算法第二章程序（广义）：
如：某一个会议的程序
宣布全议开始；
奏国歌 ；
校长讲话 ；
宣布获奖者名单；
颁奖；
获奖代表讲话；
宣布会议结束；
再如：做某个菜的程序
洗莱 ；
准备配料 ；
加热锅 ；
锅热后加油 ；
做菜的程序 ；
油热至八成，放入葱、姜、蒜和调料略炒后，加入菜煸炒 ；
加入些许水 ；
菜八成熟时，加入酱油、味精 ；
出锅，并装盘 ；
程序：
用于描述完成某项功能所涉及的对象 和 动作 规则 。
国歌、首长、名单、代表、
话、奖以及菜、锅、油、
水、酱油、味精等奏、颁、讲、宣布、放菜、出锅 动作的先后顺序以及它们能作用的对象，
要遵守一定的规则。
计算机程序：
用于描述计算机完成某项功能所涉及的对象 和 动作 规则 。
数据结构与算法在程序设计的初期 要把精力集中在问题求解的思路上,暂不考虑程序描述的细节。
组织求解对象
制定求解过程的操作步骤和规则数据结构算法数据结构：（ data structure）
描述了问题涉及对象间的联系和组织结构。
指定数据的类型和数据的组织形式。
算法：（ algorithm）
描述了求解问题的步骤或规则。
著名的计算机科学家沃思提出：
数据结构 + 算法 = 程序程序设计的关键是构造程序的数据结构并 描述问题所需要的、施加在这些数据结构上的算法。
2.1算法的概念为解决一个问题而采取的方法和步骤。
原则：
1,保证正确
2,考虑质量例一：求 1× 2× 3× 4× 5的值最原始的方法：
1,1× 2 →p
2,p× 3 →p
3,p× 4 →p
4,p× 5 →p
正确！
But 繁琐！
且不具有通用性！
改进一下！
我发出简单的循环命令，
它重复作同样的事情，
数百成千次，
却只在一瞬间，
有了结果！
1,P?1
2.ｉ? 2
3,P? P × i
4.ｉ?ｉ＋１
5.若ｉ ≤ ５则重复 3,4,5各步 ;否则计算结束。最后的 P值就是 5！。
6.输出ｓ
本算法可推广到求 N!
计算机的拿手好戏：
存储容量大
运算速度快 循环 ★★★
设计具有通用性的循环算法！
闰年的条件：
1.能被 4整除，但不能被 100整除。
2.能被 400整除。 整数
4
例二：判断某一年是否为闰年
1.输入年份 y
2.若 y能被 400整除，输出 y“是闰年,。
3.否则，
若能被 4整除，但不能被 100整除，
输出 y“是闰年,。
4,否则，输出 y“不是闰年,。
100400
例三：判断一个数是否为素数素数：
除了 1和该数本身之外，不能被其它整数整除
1,输入 n
2,i=2
3,n被 i除，得余数 r
4,如果 r=0,打印,n不是素数,,算法结束。
5,i+1=>i
6,如果 i≤n -1，重复 3,4,5步，
否则，打印,n是素数,,算法结束。
改进算法效率
ni?
例四：求正整数 n,m的最大公约数根据若两数能分别被 q整除，则其差也定能被 q整除。
输入 n,m的值
1.若 n>m,则 n? n-m
2.若 m>n,则 m? m-n
3.若 n=m,则计算结束,输出 n。否则,重复
1,2,3各步。
动动脑筋，
改进一下算法！
2.2.1 算法的表示方法
1,用自然语言表示
2,用流程图表示
3,N-S图
4,用伪代码表示算法
2.2 算法的表示及特性
(1)流程图起止框输入输出框判断框处理框流程线连接点开始输入 a,b
a>b
max=a max=b
输出 max
结束求两数最大值的流程图开始
0→s
1→i
s+a→s
i+1→i
i≤5是否结束输入第 i个数给 a
打印 s
输入 5个数求和的流程图三种基本流程结构顺序结构
A
B
P
A B
不成立成立选择结构循环结构
P
不成立
A
成立 P成立
A
不成立当型 (while)循环结构 直到型 (until)循环结构三种基本程序结构：
顺序结构、选择结构、循环结构已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。
由基本结构所构成的算法属于“结构化”算法。
(2)N-S图顺序结构 A
B
成立
A B
P
不成立选择结构循环结构 当 P成立
A
当型 (while)循环结构 直到型 (until)循环结构直到 P成立
A
0→s
1→i
输入第 i个数给 a
s+a→s
i+1→i
直到 i>5为止打印 s的值输入 5个数求和的流程图
有穷性,有限的操作步骤，
在合理的时间内完成。
确定性,每一步必须是确定的，
不能“模棱两可”。
有效性,每一步应当有效执行，
并产生有效和确定的结果。
有零个或多个输入
有一个或多个输出
2.2.2 算法的特性结构化程序设计荷兰学者 E.W.dijkctra提出了结构化程序设计
(structured programming)的理论，成为 70年代后程序设计的主流方法。它提出了一些大家都要遵循的原则，这些原则可以归纳为：
强调程序设计风格和程序结构的规范化，提倡清晰的结构，采用模块化设计,结构化编码自顶向下，逐步细化。
基本结构，组合而成。
清晰第一，效率第二。
书写规范，缩进格式。
工作报告顶层设计 工厂概况 前一阶段工作情况当前遇到的问题今后打算第一点第二点第三点第二层设计第三层设计将问题的求解由抽象逐步具体化！
自顶向下 （将一个任务分为若干层次）
逐步细化 （对各层逐步补充、完善）
模块化设计将一个任务分为若干个相对独立、功能单一的小模块，而每个模块与外部联系只有单一的入口和出口。
结构化编码 （选用结构化的语言）
2.3 算法设计和描述举例以求解全班平均成绩为例来说明怎样制定算法某个班有 10个学生 。 已知他们参加某次考试的成绩 (0到 100之间的整数 ),求全班学生在这次考试中的平均成绩 。
计数器 (counter)控制的循环：
定数循环 （ definite repetition）
total
counter
初始化
Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten
Input the next grade
Add the grade into the total
Add one tothgrade counter
Set the class average to the total divided by ten
Print the class average
main( )
{ int counter,grade,total,average;
/*初始化阶段 */
total=0;
counter=1;
/*处理阶段 */
while(counter<=10)
{ printf("Enter grade:");
scanf("%d",&grade);
total=total+grade;
counter=counter+1;
}
/*终止阶段 */
average=total/10;
printf("Class average is %d,\n",average);
}
用自顶向下、逐步细化的方法制定算法把求全班平均成绩的问题更一般化 。 考虑如下的问题：
开发一个求全班平均成绩的程序,
程序在每次运行时都能够处理任意个数的成绩 。
( top-down,stepwise refinement )
标记值 （ sentinel value）
不定数循环 （ indefinite repetition）
许多程序在逻辑上分为三个阶段：
初始化阶段输入数据值和对程序中的变量作相应调整的处理阶段计算和打印结果的终止阶段
main( )
{ float average;
int counter,grade,total;
total=0;
counter=0;
printf("Enter grade,-1 to end,");
scanf("%d",&grade);
while(grade!=-1)
{ total=total+grade;
counter=counter+1;
printf("Enter grade,-1 to end,");
scanf("%d",&grade);
}
if(counter!=0)
{ average=(float)total/counter;
printf("Class average is %.2f,\n",average);
}
else
printf("No grades were entered.\n");
}
埃拉托色尼筛法：
在纸上写上 1到 1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。
将 1到 1000之间的素数打印出来。
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
(1) 先把 1挖掉
(2) 用 2去除它后面的各个数，把能被 2整除的数挖掉。
(3) 用 3去除它后面的各个数，把能被 3整除的数挖掉。
(4) 分别用 4,5,… 各数作为除数去除这些数后面的各数，直到除数为 为止。
n
算法：（自顶向下，逐步求精）
输入 1到 n
把所有非素数去掉打印全部素数
A
B
C
顶层算法
1、去掉 1；
2、用刚才被去掉的数的下一个数 P去除 P后面的各数，把 P
的倍数去掉；
3、判断 P是否小于 √N 的整数部分，如是，则返回（ 2）继续执行，否则结束；
4、最后只剩素数。
A的细化算法输入 n
1=>i
当 i≤n
A
i=>xi
i+1=>i
回到顶层
B的细化算法
B
将 x1去掉
2=〉 i
如 xi未去掉，则将 xi+1
到 xn间 xi的倍数去掉
i+1=〉 i
当 i< n
D
i+1=〉 i
将能被 xi整除的 xj去掉
D
将 xi+1到 xn间
xi的倍数去掉
xi=0是 否 i+1=〉 j当 j<n
xj=0是 否使 xj=0
是 否
xj能被 xi整除回到顶层
C的细化算法
1=>i
当 i≤n
C
把未挖掉的 xi打印出来
i+1=>i
打印 xi
是 否
xi=0
1,分析
2,设计
(1) 总体设计
(2) 详细设计
3,程序编码以及编辑、编译和连接
4,程序测试
5,编写程序文档程序开发的一般过程为：
总 结
1．分析了解问题相关领域的知识，通过忽略次要方面，而找出解题规律模型。
2．设计设计分为两步：总体设计和详细设计。
当问题较大时,常常要把问题分为一些子问题；当子问题还大时,还应进一步分割 。
这样，一个较大的问题就被分成一些容易求解的子问题，每一个子问题将作为程序的一个模块。这是总体设计的一个任务。
但是，仅仅分解还是不够的，在总体设计时，还要考虑如何组织程序模块。
(1)总体设计
—个教学管理程序的结构图
就是设计每个模块的数据结构和算法 。
(2)详细设计
程序编码
程序的编辑
从源程序到可执行程序 （ exe） 分为两步：
A.编译,（ 编译器 compiler）
将源程序文件翻译成目标程序文件 。
B.连接,（ 连接器 linker）
将目标程序文件中目标程序模块以及程序所需的系统中固有的目标程序模块链接成一个完整的程序 。
3.程序编码以及编辑、编译和连接
(1)程序测试的目的
a.测试是程序的执行过程,目的在于发现错误；
b.一个好的测试实例在于能发现至今末发现的错误；
c.一个成功的测试是发现了至今末发现的错误的测试 。
4．程序测试
(2)测试方法和技术测试是以程序通过编译，没有语法和连接上的错误为前提的。
在此基础上，通过让程序试运行一组数据，来检测程序的逻辑以及程序中的各语句有无错误。
这一组 测试数据 应是以,任何程序都是有错误的,
为前提 精心设计 出来的，而不是随心所欲地乱凑成的。
它不仅应含有被测程序的 输人数据,而且还应包括程序执行它们后 预期的结果 ；每次测试都要把实际的结果与预期的结果相比较，以观察程序是否出错。
(1) 用户拿到程序后会不会使用它?
向用户提供 程序使用说明书 或用户文档 。
(2) 用户在使用过程中,对程序是否满意,永远满意,而不需要做任何修改?
为了便于程序的维护,需提供程序技术说明书 或称程序技术文档 。
5．编写程序文档
