算法与程序设计示例与练习

1、第一部分：顺序结构三、用编程语言描述用计算机语言来描述算法。特点：计算机可以识别并执行，但是不同型号的计算机或编程语言指令和代码则不尽相同。VB主要代码如下：Dim R As DoubleDim s As DoubleR = TextBox1.Text 此句等同于伪代码中input R,为输S = 3.14 * R * R 入语句Label2.Caption = "圆面积为：" & S 此句等同于伪代码中print ，为输出语句四、用伪代码描述：伪代码是介于流程图和编程语言间的一种算法描述方式。特点：不能为计算机识别，但却可以十分明确的描述算法。Read(r) 这句

2、也可写做input(r)Sß3.14*r*r 也可写作s=3.14*r*rWrite(“圆面积为S”,S) 这句也可写做print(“圆面积”,S)注：以后教学中如不特别注明代码类型，蓝色代码为伪代码，红色则为VB代码。例一：输入一个圆的半径，求其面积：一、 自然语言方式用人的语言描述算法。特点：计算机无法识别，但人容易理解，但不精确。(比如一盒酥，也可以让人理解成一人一口酥)1 输入一个圆的半径R2 面积S=PI*R*R3 输出圆的面积S二、 流程图方式用图形符号描述算法。特点：计算机无法识别，但对人而言则显得精确和直观。输入圆半径R圆面积S=PI*R*R输出面积SEndstart

3、练习：见算法设计p10上图1.3的流程图，写出伪代码，并尝试用VB来实现算法。伪代码：Input aInput bS=a*bPrint S提示：vb 主要代码如下，Dim a, b, s As Integera = TextBox1.Textb = TextBox2.Texts = a * bLabel3.Caption = Label3.Caption & s练习2：输入两个数分别给变量a,b;试写出一个交换a,b变量值的算法，要求用流程图和伪代码描述算法。伪代码如下：Input A,BC=AA=BB=CPrint a,b第二部份：分支结构例二：从键盘输入二个数，比较后，输出较大者。

4、算法描述：输入a,ba>b输出a的值输出b的值EndstartTRUEFALSE伪代码：Input a,bIf a>b thenPrint aElsePrint bEnd ifVb主要代码VB主要代码如下：Dim a As IntegerDim b As Integera = TextBox1.Textb = TextBox2.TextIf a > b Then Label1.Caption = aElse Label1.Caption = bEnd If例三：求一元二次方程的解（算法P19）start输入系数a,b,cd=b*b-4*a*cd>=0d<>0

5、输出无实数解X1=(-b)/(2*a)x1=(-b)+sqr(d)/(2*a)x2=(-b)-sqr(d)/(2*a)输出二个解x1,x2输出一个解：x1endFTFT注：求平方根可以用sqr(),或sqrt()函数；部份函数说明部份运算符及函数作用示例sqr(),sqrt()求平方根Sqrt(4)=2mod求余数运算符，或取模运算符7 mod 2=1Int()取整函数(不四舍五入)Int(4.96)=4Abs()取绝对值函数Abs(-5)=5求几次方23=8 , 34=81sin(),cos().三解函数Sin(90)=1伪代码如下：Input a,b,cd=a*a-4*a*cif d>

6、;=0 thenif d<>0 thenx1=(-b+sqr(d)/(2*a)x2=(-b-sqr(d)/(2*a)print x1,x2elsex1=(-b)/(2*a)end ifelseprint “无实数解”end if练习：地铁票价问题：如果从出发地到目的地经过的站数不超过3站，则票价为10元；如果超过3站，则票价在10元的基础上，每多经过一站则增加2元。画出流程图并写出伪代码。Input xIf x>3 thenY=10+(x-3)*2ElseY=10End ifPrint y(试一试：将此题用VB来实现)Private Sub CommandButton1_Cl

7、ick()Dim x, y As Integerx = InputBox("请输入一个站数", "输入站数") 注意input语句用法If x > 3 Then y = 10 + (x - 3) * 2Else y = 10End IfLabel1.Caption = "票价为：" & yEnd Sub练习：西瓜价格为1.2元/千克,若一次购买大于100千克小于200千克着价格为0.9元/千克;若一次购买200千克及以上着价格为0.8元/千克;要求(1):输入西瓜重量(千克),计算并输出应付金额。要求(2):写出伪代码补

8、充：IF语句的另一种简化写法（无else语句）第三部份 循环I. 当循环型Do loop 语句的格式格式一：Do while <条件>循环体Loop功能：Do while loop语句，当条件表达式为true时，执行循环体，否则退出循环。特点：先判断，后循环（存在0次循环的可能）II. 直到循环型功能：Do loop until语句，执行循环体，当条件表达式为false时，继续执行，否则退出循环。特点:先循环再判断（最少会进行一次循环）当循环示例例四：编程计算s=1+2+3+5s=0i=1VB主要代码如下：(此处示例的是从1加到n,n是键盘输入的)Dim i, s, n As In

9、tegern = TextBox1.Texti = 1s = 0Do While i <= n s = s + i i = i + 1LoopLabel2.Caption = "从1加到" & n & ",结果为" & sdo while i<=5s=s+ii=i+1loopprint s说明：上图先用加到五以简化分析，上面的表格是分析算法的一种手段，叫列表法，以跟踪并分析算法流程的功能。在列表中，要注意每一次循环时，每个变量是如何变化的。变量说明：i:计数器（初值为1，每循环一次值就加1）s:累加器，每循环一次，其原

10、来的值就加上i;思考：如果将这题改为为1+2+3.+100，则流程图中改如何改动？练习：如果题改为求1*2*3*100，求结果，例出流程图和写出伪代码。练习：求1+1/2+1/3+1/4+.前20项之和，写出流程图及伪代码直到循环型示例例五:从键盘输入一串密码，如果正确（假定密码是”abc123”）,则显示“你好”，否则要求重新输入。START输入密码密码正确？输出“你好”EndFTDoInput passLoop until pass=”abc123”Print “你好”VB实现Private Sub CommandButton1_Click()Dim pass As StringDo pa

11、ss = InputBox("请输入密码", "密码验证")Loop Until pass = "abc123"Label1.Caption = "你好"End Sub算法实例:(1) 枚举算法例题一： 寻找并打印1到1000以内的所有能够被3整除的自然数。基础知识回顾： Mod:求余算术运算符 示例:9 mod 2=15 mod 7=56 mod 3=0 i=1Do while i<=1000if i mod 3 = 0 thenprint iend ifi=i+1loop观察并回答1、这个题目中循环共进行

12、了多少次？2、判断共进行了多少次？总结 这个程序对从1到1000每一个数都进行了判断。即假设每一个数都是可能的解，对每一个可能的解都作判断，最后输出正确的解。 VB主要代码如下:Dim N, i As IntegerN = TextBox1.TextTextBox2.Text = "" 想一想:为什么要加上这步？如果去掉会怎么样？i = 1Do While i <= N If i Mod 3 = 0 Then TextBox2.Text = TextBox2.Text & i & vbCrLf vbCrLf代表换行符 End If i = i + 1L

13、oop注意：此题中text2要设置如下属性属性名值LockedTrueMultiLinetrueScrollBars2-fmScrollBarsVertical例题二一张单据上有一个5位数号码，它的千位和百位的数字已被涂抹得模糊不清，如下所示； 另一方面，我们知道这个数能被57或67除尽。请设计一个算法，找出该单据原有的可能号码及个数。提出问题：1、总共有多少可能的解，这些解分别是什么？2、如何检验正确的解？3、这种把所有可能情况都列举出来并检验的求解算法称为枚举法；反之如果可以把条件和结果之间的关系用公式直接表示的算法，称为解析法，比如之前讲过的地铁票价问题等。 分析： (1) 在这个5位数

14、的千位和百位上，填上2个数字，则可以形成一个可能的5位数解 n （1004719947）。 (2) 将这未知的2个数字看作一个二位数 i ， 则 n=10047+i*100，而i 的取值范围是 0,99 。 (3) 判断当 i 取遍 0,99 时所得的每个 n 是否是真正解， 即 n 是否能被 57 或 67 整除。 (4) 若 n 是真正解，则输出 n 的值，并在计数器 C (记录解的个数) 中计数。计数器 C 置初值: C=0i=0i<100n=10047+i*100 n mod 57=0 or n mod 67=0计数器C记数: C=C+1i=i+1NYY开始结束输出真正解n的值输

15、出计数器C的值Nc=0i=0do while i<=99n=10047+i*100if n mod 57=0 or n mod 67=0 thenprint nc=c+1end ifi=i+1loopPrint cEnd 第四部份 基本算法实现数组变量：是由多个普通变量组成的一个顺序；数组中的所有变量拥有共同的名称，用下标来区分数组中的每一个成员，而数组中的成员又称为数组元素：数组的定义：Dim a(10) as integer定义一个变量名为a的数组，有十个元素组成；数组元素的引用：a(1)=3 数组中的第一个元素赋值为3a(2)=5 数组中的第二个元素赋值为5a(3)=a(1)+a(

16、2) 数组中第三个元素的值为前二个元素之和，值为8例1：输入十个整数，用数组保存，打印出数组顺序并求出总和；VB代码：Dim a(10) As IntegerDim i, s As Integeri = 1s = 0Do While i <= 10 a(i) = InputBox("请输入一个数：") s = s + a(i) i = i + 1Loopi = 1Do While i <= 10 Label1.Caption = Label1.Caption & a(i) & "," i = i + 1LoopLabel2.C

17、aption = s例2：对数组a求最大值（假设有五个元素）Vb代码：Dim a(5) As Integera(1) = 3a(2) = 6a(3) = 7a(4) = 5a(5) = 1上面代码定义仅仅定义一个五元素数组，此部份不包含于流程图内Dim i, max As Integeri = 2max = a(1)Do While i <= 5 If a(i) > max Then max = a(i) End Ifi = i + 1LoopLabel2.Caption = max练习：把上题改成求最小值的话，流程图和代码该如何实现。关于冒泡法排序，以讲解排序思路为主，会说出每轮

18、排序后的情况；而代码不要求掌握；此节的讲解可以采用冒泡法排序.ppt，并辅以全A计划p111页上第20题冒泡法实现主要VB代码:i = 1Do While i <n j = n Do While j > i If d(j) < d(j - 1) Then tmp = d(j) d(j) = d(j - 1) d(j - 1) = tmp End If j = j - 1 Loop i = i + 1Loop(注：n值为数组长度)冒泡法排序算法流程图（升序（由小到大）排列）关于冒泡法的总结：1、 对n 个元素的数组而言，总共需要排n-1轮；2、 第i轮排序时，则需要比较n-i次

19、如果你理解上述两点，对冒泡法就算是掌握了。练习：1、如果把上题改成按降序（由大到小）排列，则修改流程图中何处？如何改？2、有一数组序列：3,9,11,20,35,4,7,6采用冒泡法排序（升序），经过第一轮排序后，其序列是怎样的？对分法对分法是快速查找的一种手段，它的速度远高于一般的顺序查找；但是对分法查找有个前提，就是数组中所有的元素已经排序好；注意，n 值为数组长度VB主要代码：i = 1j =ndo While (i <= j) m = Int(i + j) / 2) If d(m) = myKey Then Label2.Caption = "你要查找的数："

20、 & myKey & "是第" & m & "个数" Exit Sub Else If d(m) < myKey Then i = m + 1 Else j = m - 1 End If End Ifloop Label2.Caption = "该数没有找到！"以书上的数的序列2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92为例进行验证。思考：1，二分法查找为什么快？原因在哪。因为二分法不同于顺序查找，不是一个个的找；而是利用排序后数组的特点，不断缩小查找范围

21、以达到快速查找的目的；2、有一个序列3,9,12,24,46,51,如果要查找9这个数，那么，会折半查找(比较)几次？分析如下：第一次查找时，i=1,j=6,则m=int(1+6)/2)=3而d(3)为12 ,大于被查找数9，所以j=m-1=2然后进行第二次查找：i=1,j=2,m=int(1+2)/2)=1d(1)=3,小于9,故i=m+1=2然后第三次查找，i=2,j=2;m=int(2+2)/2)=2然后d(2)=9,说明找到，并输出此时的数组下标位置m，为2明显看出，在此题中，查找和比较的次数总共是三次，被查找数位置是第二个；请掌所第二题的分析方法，此题会考中必考！附录：一、 vb中数

22、据类型的说明：1、 常量表示一个不变的字面量。如0,123,a,P,”Tom”,3.14.2、 变量变量是用来代表一项数据的名称。电脑会在内存中为每一个定义的变量设置一个存放的位置，根据变量的类型开辟相应大小的空间。变量中的数据可以随程序需要而变化。注意：变量在使用前，必须用一个常量或表达示来赋值。否则程序要么出错，要么出现意想不到的结果。变量的赋值：A=1 把常量1赋给变量AB=A+1 把变量A的值加上1后给B,A+1是一个表达式（表达式是由常量，变量及数学符号组成的一个式子；表达式经过计算后，必须有一个常量值；最简单的表达式可以就是一个常量或变量）C=”Tom”注意：C是一个字符串变量D=

23、99.9999 3、变量的命名长度在255个字符之内第一个字符为英文，其他字符可以使用数字、字母等部分关键字(VB内部使用过的，如mod)不能作为变量名，如print，let，mod等4、变量的类型(部分如下)integer整数2个字节-3276832767long长整数4个字节-231231-1double 浮点数（实数）8个字节 -5.0*103241.7*10308string(字符串型) 如”Peter”,”老港中学” 注意：字符串型的值必须用双引号括起来。Char(字符型)如a,A,0,9 注意：字符型的值必须用单引号括起来。6、变量的定义在VB中变量必须先定义再赋值变量定义的方法:

24、Dim 变量名 as 类型示例Dim name as stringDim age as integerName=”张三”Age=18二、VB中的运算类型（1）算术运数：整数与实数类型的运算a=3运算符含义优先级示例结果乘方1a29-负号2-a-3*乘3a* a* a27/除310/a3.3333333333整除410a3Mod取模510 Mod a1+加610+a13-减7a-10-7(2)关系运算:对数值或字符比较大小的运算运算符含义示例结果=等于"ABCDE"="ABR"False>大于"ABCDE">"AB

25、R"False>=大于等于"bc">="大小"False<小于23<3False<=小于等于"23"<="3"True<>不等于"abc"<>"ABC"True注：关系运算的值只有二种true(成立),false（不成立）1）   如果两个操作数都是数值型，则按其大小比较2）   如果两个操作数都是字符型，则按字符的ASCII码值从左到右一一比较3）   汉字字符大于西文字符(3)逻辑运