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

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

1、算法与程序设计,第一章 算法和算法的表示,算法的概念,1、算法的概念 所谓“算法”，就是解题方法的精确描述。“算法”是用来表示解决问题的方法和步骤，它是由有限个步骤组成的。从更广义的角度来看，并不是只有“计算”的问题才有算法。,乐谱,菜谱,广播操图解,2.算法实例,华罗庚在数学普及读物统筹方法平话及补充中，以“泡茶”为例，阐明了设计和选择合适的、优化的算法的重要性。,算法的特性,1.有穷性 例：1+2+3+4+n2.确定性 例：L/正整数3.有0个或多个输入4.有一个或多个输出5.有效性 例：（l+d)/4,算法的表示,自然语言、伪代码、流程图,自然语言：就是指人们日常使用的语言，可以是汉语、

2、英语或其它语言。伪代码：是用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。,例如：输入三个数，然后输出其中最大的数可用如下的伪代码表示Begin（算法开始）输入 A，B，C IF AB 则 AMax 否则 BMax IF CMax 则 CMaxPrint MaxEnd(算法结束),处理框,开始、结束框,输入、输出框,判断框,流程线,连接点,流程图中的基本符号,开始框,输入变量A、B和C,AB?,Max B,Max A,CMax？,Y,N,Max C,N,输出变量C的值,结束框,Y,算法的三种基本模式,（1）顺序结构,语句1,语句2,条件,语句1,语句2,Y,N,（2）选择

3、结构,条件,(a),条件,语句组,（3）循环结构,a)当型循环,b)直到循环,Y,N,Y,N,(b),语句组,1、计算圆锥体体积的步骤有：计算底面积s=pir2 输入底面半径r、高h 输出体积v pi=3.1416 计算体积v=sh/3下列选项中，步骤顺序正确的是（A）（B）（C）（D）,A,巩固练习,2、下面结论正确的是（）A.一个程序的算法步骤是可逆的。B.一个算法可以无止境地运行下去。C.完成一件事情的算法有且只有一种。D.算法的每一步操作必须是明确的，不能有歧异或模糊。E.算法执行后一定产生确定的结果。,D E,3、下面是解决问题的算法的是（）A.打开计算机需先插好电源，再打开显示器，

4、打开主机。B.斜二测画法需将平行于x轴的长度保持不变，平行于y轴的长度变为原来的一半。C.求方程012=x的解先移项。D.建国60周年庆典。,A,算法是方法与步骤，而B与D仅陈述事件，而C虽然是步骤，但并不能达到目的，也不是解这个方程的算法。,4、在求解“一元二次方程实数根”的算法中，如果方程不存在实数解，也要求输出结果“无实数根”。此要求主要体现了算法特征中的（）A 有穷性B 有输出C 确定性D唯一性,B,5、某停车场收费标准如下：1小时及以内，收费 5元；超过1小时的，超过部分每小时按15元 收费。用算法描述这一收费标准，合适的算 法流程是（A）顺序模式（B）循环模式（C）选择模式（D）树

5、型模式,C,6、某算法的流程图如下所示：,依次输入x的值为5、3、0后，该算法的输出结果为（A）2（B）3（C）5（D）8,D,7、某算法的自然语言描述与流程图表示分别如下：自然语言 流程图,第1步：输入一个实数x第2步：判断x与0的大小关系，若x0，则y=x2-1，否则y=2x-1第3步：输出y第4步：结束,N,Y,开始,x 0?,输出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 1,B,第二节课,上节知识回顾,开始,i=10,Y,i=1 s=0,N,结束,输出

6、S,i=i+1 S=s+1,1、以上流程图属于（）结构,2、此流程图属于什么结构？请描述该流程图的含义？,提示：1、“”表示给于 2、temp、a、b表示变量,3、假如你是电费收费员，现在需要向某位住户收取电费，以下是一个有关电费收费问题的流程图，请解释一下收费规则？并说明此图属于什么结构？,4：以下程序，当输入a,b,c的值分别为10，20，30时，输出结果为多少？该流程图完成了什么功能？,.某算法的流程图如下所示：,开始,结束,输出c,输出b,cb？,N,Y,输入a、b的值,ca+5,当输入a和b的值分别为3、6时，该算法的输出结果为,.某旅游景点规定，身高在1.2米以下的儿童免票，身高在

7、1.2米1.5米的儿童购买半价票，身高超过1.5米的购全价票。下图所示算法用于根据身高判断购票情况：,用于输出“购全价票”的图框编号是,D,练习5、当输入n的值为5时，输出s的值为多少？该流程图完成的什么功能？,1*1*2*3*4*5=120,1*2*3*4*5*6=720,第二章 算法实例,本章通过求解几个应用问题实例，介绍几种常用的算法设计方法，如：（1）用枚举和解析方法设计算法（2）在排序和查找中常用的几种简单算法,排序,冒泡排序,选择排序,查找,顺序查找,对分查找,一、枚举算法,枚举算法就是把各种可能情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果

8、。,算法分析：,（1）在这个5位的模糊处，依次填入00、01、0299这100个数，从而产生出全部可能解25006、25016、25026 25996；（2）使用循环结构模式，让变量j依次取0到99，那么25006+j*10就是一个可能解（用变量n表示）；（3）对任一可能解n，判断是否能被37或67整除，若是就是一个真正解。,流程图：,二、解析算法,解析算法是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。,流程图：设R为总电阻 r为输入的电阻值,三、排序,把杂乱无章的数据变为有充的数据，这一过程即称为排序。是计算机程序中经常要用到的基本算

9、法。,（1）冒泡排序：在一列数据中把较小（较大）的数据逐次向上推移的一种排序技术。,例：将27、36、32、18用冒泡法从小到大排序,第一遍：,第二遍：,第二遍：,例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）

10、35，48，88，110，64（D）35，48，64，88，110,（2）选择排序算法：是对冒泡排序的改进。这种方法是在参加排序数组的所有元素中找出最小（或最大）的元素，使它与第一个元素中的数据相互交换位置，然在余下的元素中找出最小（或最大）的，与第二个元素中的数据交换位置，以此类推，直到所有元素成为一个有序的序列。,如上例：将27、36、32、18用选择排序算法从小到大排序,例、用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为165，168，178，175，171，则下列选项中可能性是原始数据序列的是（）（A）175，178，168，165，171（B）178

11、，168，165，175，171（C）165，178，168，175，171（D）165，168，171，175，178,B,四、查找,（1）顺序查找,（2）对分查找：非常高效，但被查找的数据必须是有序,例：以下16个数据中，以对分法查找35的过程：,12345678910111213141516,12345678910111213141516,12345678910111213141516,12345678910111213141516,（1）,（2）,（3）,（4）,标号 数字,标号 数字,标号 数字,标号 数字,例、7位学生的身高（单位:cm）从高到低依次为：178，177，175，17

12、2，170，165，162。用对分查找法找到178所需要的查找次数是（A）1（B）2（C）3（D）4,C,巩固练习：,1、统计个位数是6，且能被三整除的三位数共有多少个，可采用的算法是（）（A）查找算法（B）枚举算法（C）解析算法（D）排序算法,B,2计算两个并联电阻总电阻值的算法如下：输入两电阻R1、R2 的值计算总电阻R=,输出总电阻R 上述算法属于,3.7位学生的身高（单位:cm）从高到低依次为：178，177，175，172，170，165，162。用对分查找法找到178所需要的查找次数是,（D）4,（C）3,（B）2,（A）1,4、使用选择排序的方法对数据8，6，1，9，4从大到小排

13、序，需要进行数据互换的次数是（A）5（B）2（C）3（D）4,D,5、在有序单词序列：As、Book、Door、English、Floyd、Good、Hello、Sun中，用对分查找法找到单词“Good”所需要的查找次数是（A）1（B）2（C）3（D）4,B,6、利用对分查找，在某校报名参加学生会主席竞选的学号列表20080101，20080135，20080238，20080342，20080450，20080558，20080633，20080708，20080846，20080910中，查找学号为20080846学生的过程中，依次被访问到的学号是（）,（A）20080450，200807

14、08，20080846（B）20080450，20080708，20080910，20080846（C）20080558，20080708，20080846（D）20080558，20080708，20080910，20080846,7、某书店第30周每天图书的销售量（单位：册）存放在数组d中，如下表所示：,若采用冒泡排序算法对这些数据进行升序排列，那么在完成第一遍的加工时，变量d(1)、d(7)的值分别为A 122 502B 201 618C 98 618D 98 502,6、小明在一次商品竞猜游戏中，采用了对分查找的算法进行猜价。当主办方出示了一件元以内的商品后，小明第次猜价时猜中了商品。

15、该商品的价格可能性是,（A）（B）（C）（D）,7、某查找算法的流程图如左下列对该流程图的分析，正确的是：（A）采用顺序查找算法在数组a中查找20，找到则输出“20”（B）采用对分查找算法在数组a中查找20，找到则输出“Y”（C）若数组a中存在20，则查找次数一定小于10（D）若数组a中不存在20，则查找次数一定为10,第三节课,第三章 VB程序设计初步,一、基本数据类型、常量和变量,1、数据类型,2、常量,是指在程序执行过程中其值不能改变的存储单元或数据。,例：下面各种不同类型的常量整数常量：12 1024实数常量：3.1416-0.25字符串常量：Basic 0.618 逻辑常量：True

16、 Flase,常量在程序设计中用Const语句加以说明。,Const PI=3.14159,3、变量,是指在程序执行过程中其值可以改变的存储单元或数据。,变量名由字母、数字和下划线等字符组成，但必须以字母开头，在变量名中对大小写字母是不加区分的。,变量在程序设计中用Dim语句加以说明。,其常用格式为：Dim 变量名 As 变量的类型,例：Dim count As Integer count是整数类型的变量 Dim x As Double,y As Double x和y都是双精度实数类型的变量 Dim Name As String Name是字符串类型的变量,4、数组变量,主要用来存储一批同类型

17、的数据。,组成数组的每一个变量被称为数组的元素。在实际应用中，一维数组用来存储数据的一个线性序列，二维数组用来存储一个二维数据（即表格）,一维数组常用说明形式：,Dim 数据变量名（A1 TO A2）As 变量的类型注：A1 和 A2是下标的下界与上界，都是常量,例：Dim score(1 To 50)As Integer 说明score是由50个整数变量构成的一个一维数组变量，即它有50个元素score（1）、score（2）、score（3）、score（49）、score（50）,二维数组常用说明形式：,Dim 数据变量名（A1 TO A2，B1 TO B2）As 变量的类型注：A1 和

18、 A2是第一个下标的下界与上界，B1 和 B2是第二个下标的下界与上界，它们都是常量。,例：Dim price(1 To 50,1 To 8)As Double 说明price是个二维数组，可以用来存储20行，每行中有8个双精度实数数据。一般地，price（i,j）是指数组第一i行第j列上的元素。,例1：在VB中，用变量h1 存储人民币与美元的汇率（如：6.348），则变量h1的数据类型应说明为（）,（A）Integer（B）Single（C）Date（D）Long,B,例2：在Visual Basic中，用变量code存储学生的借阅卡编码(如“CH20130036”)，则变量code的数据类

19、型应说明为（A）Integer（B）Single（C）String（D）Date,C,例3：在VB中，下列能作为变量名的是（）,（A）End（B）b7（C）2a（D）pass_1,D,5、VB常用的标准函数,常用数学函数,常用类型转换函数和字符串函数,6、VB中的基本运算和表达式,算术运算符,关系运算符,逻辑运算符,逻辑“非”运算：计算结果是原始数据的逻辑值的相反,逻辑“与”运算：仅当运算符两边的表达式的逻辑值都为真时，计算结果值才为真，否则计算结果总是假。,逻辑“或”运算：仅当运算符两边的表达式的逻辑值都为假时，计算结果值才为假，否则计算结果总是真。,表达式：,一个表达式中可能包算术运算、关

20、系运算和逻辑运算等多种基本运算，以及这些基本运算所涉及的数据（常量和变量）,巩固练习：,（1）写出下列数学式的VB表达式：,（2）设a=2,b=3,c=4,d=5,表达式ab AND cc 的值是,（A）True（B）Flase（C）-1（D）1,B,（3）在物理学中，两个物体质量分别为m1和m2，计算它们之间的万有引力可以用公式：F=G，若用VB语句来表示，正确的是,（A）F=Gm1m2/r*2（B）F=Gm1m2/r2（C）F=G*m1*m2/r2（D）F=G*m1*m2/r*r,c,（4）表达式Abs(-3.6)*Sqr(100)的值是,（A）-360（B）360（C）-36（D）36,

21、D,（5）与数学表达式“2n-10且2n-11”对应的VB表达式是,（A）2n-10 and 2n-11（B）2n-10 and 2n-11（C）2*n-10 or not 2*n-1=1（D）2*n-10 and 2*n-11,D,该表达式值为False该表达式值的数据类型是Boolean 因为b*b-4*a*c结果为8，所以该表达式值不存在,（6）设a=3,b=2,c=1,下列关于VB表达式b*b-4*a*c=0的说法正确的有,（A）（B）（C）（D）,A,（7）下棋时要通过掷骰子来随机确定走棋步数。骰子的六个面上标有数字1至6，下面能表示产生1至6之间的随机整数的表达式是,（A）Rnd(

22、1)*6（B）Rnd(1)*5+1（C）Int(Rnd(1)*6)+1（D）Int(Rnd(1)*5)+1,C,（8）在VB中，表达式Len(-100)+100的值是,（A）0（B）104（C）200（D）-100100,B,7.语句,语句是一种用来描述或规定计算机应该完成的一串操作的（宏）命令。一行上相邻的两个语句之间用冒号（：）分隔。,如:A=VB程序设计 Text1.Text=A,Dim v As IntegerDim book As StringDim sum As Singlev=26v=v+1book=VB程序设计 sum=v*123.4+56.7,（一）赋值语句,给变量赋值,格式

23、：变量名=表达式,设置对象的属性,格式：对象名.属性=表达式,例：下列能作为赋值语句的是（）,（A）10=i（B）i+j=10（C）t=Flase（D）i=10-j And j=2,c,例：有如下程序段 a=360 b=100 c=a+Str(b)该程序段运行后，c的值为（）,（A）260（B）360-100（C）460（D）360100,B,先对条件测试，根据测试的结果选择执行不同的分支,If-Then-Else-End If结构语句,Visual Basic 程序设计,（二）选择语句,1.IfThen 结构,格式:If 条件 Then(A组语句)EndIf,If条件语句,例：If scor

24、e=60 Then Print score Print 祝贺你考试通过！End If Print“继续努力！”,执行规则：若条件成立,执行A组语句;条件不成立,跳过A组语句.条件：可以为逻辑变量、关系表达式或逻辑表达式,例：输入两个数，分别放在x和y变量中，比较它们大小，然后将大数放在x中，小数放在y中。,Dim x as integerDim y as integerx=val(Text1.text)y=val(Text2.text)If x y Then y=x x=yEnd IfPrint x,y,t=x x=y y=t,例：If score=60 Then Print“祝贺你考试通过！

25、”Else Print“考试未通过.”End If Print 继续努力！,2.IfThenElse 结构,格式：If 条件 Then A组语句 Else B组语句 END If,执行规则:条件成立,执行A组语句,条件不成立,执行B组语句,例：输入二级考试成绩，要求显示对应三级制的评定。评定条件为：,3.IfThenElseIf 结构,Mark=Val(Text1.Text)If Mark=90 Then Print 优ElseIf Mark=60 Then Print“通过Else Print“未通过End If,格式：If 条件1 Then（A组语句）ElseIf 条件2 Then（B组语

26、句）ElseIf 条件3 Then（C组语句）Else（n组语句）End If,例：有如下Visual Basic程序段：a=360 b=Val(a)c=Len(a)If b c Then Label1.Caption=取数值 Else Label1.Caption=取字符 End If该程序段运行后，在标签Label1上显示的是_。,（三）循环语句,循环:是在指定的条件下多次重复执行一组语句,For-Next循环结构语句,Do-Loop循环结构语句,1.While循环,Do While 循环体 Loop,执行过程:（先判断，后执行）先判断循环条件,若为真:执行循环体,再判断循环条件否则，跳过

27、循环体,执行Loop之后语句,DoLoop循环结构语句,Do While 循环体 Loop,例1:求1+2+3+4+10的和.,Dim I As Integer Dim s As Integer I=1:s=0Do WhileLoopPrint I,s,s=s+I,I=10,I=I+1,1.While循环,I=11:,(1)循环体执行了几次?(2)没有I=1会怎样?(3)将Print语句移到Loop的 前面结果怎样?(4)I先赋值为11,结果如何?,For I=10 To 1 Step-1,程序代码：Dim I As Integer Dim s As Integer s=0 For I=1 T

28、o 10 step 1 Next I Print I,s,例1:求1+2+3+4+10之和.,分析:重复过程(循环体):ss+I初值、终值和增量:1、10、1,循环体的执行次数是多少?输出的I、S的值是多少?,s=s+I,For循环结构语句,For 循环变量=初值 TO 终值 Step 步长 语句块 Next 循环变量,初值与终值换位 可以吗？,注意：初值(e1)、终值(e2)、步长(e3)必须是数值型。若步长为正，初值终值；缺省为默认为1；在已知循环次数时使用For循环，循环次数为：循环次数=Int(终值-初值)/步长)+1 组成循环体的语句块可以是一条或多条语句；,S1=0S2=0For

29、I=1 To 1000 S1=S1+INext I,计算11000的奇数和与偶数和 方法一：方法二：,Step 2,For I=1 To 1000 Step 2 S2=S2+INext IPrint S1,S2,2,S1=0S2=0For I=1 To 1000 If I mod 20 then S1=S1+I Else S2=S2+I End IfNext IPrint S1,S2,For循环结构语句,例1：在包含100个元素的数组a中，寻找最小值的 Visual Basic程序段如下：min=a(1)变量min用于存储最小值For i=2 To 100,Next I则方框中最合适的语句是（

30、A）If a(i)min Then min=a(i)（D）If a(i)min Then a(i)=min,A,s=0:t=1:g=2Do While g=6 t=t*g s=s+t _Loop,s=0:t=1For g=2 To 6 t=t*g s=s+tNext g,（A）g=2（B）g=6（C）g=g+1（D）g=g+2,例2：为使左、右框内的Visual Basic程序段实现相同的功能，可在左框内划线处填写的代码是,c,1、以下是一段Visual Basic程序:If I=1 Then X=X+1 Else X=X*2 End If它的基本结构属于().A、顺序结构 B、选择结构C、循

31、环结构D、树型结构,综合练习,B,2、下列程序段运行后，变量Value的值是（）x=20If x=10 Then Value=5*xElse Value=4*xEnd IfA、100 B、80 C、90 D、70,A,3、下列程序段运行后,m的值为()A=2:b=1:c=5If A b Then m=A Else m=bIf c m Then m=c选项：A、1 B、2 C、5 D、提示错误，无答案,A,5、以下Visual Basic程序的功能是：计算表达式1+2+4+8+16+32+1024的值，并在文本框Text1中输出结果。为了实现这一功能，程序中划线处的语句应更正为_。Private

32、 Sub Command1_Click()Dim a As Integer,s As Longs=0a=1Do While a=1024 s=s+a a=a+2LoopText1.Text=Str(s)End Sub,a=a*2,6、下列Visual Basic程序的功能是：计算表达式12+42+72+972的值，并在文本框Text1中输出表达式的值。为了实现这一目标，程序中划线处填空。Private Sub Command1_Click()Dim sum As LongDim i As Integersum=0For i=1 To 97 Step _ sum=sum+_Next iText1.Text=Str(sum)End Sub,3,i2,7、以下Visual Basic程序的功能是：找出自然数1-100之间被3整除的数，并在文本框Text1中输出这些数的累加和。为了实现这一功能，程序中划线处的语句应更正为_。Private Sub Command1_Click()Dim i As Integer,sum As Integersum=0For i=1 to 100 If i Mod 3=0 Then sum=sum+3Next iText1.Text=Str(sum),sum=sum+i,