重庆警院《计算机基础》课件第8章 算法和程序设计语言

1、 第8章 算法和程序设计语言教学目的了解算法与程序的基本概念掌握自然语言、流程图、伪代码等算法的表示方法掌握枚举、迭代、排序和查找等算法设计的基本方法学习内容算法与程序算法的基本概念算法的概念算法的表示算法设计的基本方法枚举法迭代法排序查找一 算法与程序什么是程序？按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则计算机学科中,程序描述了计算机处理数据、解决问题的过程程序和算法的关系是怎样的？ 引例:从存放教职工档案的“d:zgxx.txt”文件中，显示出教龄满30年的女教工的姓名和所在部门程序=数据结构+算法程序包括两方面的内容：（1）对数据的描述:指定欲处理的数据类型

2、和数据的组织形式，也就是数据结构。例如教职工的姓名, 部门, 教龄等都具有相应的数据类型（2）对操作的描述:指定操作步骤，例如“fopen”打开文件、“fscanf”读入数据、“If”判断是否满足条件等。这些操作的先后顺序以及它们所作用的数据，要遵守一定的规则，即求解问题的的算法。二 算法的概念1 什么是算法?广义的说：计算机来解决的某一类问题的方法或步骤。在数学中：按照一定规则解决某一类问题的明确和有限的步骤，称为算法。算法是程序的核心计算机解决任何问题都要依赖于算法。只有将解决问题的过程分解为若干个明确的步骤,即算法,并用计算机能够接受的“语言”准确地描述出来，计算机才能够解决问题。广播操

3、图解是广播操的算法；菜谱是做菜的算法；歌谱是一首歌曲的算法；空调说明书是空调使用的算法。我们身边的算法算法趣味案例1： 有一个农夫带一条狼、一只羊和一筐白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？ 方法和过程：1、带羊到对岸，返回；2、带菜到对岸，并把羊带回；3、带狼到对岸，返回；4、带羊到对岸。算法趣味案例2:小球称重 9个编号小球中有一个的质量偏小，其余的质量标准。用一天平,无需砝码，检出质量偏小的小球。解法三：先将小球分成（1，2，3，4）与（5，6，7，8）两堆，若两堆的质量的相等则偏小的小球是第9个，否则将偏轻的小球分

4、成两堆进行称量。解法一：9个小球分成5堆，（1,2）,（3,4）,（5,6）,（7,8）,（9）解法二：可将9个小球分成3堆进行称量, (1,2,3), (4,5,6),(7,8,9),若1,2相等,则称量第三堆中,否则对偏轻的一堆继续称量。哪种方法称量次数最少?2 算法的两个要素算法是由操作与控制结构两个要素组成（1）操作算术运算：加、减、乘、除等。关系运算：大于、大于等于、小于、小于等于、等于、不等于等。逻辑运算：与、或、非等。数据传送：输入、输出、赋值等。（2）控制结构 各操作之间的执行顺序 顺序结构、选择结构、循环结构 称为算法的三种基本结构1.顺序结构 程序按照语句的书写次序顺序执行

5、。BA 先执行A操作，再执行B操作，两者是顺序执行关系。 2.选择结构 通过判断特定条件，选择一个分支执行。当P条件成立时，执行A操作，否则执行B操作APB 成立不成立 语句不成立 P成立当P条件成立时，执行语句操作，否则跳过语句操作逻辑判断 3. 循环结构 在给定条件下，反复执行循环体，直到条件不满足为止.(1)形式a当型循环结构不成立 PA成立 当P条件成立时，反复执行A,直到P为零为止。逻辑判断逻辑判断(2)形式b直到型循环结构先执行A操作，再判断P是否成立，若P成立，再执行A，直到P不成立为止。AP成立不成立逻辑判断逻辑判断将例2 求1+2+3+4+10的和用流程图进行描述。 n+1

6、= n1 = ns+n = s0 = sn 10输出s是否算法举例-流程图描述3 算法的特点有穷性 任意一个算法在执行有穷个计算步骤后必须终止。每一个计算步骤，必须是精确地定义、无二义性可行性 有限多个步骤应该在一个合理的范围内进行输入 一般有0个或多个输入，它们取自某一特定的集合。输出 一般有若干个输出信息，是反映对输入数据加工后的结果。4 算法的分类（1）数值计算算法 用于科学计算。特点是少量的输入、输出，复杂的运算。例如：计算圆周率，积分（2）非数值计算算法 对数据的管理。特点是大量的输入、输出，简单的算术运算和大量的逻辑运算。例如：排序 查找替换 5 算法的表示自然语言传统流程图N-S

7、流程图伪代码计算机语言算法及其描述方法 自然语言描述烧开水的过程第一步，往壶内注水。第二步，点火加热。第三步，观察；如果水开，则停止燃火，否则继续燃火。第四步，如果水未开，重复过程的第三步，直至水开。自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想利用求圆周率公式 计算圆周率分析:对通项式：ti= ，i=1，2， ，进行累加，直到某项ti绝对值小于精度即|t| n1 = ns+n = s0 = sn 10输出s是否伪代码介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解。1. 输入n;

8、2. f=1;3. i=1;4. 循环直到in结束4.1 f=i*f;4.2 i=i+1;5. 输出f;BEGIN pi0 /变量赋初值 s1 i1 t1 While (|t|10-8) pipi+ t/计算累加和 s-1*s ii+1 ts*1/(2*i-1)/计算通项Print pi*4/输出圆周率值 End 有如下简单约定：用Begin开始、End结束；每一条指令占一行“/”标志表示注释输入/输出以Input/Print表示；用“”表示赋值； 用缩进表示代码块结构，块中多句语句用一对括起；数组形式：数组名下界上界；数组元素：数组名序号；一些函数调用或者处理简单任务可以用一句自然语言代替。

9、计算机语言#include iostream.h /文件包含，作用为输入和输出#include iomanip.h/文件包含，作用为输入和输出#include math.h/包含数学函数void main()int s,i;/s为控制正负号变化，i为第i项double pi,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); /下一项值coutsetprecision(8)pi*4endl

10、;只有用计算机语言编写的程序才能被计算机执行必须严格遵循所选择的编程语言的语法规则三 常用算法枚举法迭代法排序选择法冒泡法查找顺序查找二分查找枚举法亦称穷举法或试凑法。例：计算机破案 张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？分 析 用0表示不是凶手，1表示凶手，则每个人的取值范围就是0，1算 法在每个人的取值范围0，1的所有可能中进行搜索，如果表格的组合条件同时满足，即为凶手。相应的伪代码为：For A=0 to 1

11、For B=0 to 1 For C=0 to 1 For D=0 to 1 If(A=0)+(C=1)+(D=1)+(D=0)=3And(A+B+C+D=1) Print A,B,C,D / 输出的值是1的为凶手，要同时满足例:安排考试3门课程为A、B、C，考试安排在周一到周六，先考A，后考B，最后考C课程；一天只能安排一门课程考试；最后课程只能安排在周5或周6，请列出安排考试的所有方案。分析：解决该问题关键是根据安排日期的规定，每门课程搜索的日期范围不同；For A=1 To 4 For B=A+1 To 5 /B课程总比A晚考 For C= 5 To 6 /C最早周5考 If (BC )

12、 /排除B=C的情况，不能在同一天考 Print A,B,C / 输出的值是A、B、C分别安排的考试周的星期几综合案例： 4位同学中有一位做了好事不留名，表扬信来了之后，校长问这4位是谁做的好事。 A说：不是我。 B说：是C。 C说：是D。 D说：他胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。问题分析：分别假设这个做好事的人为这四人中的一个，然后到每句话中去测试，看有几句话是真话，若有三句真话（第3、4条为互补规则，无法同时满足），则该人是要找的人。已知规则（转化为相应的表达式）： A说：不是我。对应（thisman!=A） B说：是C。对应（this

13、man=C） C说：是D。对应（thisman=D） D说：他胡说。对应（thisman!=D）数据处理：判定每条规则的真假值（0或1），求取4条规则值之和。循环部分：thisman=A时，A!=A; 假，值为0；A=C; 假，值为0；A=D; 假，值为0；A!=D; 真，值为1；判断部分：判断是否有三句真话，即求和值等于3时满足条件，终止循环。thisman换成下一个人开始结束this=Dthisman=A4个表达式加求和sum是否打印thismansum=3是否枚举法基本思想:采用搜索的方法，根据题目的部分条件确定答案的大致搜索范围在此范围内对所有可能的情况逐一验证若某个情况符合题目的条件

14、，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。枚举法是一种比较熬时的算法。为提高效率，根据解决问题的情况，尽量减少内循环层数或每层循环次数。思考题:百元买百鸡问题。假定小鸡每只0.5元,公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，列出所有可能的购鸡方案。搜索的范围?要满足的条件是什么？请尝试画出算法流程图枚举法问题分析与算法设计设：要买x只公鸡，y只母鸡，z只小鸡，可得到方程: x+y+z=100 5x+3y+z/3=100 取值范围：x：1 20 y：1 33 z: 3 99迭代法又称递推法，利用问题本身所具有的某种递推关系求解问题。例：猴子吃桃问

15、题 小猴有桃若干，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7天早上只剩下1个了，问小猴原有多少个桃子？设第n天的桃子为xn，它是前一天的桃子数的一半少1个，即xn-1=(xn+1)2 （递推公式）总结迭代法的基本思想: 从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。思考题：高次方程求根求高次方程根： 的近似解，精度为10-5 。迭代公式为：算法步骤为：选择方程的近似根作为初值赋值给x1；将x1的值保存于x0，通过迭代公式求得新

16、近似根x1；若x1与x0的差绝对值大于指定的精度时，继续执行 步骤迭代；否则x1就是方程的近似解。：初值的选择对计算有什么影响？请画出算法流程图排序常用排序算法选择法冒泡法插入排序合并排序快速排序1234567431891355743以7个元素为例说明选择排序位置1位置7的元素初始排列如下所示算法思想:每次在无序数中找最小（递增）数的下标，然后存放在无序数的第一个位置。(1)选择法1234567431891355743第一趟：从7个元素中选出最小者，将其换入位置1，过程为：令min_elem表示最小元素（初值为位置1的元素），k为最小元素的位置序号（初值为1），逐一比较，找出最小元素及其位置。

17、位置6的元素最小交换12345677439135543431234567718913554343第二趟：从6个元素中选出最小者，将其换入位置2，过程为：令min_elem表示最小元素（初值为位置2的元素），k为最小元素的位置序号（初值为2），逐一比较，找出最小元素及其位置位置3的元素最小交换12345677918135543431234567791813554343第三趟：从5个元素中选出最小者，将其换入位置3，过程为：令min_elem表示最小元素（初值为位置3的元素），k为最小元素的位置序号（初值为3），逐一比较，找出最小元素及其位置位置4的元素最小交换123456779131855434

18、31234567791318554343第四趟：从4个元素中选出最小者，将其换入位置4，过程为：令min_elem表示最小元素（初值为位置4的元素），k为最小元素的位置序号（初值为4），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791318554343第五趟：从3个元素中选出最小者，将其换入位置5，过程为：令min_elem表示最小元素（初值为位置5的元素），k为最小元素的位置序号（初值为5），逐一比较，找出最小元素及其位置位置6的元素最小交换12345677913184355431234567791318435543第六趟：从2个元

19、素中选出最小者，将其换入位置6，过程为：令min_elem表示最小元素（初值为位置6的元素），k为最小元素的位置序号（初值为6），逐一比较，找出最小元素及其位置位置7的元素最小交换12345677913184343551234567431891355743以7个元素为例，经过6趟选择，将元素排列有序排序12345677913184343557个元素进行选择排序时，需要六趟，用i表示趟数i 1i=6?结束Yi i+1N进行第i趟选择排序开始i 1i=6?结束Yi i+1Nk表示最小元素的位置k i, j i+1 比较ak和aj如果ajak则令k = jj j+1NY交换ak和aj开始j=7?12

20、34567431891355743以7个元素为例说明冒泡排序位置1位置7的元素初始排列如下所示(2) 冒泡法1234567431891355743第一步：令位置1和位置2的元素比较，若位置1的元素大，则交换交换1234567184391355743第二步：令位置2和位置3的元素比较，若位置2的元素大，则交换交换12345671894313557431234567189431355743第三步：令位置3和位置4的元素比较，若位置3的元素大，则交换交换1234567189134355743第四步：令位置4和位置5的元素比较，若位置4的元素大，则交换第五步：令位置5和位置6的元素比较，若位置5的元素

21、大，则交换交换12345671891343755431234567189134375543第六步：令位置6和位置7的元素比较，若位置6的元素大，则交换交换1234567189134374355最大元素被交换到最后一个位置(位置7)下一趟则需将次大元素交换到倒数第二个位置1234567189134374355123456791813437435512345679131843743551234567913187434355次大元素被交换到倒数第二个位置(位置6)下一趟则需将第三大元素交换到倒数第三个位置，依此类推以7个元素为例说明冒泡排序，存放每个元素的位置以序号进行标记经过六趟冒泡排序后，位置1

22、位置7中的元素排列如下所示12345677913184343551234567431891355743排序i 1i=6?结束Yi i+1N进行第i趟冒泡排序开始7个元素进行冒泡排序时，需要六趟，用i表示趟数i 1iaj+1则交换j j+1NYj表示元素的位置aj与aj+1是相邻的元素jamid，low = mid+1； 若xhigh无查找区域，找不到思考题利用二分法查找方法，设计人与计算机做猜数游戏。由计算机随机产生一个1，100的任意整数key，让用户猜这个数。利用二分法的思想,该怎样解决?请画出流程图小结什么叫算法？算法和程序的关系?算法的要素，算法的特征常见的算法表示形式，它们的优缺点。

23、常用算法：枚举、迭代、排序、查找思考题 1.根据下面的算法画出流程图，实现输入两个数并显示出其中的较大数。 1）输入A，B两个数 2）比较这两个数，判断哪个数大，将较大数放入BIG变量中 3）显示较大数2.用伪代码和流程图编写一个算法，要求实现重复输入10数，显示每个数及其平方数。3.用枚举法算法思想，写出求方程：i3+j3+k3=1根的伪代码，其中i,j,k的取值范围为：-3i5； -5j6；-4k2。4.用伪代码或流程图编写一个算法，实现重复输入10个数，求最小值和最大值，并把结果显示。程序设计语言发展语言处理程序程序设计一般过程程序设计方法4 程序设计语言概述系统软件操作系统语言处理程序

24、实用程序翻译工具作用：将源程序翻译成计算机能识别的机器语言程序。程序设计语言：机器语言汇编语言高级语言典型的程序设计语言有：FORTRAN、Pascal、C与C+、BASIC、Java、C#等。汇编程序编译程序解释程序1.机器语言由“0”、“1”二进制代码按一定规则组成的、能被机器直接理解、执行的指令集合。 缺点：编程工作量大，难学、难记、难修改； 不同计算机的指令系统不同，机器语言通用性差优点：代码不需要翻译，所占空间少，执行速度快。例如，计算A=15+10 的机器语言程序如下：10110000 00001111： 把15放入累加器A中00101100 00001010： 10与累加器A的值

25、相加，结果仍放入A中11110100： 结束，停机2.汇编语言使用反映机器指令功能的助记符代替机器语言的符号语言。例如用ADD表示加、SUB表示减、JMP表示程序跳转等等。优点：克服了机器语言难读等缺点，保持了其编程质量高、占存储空间少，执行速度快的优点。缺点：仍然依赖于机器，通用性差。特点：源程序必须通过汇编程序翻译成机器语言。常用于过程控制等编程。例如，计算 A=15+10 的汇编语言程序：MOVA，15：把15放入累加器A中ADDA，10：10与累加器A相加，结果存入A中HLT：结束，停机类比：IP地址202.120.189.146机器语言域名汇编语言3.高级语言接近于自然语言和数学公式

26、的程序设计语言。优点：接近算法语言，易学、易掌握，可读性好，可维护性强，可靠性高；可移植性好，重用率高自动化程度高，编程效率高。缺点：源程序要通过翻译程序翻译成机器语言，代码不最优。例如，计算 A=15+10 的BASIC语言程序如下：A=15+10 15与10相加的结果放入A中PRINT A 输出AEND 程序结束2 语言处理程序机器语言源程序汇编语言源程序机器语言程序（目标程序）汇编程序翻译低级语言处理程序高级语言翻译程序高级语言源程序计算结果解释程序数据高级语言源程序计算结果连接程序数据目标程序可执行程序编译程序解释方式编译方式BasicC+程序库可脱离编译程序和源程序独立存在并反复使用3 程序设计的一般过程分析问题确定数学模型程序编写、编辑、编译和连接算法设计运行和测试结构化程序设计思想最早由荷兰科学家E.W.Dijkstra提出任何程