算法与程序设计课件3.ppt

《算法与程序设计课件3.ppt》由会员分享，可在线阅读，更多相关《算法与程序设计课件3.ppt（99页珍藏版）》请在优知文库上搜索。

1、算法与程序设计算法与程序设计第一章第一章 算法和算法的表示算法和算法的表示算法的概念算法的概念1、算法的概念、算法的概念 所谓所谓“算法算法”，就是解题方法的精确描述。，就是解题方法的精确描述。“算法算法”是用是用来表示解决问题的方法和步骤，它是由有限个步骤组成的。来表示解决问题的方法和步骤，它是由有限个步骤组成的。 从更广义的角度来看，并不是只有从更广义的角度来看，并不是只有“计算计算”的问题才有算法的问题才有算法。乐谱乐谱菜谱菜谱广播操图解广播操图解2.算法实例算法实例 华罗庚在数学普及读物华罗庚在数学普及读物统筹方法平话及补充统筹方法平话及补充中，以中，以“泡茶泡茶”为例，阐明了设计和选

2、择合适的、优化的算法的重要为例，阐明了设计和选择合适的、优化的算法的重要性。性。算法的特性算法的特性 1.有穷性有穷性 例：例：1+2+3+4+n2.确定性确定性 例：例：L/L/正整数正整数3.有有0个或多个输入个或多个输入4.有一个或多个输出有一个或多个输出5.有效性有效性 例例：（：（l+d )/4算法的表示算法的表示自然语言、伪代码、流程图自然语言、伪代码、流程图自然语言：就是指人自然语言：就是指人们日常使用的语言，们日常使用的语言，可以是汉语、英语或可以是汉语、英语或其它语言。其它语言。伪代码：是用介于自伪代码：是用介于自然语言和计算机语言然语言和计算机语言之间的文字和符号之间的文字

3、和符号（包括数学符号）来（包括数学符号）来描述算法。描述算法。例如：输入三个数，然后输出例如：输入三个数，然后输出其中最大的数可用其中最大的数可用如下的伪代码表示如下的伪代码表示Begin（算法开始） 输入 A，B，C IF AB 则 AMax 否则 BMax IF CMax 则 CMaxPrint MaxEnd (算法结束)处理框处理框开始、结束框开始、结束框输入、输出框输入、输出框判断框判断框流程线连接点流程图中的基本符号流程图中的基本符号开始框开始框输入变量输入变量A、B和和CAB?Max BMax ACMax？YNMax CN输出变量输出变量C的值的值结束框结束框Y算法的三种基本模式算

4、法的三种基本模式 （1）顺序结构）顺序结构语句语句1语句语句2条件条件语句语句1语句语句2YN（2）选择结构）选择结构条件条件( a )条件条件语句组语句组（3）循环结构）循环结构a) 当型循环当型循环b) 直到循环直到循环YNYN( b )语句组语句组1、计算圆锥体体积的步骤有： 计算底面积s=pir2 输入底面半径r、高h 输出体积v pi=3.1416 计算体积v=sh/3下列选项中，步骤顺序正确的是（A）（B）（C）（D）A巩固练习巩固练习2、下面结论正确的是（ ） A.一个程序的算法步骤是可逆的。B.一个算法可以无止境地运行下去。 C.完成一件事情的算法有且只有一种。D.算法的每一步

5、操作必须是明确的，不能有歧异或模糊。 E.算法执行后一定产生确定的结果。 D E3、下面是解决问题的算法的是（ ） A.打开计算机需先插好电源，再打开显示器，打开主机。 B.斜二测画法需将平行于x轴的长度保持不变，平行于y轴的长度变为原来的一半。 C.求方程012=x的解先移项。 D.建国60周年庆典。 Av算法是方法与步骤，而算法是方法与步骤，而B与与D仅陈述事件，而仅陈述事件，而C虽然是步骤，虽然是步骤，但并不能达到目的，也不是解这个方程的算法。但并不能达到目的，也不是解这个方程的算法。4、在求解“一元二次方程实数根”的算法中，如果方程不存在实数解，也要求输出结果“无实数根”。此要求主要体

6、现了算法特征中的 （ ）A 有穷性B 有输出C 确定性D唯一性B5、某停车场收费标准如下：1小时及以内，收费 5元；超过1小时的，超过部分每小时按15元 收费。用算法描述这一收费标准，合适的算 法流程是 （A）顺序模式 （B）循环模式 （C）选择模式 （D）树型模式C6、某算法的流程图如下所示：输出输出sx0 x0？N NY Y输入输入x x的的值值ss+xss+x结束结束s0s0开始开始输入输入x x的的值值依次输入x的值为5、3、0后，该算法的输出结果为（A）2（B）3（C）5（D）8D7、某算法的自然语言描述与流程图表示分别如下：自然语言 流程图 第第1 1步：输入一个实数步：输入一个实

7、数x x第第2 2步：判断步：判断x x与与0 0的大小的大小关系，若关系，若x0 x0，则，则y=xy=x2 2- -1 1，否则，否则y=2x-1y=2x-1第第3 3步：输出步：输出y y第第4 4步：结束步：结束N NY Y开始开始x x 0?0?输出输出y y结束结束输入输入x x则流程图中空白处理框和处应填入的是（A） y x2 1 x 2x 1（B） y x2 1 y 2x 1（C） y 2x 1 y x2 1（D） x x2 1 y 2x 1B第二节课第二节课上节知识回顾上节知识回顾开始开始i=10Yi=1 s=0N结束结束输出输出S i=i+1 S=s+11、以上流程图属于（

8、 ）结构2、此流程图属于什么结构？请、此流程图属于什么结构？请描述该流程图的含义？描述该流程图的含义？开始开始输入输入a的值的值结束结束输入输入b的值的值 temp a ab b temp 输出输出a,b的值的值提示：提示： 1、 “”表示给于表示给于 2、temp、a、b表示变量表示变量开始开始输入电的度数输入电的度数dushu如果如果 dushu=50N如果如果 dushu=200YDianfei=dushu * 0.53YDianfei=50 * 0.53+(dushu-50)*0.56NDianfei=50 * 0.53+150*0.56+(dushu-200)*0.63输出输出dia

9、nfei的值的值结束结束3、假如你是电费收费员，、假如你是电费收费员，现在需要向某位住户收取现在需要向某位住户收取电费，以下是一个有关电电费，以下是一个有关电费收费问题的流程图，请费收费问题的流程图，请解释一下收费规则？并说解释一下收费规则？并说明此图属于什么结构？明此图属于什么结构？4：以下程序，当输入：以下程序，当输入a,b,c的值分别为的值分别为10，20，30时，输出结果时，输出结果为多少？该流程图完成了什么功能？为多少？该流程图完成了什么功能？. . 某算法的流程图如下所示：某算法的流程图如下所示：开始开始结束结束输出输出c c输出输出b bcbcb？N NY Y输入输入a a、b

10、b的值的值ca+5ca+5当输入当输入a a和和b b的值分别为的值分别为3 3、6 6时，该算法的输出结果为时，该算法的输出结果为（A A）3 3（B B）6 6（C C）8 8（D D）9 9. .某旅游景点规定，身高在某旅游景点规定，身高在1.21.2米以下的儿童免票米以下的儿童免票，身高在身高在1.21.2米米1.51.5米的儿童购买半价票，身高超过米的儿童购买半价票，身高超过1.51.5米的购全价票。下图米的购全价票。下图所示算法用于根据身高判断购票情况：所示算法用于根据身高判断购票情况：开始开始结束结束h1.2?h1.2?N NY Yh1.h1.5?5?Y YN N用于输出用于输出

11、“购全价票购全价票”的的图框编号是图框编号是（A A）（B B）（C C）（D D）D开始开始输入输入n的值的值s=1i=1i=n?结束结束输出输出s的值的值Ns=s*ii=i+1Y练习练习5、当输入、当输入n的值为的值为5时，时，输出输出s的值为多少？该流程图完的值为多少？该流程图完成的什么功能？成的什么功能？练习练习6、将流程图中、将流程图中 改为：改为： 流程图的功能一样吗？如果不一流程图的功能一样吗？如果不一样，当样，当n=5时，结果变成多少？时，结果变成多少？s=s*ii=i+1i=i+1s=s*i1*1*2*3*4*5=1201*2*3*4*5*6=720第二章第二章 算法实例算法

12、实例本章通过求解几个应用问题实例，介绍几种常用的算法设计方法，本章通过求解几个应用问题实例，介绍几种常用的算法设计方法，如：（如：（1 1）用枚举和解析方法设计算法）用枚举和解析方法设计算法 （2 2）在排序和查找中常用的几种简单算法）在排序和查找中常用的几种简单算法 排序排序冒泡排序冒泡排序选择排序选择排序查找查找顺序查找顺序查找对分查找对分查找一、枚举算法一、枚举算法 枚举算法就是把各种可能情况都考虑到，并对全部可能枚举算法就是把各种可能情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果。求的结果。例例

13、1：一张单据上有一个：一张单据上有一个5位位数，其百位与十位数变得模数，其百位与十位数变得模糊不清（如图），但知道这糊不清（如图），但知道这个个5位数是位数是37或或67的倍数。的倍数。现在要设计一个算法，找出现在要设计一个算法，找出所有满足这些条件的所有满足这些条件的5位数，位数，并统计这些并统计这些5位数的个数位数的个数NO.25 6算法分析：算法分析：（1）在这个）在这个5位的模糊处，依次填入位的模糊处，依次填入00、01、0299这这100个数，从而产生出全部可能解个数，从而产生出全部可能解25006、25016、25026 25996；（2）使用循环结构模式，让变量）使用循环结构模式

14、，让变量j依次取依次取0到到99，那么，那么25006+j*10就是一个可能解（用变量就是一个可能解（用变量n表示）；表示）；（3）对任一可能解）对任一可能解n，判断是否能被，判断是否能被37或或67整除，若是整除，若是就是一个真正解。就是一个真正解。流程图：流程图：j100j100？N NY Y输出输出: :真正解真正解n n的的值值nn25006+j25006+j* *1010结束结束开始开始计数器设初值：计数器设初值：c 0c 0j 0j 0N N是是3737或或6767的倍数？的倍数？Y Y计数器：计数器：c c+1输出输出c c的值的值N Nj j+1j j+1二、解析算法二、解析算

15、法 解析算法是指用解析的方法找出表示问题的前提条件与解析算法是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。现问题求解。例例2：计算：计算n个电阻并联后的总电阻个电阻并联后的总电阻算法分析：算法分析：（1）R1R22个电阻并联图R1R2Rnn个电阻并联图（2）n个并联电阻的总电阻值个并联电阻的总电阻值R的倒数等于参与并联的各个电的倒数等于参与并联的各个电阻值的倒数之和即：阻值的倒数之和即：RR21R11Rn=11+流程图：流程图：设设R为总电阻为总电阻 r为输入的电阻值为输入的电阻值数据

16、输入数据输入完？完？N NY YR R+1/rR R+1/r结束结束开始开始初始准备：初始准备：R 0R 0Y Y输出输出R R的值的值N N输入一个输入一个r r值值r=0r=0？输出输出: :”无连接无连接“三、排序三、排序 把杂乱无章的数据变为有充的数据，这一过程即称为排序。是把杂乱无章的数据变为有充的数据，这一过程即称为排序。是计算机程序中经常要用到的基本算法。计算机程序中经常要用到的基本算法。（1）冒泡排序：）冒泡排序： 在一列数据中把较小（较大）的数据逐次向上推移的一种排序技术。在一列数据中把较小（较大）的数据逐次向上推移的一种排序技术。例：将例：将27、36、32、18用冒泡法从小到大排序用冒泡法从小到大排序第一遍：第一遍：27363218273618322718363218273632第二遍：第二遍：18273632182732361827323618273236第二遍：第二遍：1827323618273236例例1、某烹饪比赛中，位专家评委给某厨师的打分分别、某烹饪比赛中，位专家评委给某厨师的打分分别是，。采用冒泡排序是，。采用冒泡排序算法对其进行排序，若完成第一遍时