第9.2节 程序与算法

1、问题解决和算法，2，第九章问题解决和算法9.1问题解决9.2程序和算法9.2.1程序9.2.2算法的概念9.2.3算法的表达9.3算法设计的基本方法9.3.1枚举法9.3.2迭代9.3.3排序9.3.4搜索9.3.5编程的一般过程9.3.6编程1 .程序例9.2以下是某个学校颁奖典礼的程序：主持人宣布颁奖典礼开始，介绍领导宣布获胜者，主持人宣布会议结束。按一定顺序排列的工作，即操作顺序，描述了完成某项功能所涉及的对象和动作规则。在计算机科学中，程序描述了计算机处理数据和解决问题的过程。3.什么节目？例9.2下面是某学校颁奖仪式的程序：主持人宣布颁奖仪式开始，介绍出席颁奖仪式的领导，发言并宣布获

2、奖者，主持人宣布会议结束。按一定顺序排列的工作，即操作顺序，描述了完成某项功能所涉及的对象和动作规则。在计算机科学中，程序描述了计算机处理数据和解决问题的过程。例9.3教师节到来时，有必要向已经教书30年的教职员工颁发荣誉证书。要求从存储教师档案的“d:zg.dat”文件中显示从事教学30年的教师的姓名和部门。c语言程序如下：# include stdafx . h # include int main()charxm 80，charbm80int jl文件*fp。fp=fopen(d:zg.dat，r)；while(！feof(fp) fscanf(fp，%s，XM)；fscanf(fp，%

3、s，BM)；程序包括两个方面：(1)数据描述：指定要处理的数据类型和数据组织形式，即数据结构。例如，教工的姓名、部门、教龄都有相应的数据类型，文件d:zgxx.txt规定了数据的组织形式。(2)操作描述：规定了操作步骤，如打开文件、读取数据、判断是否满足条件等。这些操作的顺序和它们所作用的数据应该遵守一定的规则，即解决问题的算法。程序=数据结构算法，两种算法的概念，1什么是算法？用计算机解决某类问题的方法或步骤算法是程序的核心示例：称：个小球，九个编号的小球中有一个质量小，其余的有质量标准。使用不带重量的天平来检测小球。7，两个算法的概念，1什么是算法？用计算机解决某类问题的方法或步骤算法是程

4、序的核心示例：称：个小球，九个编号的小球中有一个质量小，其余的有质量标准。使用不带重量的天平来检测小球。解决方案3:将小球分成两堆(1，2，3，4)和(5，6，7，8)。如果两堆的质量相等，较小的球是第九个；否则，将较轻的球分成两堆称重。解决方案1:将9个球分成5堆：(1，2)、(3，4)、(5，6)、(7，8)、(9)；解决方案2: 9个球可以分成3堆进行称重，(1，2，3)，(4，5，6)，()、9、哪种方法的称重次数最少？圆周率的计算(1)割线法，10，S正则12边=12 S=4，圆周率=S正则12边/R/R=3。公元3世纪，刘辉使用了“割线圆”，即利用一个圆内接正六边形，并依次将边数增

5、加一倍，直到祖冲之精确圆周率到小数点后15位，算法步骤：测量圆的半径R，作一个圆的正n边内接，求一个小三角形的面积，求一个圆的正n边内接面积，求圆周率=S/R/R，端，11，(2)利用圆周率公式， 相同的问题可以用不同的算法来解决，具有不同的求解效率和较高的选择效率关系运算：大于、大于或等于、小于、小于或等于、等于、不等于等。 逻辑运算：与、或、非等。数据传输：输入、输出、分配等。12，(a)序列结构，(b)选择结构，(2)控制结构，序列结构，选择结构和循环结构的操作之间的执行序列，它们被称为算法的三个基本结构，13，(c)正循环结构(d)直到正循环结构，14，它是序列结构，15总体上，打开文

6、件，从文件中读取一行，真，假，正循环，3个算法的特征，和有限性。任何算法必须在执行有限计算步骤后终止。每个计算步骤都必须精确定义，没有歧义，并且可行性有限。应该在合理的范围内执行多个步骤。通常有0个或更多的输入，它们取自一个特定的集合。输出通常有几个输出信息，反映了处理输入数据的结果。算法分类(1)数值计算算法用于科学计算，其特点是输入输出量小，运算复杂。非数值计算算法的数据管理特征是大量的输入和输出、简单的算术运算和大量的逻辑运算。例如，排序、搜索和替换，随着计算机技术的发展和应用的普及，非数值计算算法涉及的范围更广，研究任务更重。17，5算法表示，自然语言，传统流程图，伪代码计算机语言，1

7、8，使用pi公式计算pi，分析：并累加通式：ti=，i=1，2，直到某个ti的绝对值小于精度，即|t|10-8。19，自然语言，初始状态：累加器pi0，计数器i1，第一项t1，正负符号变化S1；重复下面的语句，直到某个项目的绝对值小于精度，然后旋转；计算累计总和：pipit准备下一个项目：ii 1，s-1*s，TS * 1/(2 * I-1)；输出：显示结果pi*4。优点：容易理解缺点：(1)不严格，容易产生歧义。(2)繁琐冗长，难以清晰表达算法的逻辑流程，不直观。20、传统流程图，使用一些图片框、线条和文字描述来形象直观地描述算法处理过程。21，计算圆周率的流程图，缺点：制作费时，优点：更好

8、地反映了程序设计的逻辑，22，BEGIN pi0 /变量赋值为初始值s1 i1 t1同时(|t|10-8) pipi t/计算累积和s-1 * sii1 ts * 1/(2 * i .每条指令占用一行“/”，表示注释的输入/输出表示为Input/Print；使用“”表示分配；缩进用来表示代码块的结构，并且块中的多个句子被一对包围；数组形式：数组名称的下限和上限；数组元素：数组名称的序列号；一些函数调用或简单的任务可以被自然语言代替。伪代码：描述了自然语言和计算机语言之间的单词和符号算法。，23，计算机语言，# includei OS stream . h/文件包含，用作输入和输出#include iomanip.h/文件包含，用作输入和输出# includei math . h/包含数学函数void main() int s，I；/s是控制符号变化，I是第一项双圆周率，t；