算法与程序设计课件3

算法与程序设计第一章算法和算法的表示算法的概念1、算法的概念所谓“算法”，就是解题方法的精确描述。“算法”是用来表示解决问题的方法和步骤，它是由有限个步骤组成的。从更广义的角度来看，并不是只有“计算”的问题才有算法。乐谱菜谱广播操图解2.算法实例华罗庚在数学普及读物《统筹方法平话及补充》中，以“泡茶”为例，阐明了设计和选择合适的、优化的算法的重要性。算法的特性1.有穷性例：1+2+3+4+…+n2.确定性例：L/正整数3.有0个或多个输入4.有一个或多个输出5.有效性例：（l+√d)/4算法的表示自然语言、伪代码、流程图自然语言：就是指人们日常使用的语言，可以是汉语、英语或其它语言。伪代码：是用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。例如：输入三个数，然后输出其中最大的数可用如下的伪代码表示Begin（算法开始）输入A，B，CIFAB则A→Max否则B→MaxIFCMax则C→MaxPrintMaxEnd(算法结束)处理框开始、结束框输入、输出框判断框流程线连接点流程图中的基本符号开始框输入变量A、B和CAB?MaxBMaxACMax？YNMaxCN输出变量C的值结束框Y算法的三种基本模式（1）顺序结构语句1语句2条件语句1语句2YN（2）选择结构条件(a)条件语句组（3）循环结构a)当型循环b)直到循环YNYN(b)语句组1、计算圆锥体体积的步骤有：①计算底面积s=pi·r2②输入底面半径r、高h③输出体积v④pi=3.1416⑤计算体积v=s·h/3下列选项中，步骤顺序正确的是（A）②④①⑤③（B）①②③④⑤（C）②①⑤④③（D）①③②④⑤A巩固练习2、下面结论正确的是（）A.一个程序的算法步骤是可逆的。B.一个算法可以无止境地运行下去。C.完成一件事情的算法有且只有一种。D.算法的每一步操作必须是明确的，不能有歧异或模糊。E.算法执行后一定产生确定的结果。DE3、下面是解决问题的算法的是（）A.打开计算机需先插好电源，再打开显示器，打开主机。B.斜二测画法需将平行于x轴的长度保持不变，平行于y轴的长度变为原来的一半。C.求方程012=−x的解先移项。D.建国60周年庆典。A算法是方法与步骤，而B与D仅陈述事件，而C虽然是步骤，但并不能达到目的，也不是解这个方程的算法。4、在求解“一元二次方程实数根”的算法中，如果方程不存在实数解，也要求输出结果“无实数根”。此要求主要体现了算法特征中的（）A有穷性B有输出C确定性D唯一性B5、某停车场收费标准如下：1小时及以内，收费5元；超过1小时的，超过部分每小时按15元收费。用算法描述这一收费标准，合适的算法流程是（A）顺序模式（B）循环模式（C）选择模式（D）树型模式C6、某算法的流程图如下所示：输出sx≠0？NY输入x的值s←s+x结束s←0开始输入x的值依次输入x的值为5、3、0后，该算法的输出结果为（A）2（B）3（C）5（D）8D7、某算法的自然语言描述与流程图表示分别如下：自然语言流程图第1步：输入一个实数x第2步：判断x与0的大小关系，若x≥0，则y=x2-1，否则y=2x-1第3步：输出y第4步：结束NY开始x0?②输出y①结束输入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=1s=0N结束输出Si=i+1S=s+11、以上流程图属于（）结构2、此流程图属于什么结构？请描述该流程图的含义？开始输入a的值结束输入b的值temp←aa←bb←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输出dianfei的值结束3、假如你是电费收费员，现在需要向某位住户收取电费，以下是一个有关电费收费问题的流程图，请解释一下收费规则？并说明此图属于什么结构？4：以下程序，当输入a,b,c的值分别为10，20，30时，输出结果为多少？该流程图完成了什么功能？５.某算法的流程图如下所示：开始结束输出c输出bc≥b？NY输入a、b的值c←a+5当输入a和b的值分别为3、6时，该算法的输出结果为（A）3（B）6（C）8（D）9Ｃ６.某旅游景点规定，身高在1.2米以下的儿童免票，身高在1.2米～1.5米的儿童购买半价票，身高超过1.5米的购全价票。下图所示算法用于根据身高判断购票情况：开始结束②h1.2?NY①h≤1.5?③④YN用于输出“购全价票”的图框编号是（A）①（B）②（C）③（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第二章算法实例本章通过求解几个应用问题实例，介绍几种常用的算法设计方法，如：（1）用枚举和解析方法设计算法（2）在排序和查找中常用的几种简单算法排序冒泡排序选择排序查找顺序查找对分查找一、枚举算法枚举算法就是把各种可能情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果。例1：一张单据上有一个5位数，其百位与十位数变得模糊不清（如图），但知道这个5位数是37或67的倍数。现在要设计一个算法，找出所有满足这些条件的5位数，并统计这些5位数的个数NO.256＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊算法分析：（1）在这个5位的模糊处，依次填入00、01、02……99这100个数，从而产生出全部可能解25006、25016、25026……25996；（2）使用循环结构模式，让变量j依次取0到99，那么25006+j*10就是一个可能解（用变量n表示）；（3）对任一可能解n，判断是否能被37或67整除，若是就是一个真正解。流程图：j100？NY输出:真正解n的值n←25006+j*10结束开始计数器设初值：c0j0N是37或67的倍数？Y计数器：cc+1输出c的值Njj+1二、解析算法解析算法是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。例2：计算n个电阻并联后的总电阻算法分析：（1）R1R22个电阻并联图R1R2Rn…n个电阻并联图（2）n个并联电阻的总电阻值R的倒数等于参与并联的各个电阻值的倒数之和即：RR21R11Rn—=—1——1+++…流程图：设R为总电阻r为输入的电阻值数据输入完？NYRR+1/r结束开始初始准备：R0Y输出R的值N输入一个r值r=0？输出:”无连接“三、排序把杂乱无章的数据变为有充的数据，这一过程即称为排序。是计算机程序中经常要用到的基本算法。（1）冒泡排序：在一列数据中把较小（较大）的数据逐次向上推移的一种排序技术。例：将27、36、32、18用冒泡法从小到大排序第一遍：27363218273618322718363218273632第二遍：18273632182732361827323618273236第二遍：1827323618273236例1、某烹饪比赛中，６位专家评委给某厨师的打分分别是９８，９２，９４，９０，９７，９３。采用冒泡排序算法对其进行排序，若完成第一遍时的结果为：９０，９８，９２，９４，９３，９７，则完成第二遍时的结果是（A）９０，９２，９８，９３，９４，９７（B）９０，９２，９８，９４，９３，９７（C）９０，９２，９８，９４，９２，９７（D）９０，９２，９３，９８，９４，９７A例2、某书店在5所学校流动售书量(单位：本)分别是88，110，48，64，35。采用冒泡排序对其进行排序，若完成第一遍时的结果是：35，88，110，48，64，则完成第二遍时的结果是（A）35，88，110，48，64（B）35，48，88，64，110（C）35，48，88，110，64（D）35，48，64，88，110Ｃ（2）选择排序算法：是对冒泡排序的改进。这种方法是在参加排序数组的所有元素中找出最小（或最大）的元素，使它与第一个元素中的数据相互交换位置，然在余下的元素中找出最小（或最大）的，与第二个元素中的数据交换位置，以此类推，直到所有元素成为一个有序的序列。如上例：将27、36、32、18用选择排序算法从小到大排序27363218183632271827323618273236例、用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为165，168，178，175，171，则下列选项中可能性是原始数据序列的是（）（A）175，178，168，165，171（B）178，168，165，175，171（C）165，178，168，175，171（D）165，168，171，175，178B四、查找（1）顺序查找（2）对分查找：非常高效，但被查找的数据必须是有序例：以下16个数据中，以对分法查找35的过程：1015171822273545485265677285979812345678910111213141516101517182227354548526567728597981234567891011121314151610151718222735454852656772859798123456789101112131415161015171822273545485265677285979812345678910111213141516（1）（2）（3）（4）标号数字标号数字标号数字标号数字例、7位学生的身高（单位:cm）从高到低依次为：178，177，175，172，170，165，162。用对分查找法找到178所需要的查找次数是（A）1（B）2（C）3（D）4C巩固练习：1、统计个位数是6，且能被三整除的三位数共有多少个，可采用的算法是（）（A）查找算法（B）枚举算法（C）解析算法（D）排序算法B2．计算两个并联电阻总电阻值的算法如下：①输入两电阻R1、R2的值②计算总电阻R=2121RRRR③输出总电阻R上述算法属于（A）枚举算法（B）解析算法（C）排序算法（D）查找算法3.7位学生的身高（单位:cm）从高到低依次为：178，177，175，172，170，165，162。用对分查找法找到178所需要的查找次数是（D）4（C）3（B）2（A）14、使用选择排序的方法对数据8，6，1，9，4从大到小排序，需要进行数据互换的次数是（A）5（B）2（C）3（D）4D5、在有序单词序列：As、Book、Door、English、Floyd、Good、Hello、Sun中，用对分查找法找到单词“Good”所需要的查找次数是（A）1（B）2（C）3（D）4B6、利用对分查找，在某校报名参加学生会主席竞选的学号列表20080101，20080135，20080238，20080342，20080450，20080558，20080633，20080708，20080846，20080910中，查找学号为20080846学生的过程中，依次被访问到的学号是（）（A）20080450，20080708，20080846（B）20080450，20080708，20080910，20080846（C）20080558，20080708，20080846（D）20080558，20080708，20080910，20080846Ａ7、某书店第30周每天图书的销售量（单位：册）存放在数组