第8章算法和程序设计语言

算法初步同济大学教学目的了解算法与程序的基本概念掌握自然语言、流程图、伪代码等算法的表示方法掌握枚举、迭代、排序和查找等算法设计的基本方法2教学内容

算法与程序算法的基本概念算法的概念算法的表示算法设计的基本方法枚举法迭代法排序查找3一算法与程序什么是程序？程序和算法的关系是怎样的？

引例:从存放教职工档案的“d:\zgxx.txt”文件中，显示出教龄满30年的女教工的姓名和所在部门按一定的顺序安排的工作即操作序列描述完成某项功能所涉及的对象和动作规则计算机学科中,程序描述了计算机处理数据、解决问题的过程45程序=数据结构+算法程序包括两方面的内容：（1）对数据的描述:指定欲处理的数据类型和数据的组织形式，也就是数据结构。例如教职工的姓名,部门,教龄等都具有相应的数据类型文件d:\zgxx.txt指定了数据的组织形式。（2）对操作的描述:指定操作步骤，例如“fopen”打开文件、“fscanf”读入数据、“If”判断是否满足条件等。这些操作的先后顺序以及它们所作用的数据，要遵守一定的规则，即求解问题的的算法。二算法的概念1什么是算法?计算机来解决的某一类问题的方法或步骤算法是程序的核心例:小球称重

9个编号小球中有一个的质量偏小，其余的质量标准。用一天平,无需砝码，检出质量偏小的小球。6

解法三：先将小球分成（1，2，3，4）与（5，6，7，8）两堆，若两堆的质量的相等则偏小的小球是第9个，否则将偏轻的小球分成两堆进行称量。解法一：9个小球分成5堆，（1,2）,（3,4）,（5,6）,（7,8）,（9）解法二：可将9个小球分成3堆进行称量,

(1,2,3),(4,5,6),(7,8,9),若1,2相等,则称量第三堆中,否则对偏轻的一堆继续称量。7哪种方法称量次数最少?例:圆周率的计算(1)割圆法8S正12边形=12×△S=4圆周率=S正12边形/R/R=3公元3世纪，刘徽利用“割圆术”，也就是利用圆内接正六边形算起，依次将边数加倍，一直算到内接正3072边形的面积，从而得到圆周率的近似值为=3.1416，祖冲之把圆周率精确到小数点后15位算法步骤：①量出圆的半径R②做圆的内接正n边形③求小三角形的面积△S④求圆的内接正n边形面积S=△S×n⑤求圆周率=S/R/R⑥结束9(2)利用求圆周率公式

同一个问题，可用不同的算法来求解算法不同，求解的效率不同选择效率高、容易理解和编程实现的算法2算法的两个要素

算法是由操作与控制结构两个要素组成（1）操作①算术运算：加、减、乘、除等。②关系运算：大于、大于等于、小于、小于等于、等于、不等于等。③逻辑运算：与、或、非等。④数据传送：输入、输出、赋值等。10(a)顺序结构(b)选择结构（2）控制结构各操作之间的执行顺序顺序结构、选择结构、循环结构，称为算法的三种基本结构11(c)当型循环结构(d)直到型循环结构12输出count开始置初态：累加器count←0;到文件结尾了吗？输出职工信息,Count++结束falsetrue从整体上看是顺序结构13打开文件教龄>30且性别为女？从文件中读入一行truefalse当型循环3算法的特点有穷性

任意一个算法在执行有穷个计算步骤后必须终止。每一个计算步骤，必须是精确地定义、无二义性可行性

有限多个步骤应该在一个合理的范围内进行输入

一般有0个或多个输入，它们取自某一特定的集合。输出

一般有若干个输出信息，是反映对输入数据加工后的结果。144算法的分类（1）数值计算算法

用于科学计算

特点是少量的输入、输出，复杂的运算。例如：计算圆周率，积分（2）非数值计算算法

对数据的管理

特点是大量的输入、输出，简单的算术运算

和大量的逻辑运算。例如：排序查找替换

随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究的任务更重。155算法的表示自然语言传统流程图N-S流程图伪代码计算机语言16利用求圆周率公式

计算圆周率分析:对通项式：ti=，i=1，2，…，进行累加，直到某项ti绝对值小于精度即|t|<10-8为止。17自然语言①置初态：累加器pi←0，计数器i←1，第1项t←1，正负符号变化s←1；②重复执行下面的语句，直到某项绝对值小于精度，转③；求累加和：pi←pi+t；为下一项作准备：i←i+1、s←-1*s、t←s*1/(2*i-1)；③输出：显示结果pi*4。④结束优点:通俗易懂缺陷：（1）不太严格，易产生歧义性。（2）繁琐、冗长，并且很难清楚地表达算法的逻辑流程，不直观。18传统流程图采用一些图框、线条以及文字说明来形象地、直观地描述算法处理过程。19输出pi*4开始pi←0;s←1i←1;t←1|t|≥10-8pi←pi+ts←-1*si←i+1t←s*1/(2*i-1)结束falsetrue计算圆周率的流程图缺陷：制作费时优点:较好的体现程序设计的逻辑20N-S流程图美国学者I.Nassi和B.Shneideman提出去掉了传统流程图中带箭头的流向线,全部算法以一个大的矩形框表示，该框内还可以包含一些从属于它的小矩形框适于结构化程序设计。21

计算圆周率N-S图

N-S图的三种控制结构22BEGIN

pi←0//变量赋初值

s←1

i←1

t←1

While(|t|≥10-8)

{

pi←pi+t//计算累加和s←-1*si←i+1t←s*1/(2*i-1)//计算通项}Printpi*4//输出圆周率值End有如下简单约定：用Begin开始、End结束；每一条指令占一行“//”标志表示注释输入/输出以Input/Print表示；用“”表示赋值；用缩进表示代码块结构，块中多句语句用一对{}括起；数组形式：数组名[下界‥上界]；数组元素：数组名[序号]；一些函数调用或者处理简单任务可以用一句自然语言代替。伪代码:用介于自然语言和计算机语言之间的文字和符号来描述算法。

23计算机语言#include"iostream.h" //文件包含，作用为输入和输出#include"iomanip.h" //文件包含，作用为输入和输出#include"math.h" //包含数学函数voidmain(){ ints,i; //s为控制正负号变化，i为第i项 doublepi,t; //pi存放累加和项，t当前某项 pi=0; s=i=1=t;; while(abs(t)>=0.00000001)//当当前项还没有到达精度，继续求和 { pi=pi+t; //求和 s=-1*s; //为下一项作准备，符号变化/ i++; // t=s*1.0/(2*i-1); //下一项值 } cout<<setprecision(8)<<pi*4<<endl;}只有用计算机语言编写的程序才能被计算机执行必须严格遵循所选择的编程语言的语法规则24三

常用算法枚举法迭代法排序选择法冒泡法查找顺序查找二分查找25枚举法亦称穷举法或试凑法。例：计算机破案张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？26分析

用0表示不是凶手，1表示凶手，则每个人的取值范围就是[0，1]

27算法

在每个人的取值范围[0，1]的所有可能中进行搜索，如果表格的组合条件同时满足，即为凶手。相应的伪代码为：ForA=0To1ForB=0TO1ForC=0To1ForD=0To1If((A=0)+(C=1)+(D=1)+(D=0))=3And(A+B+C+D=1)PrintA,B,C,D//输出的值是1的为凶手，要同时满足28例:安排考试3门课程为A、B、C，考试安排在周一到周六，先考A，后考B，最后考C课程；一天只能安排一门课程考试；最后课程只能安排在周5或周6，请列出安排考试的所有方案。分析：解决该问题关键是根据安排日期的规定，每门课程搜索的日期范围不同；ForA=1To4ForB=A+1To5//B课程总比A晚考ForC=5To6//C最早周5考If(B<C)//排除B=C的情况，不能在同一天考PrintA,B,C//输出的值是A、B、C分别安排的考试周的星期几29总结枚举法基本思想:采用搜索的方法，根据题目的部分条件确定答案的大致搜索范围在此范围内对所有可能的情况逐一验证若某个情况符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。枚举法是一种比较熬时的算法。为提高效率，根据解决问题的情况，尽量减少内循环层数或每层循环次数。30思考题:百元买百鸡问题。假定小鸡每只0.5元,公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，列出所有可能的购鸡方案。搜索的范围?要满足的条件是什么？请尝试写出伪代码31迭代法又称递推法，利用问题本身所具有的某种递推关系求解问题。例：猴子吃桃问题小猴有桃若干，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7天早上只剩下1个了，问小猴原有多少个桃子？32设第n天的桃子为xn，它是前一天的桃子数的一半少1个，即xn-1=(xn+1)×2（递推公式）33总结迭代法的基本思想:从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。34思考题：高次方程求根求高次方程根：的近似解，精度ε为10-5。迭代公式为：算法步骤为：①选择方程的近似根作为初值赋值给x1；②将x1的值保存于x0，通过迭代公式求得新近似根x1；③若x1与x0的差绝对值大于指定的精度ε时，继续执行步骤②迭代；否则x1就是方程的近似解。：初值的选择对计算有什么影响？请画出算法流程图35排序常用排序算法选择法冒泡法插入排序合并排序快速排序36(1)选择法将N个数按照从小到大的顺序排序原始数据869327过程演示算法思想:每次在无序数中找最小（递增）数的下标，然后存放在无序数的第一个位置。Fori=0Ton-2//n个数进行n-1轮比较{min←i//每一轮内，假定当前个最小Forj=i+1Ton-1Ifa[j]<a[min]min←j//记录当前的最小元素，替换mina[i]元素与a[min]元素交换//一轮结束，最小的元素放在a[i]位置}37(2)冒泡法①从第一个元素开始，对数组中两两相邻的元素比较，即a[0]与a[1]比若为逆序，则a[0]与a[1]交换；然后a[1]与a[2]比较，…，直到最后a[n-2]与a[n-1]比较，这时一轮比较完毕，一个最大的数“沉底”，成为数组中的最后一个元素a[n-1]，一些较小的数如同气泡一样“上浮”一个位置。②然后对a[0]～a[n-2]的n-1个数进行同①的操作，次最大数放入a[n-2]元素内，完成第二轮排序；依次类推，进行n-1轮排序后，所有数均有序，第3轮比较后，实际数组已经有序，后面两轮比较是多余,如何解决?38Fori=0Ton-2//n个数进行n-1轮比较Forj=0Ton-2-i//每一轮内Ifa[j]>a[j+1]//若相邻两个次序不对

a[j]与a[j+1]元素交换//则交换位置，小数上浮，大数下沉Fori=0Ton-2//n个数进行n-1轮比较{noswap←true//数据不需交换,即已经有序

Forj=0Ton-2-i//每一轮内Ifa[j]>a[j+1]//若相邻两个次序不对

{a[j]与a[j+1]元素交换//则交换位置，小数上浮，大数下沉noswap←false//一旦交换过，noswap设置为flase}Ifnoswap数据已经有序提前结束//一轮比较结束，根据noswap值判断数据有序否

}数据已经有序后,后续的比较可省略查找39已知姓名,怎么查找某个学生?已知学号,怎么查找某个学生?1251252高靖遥男交通运输类1251254李一鸣男交通运输类1251259张晓敏女交通运输类1251269施奕辰男交通运输类1251270方尧男交通运输类1251271应一丹女交通运输类1251273王子恒男交通运输类1251278黄彬男交通运输类1251281朱一鸣男交通运输类1251283陈钰女交通运输类1251285王羿童男交通运输类1251298邓能静女交通运输类1251306王寒冰男交通运输类1251314陈彦旭男交通运输类1251328温馨女交通运输类1251329刘建兴男交通运输类1251330彭洋男交通运输类(1)顺序查找适用于无序序列，按顺序逐一比对。

例：输入一个数key，查找它是否在数列中，如在，输出是第几个数。40(2)二分查找二分法查找只适合于在已排好序的数组中进行。①待查区间的下界low为1，上界high为N。②求待查区间中间元