17-18版算法与程序设计算法的程序实现

1、算法与程序设计算法的程序实现浙江考试标准考试内容考核要求考试属性1.枚举算法及程序实现c加试2.解析算法及程序实现c3.排序算法及程序实现冒泡排序(2)选择排序c4.查找算法及程序实现(1) 顺序查找(2) 对分查找c5.递归算法a6.VB访问Access数据库(1)通过ADO对象连接数据库通过Recordset对象获取数据表中的数据a学竜知识梳理一、枚举算法1 枚举算法的基本思想根据问题的本身性质，出该问题 能的情况，并根据 题目的条件逐一分析、判断是否满足条件，若满足，则它是问题的一个解，从而挑选出符合条件的 。2枚举算法解题的基本思路(1) 确定枚举对象、枚举范围和判断条件。(2) 一一

2、列举可能的解，验证是否是问题的解。 3枚举算法程序实现的三要素。(1) 枚举解时，既不能遗漏任何一个真正解，又不能有重复，用循环语句实 现。(2) 条件判断时，利用问题提供的约束条件筛选、判断解的正确性，用分支 语句实现。(3) 求解形式一般以输出解的内容或进行与解有关的其他计算。二、解析算法1解析算法的基本思想 用解析的方法找出表示问题的前提条件与所求结果之间关系的 ，并通过表达式的计算来实现问题的求解。2解析算法解题的基本思路(1) 建立正确的数学模型，即得出正确的数学表达式。(2) 保证计算过程描述的正确性。用正确合理的 VB 变量、表达式来表示已经得出的数学表达式。 3解析算法程序实现

3、的步骤(1) 运用解析算法分析问题，寻找问题中各要素之间的关系，用表示它们的关系。(2) 写出解决问题的解析步骤，编写程序实现，通过运行程序求得问题的正 确解。三、冒泡排序1 冒泡排序基本思想是在待排序的数据中，先找到最小 (大)的数据将它放到最前面，再 从第二个数据开始，找到第二小 (大)的数据将它放到第二个位置，以此类推，直 到只剩下最后一个数据为止。2冒泡排序的实现要素 (1)将数据存放在数组中，确定数组的名称、元素个数。(2) 比较与交换进行，在冒泡排序中，第i遍排序比较n i次，最多交换n i次。(3) 强调素的比较和交换。3.冒泡排序的程序实现(1) 从后向前实现冒泡排序从后向前实

4、现冒泡排序的程序结构：-让i从1到n 1循环让j从n到i + 1循环步长为1 如果dj与d(j 1逆序，则两者互换(冒泡一次)I循环尾1循环尾(2) 从前向后实现冒泡排序从前向后实现冒泡排序的程序结构：-让i从1到n 1循环让j从1到n i循环如果d j与d j + 1逆序，则两者互换 冒泡一次I循环尾1循环尾【自我校对】列举所有所有解数学表达式数学表达式同时相邻四、选择排序1 选择排序基本思想是在所有的记录中选出最小(大)的数据，把它与第一个数据交换， 然后在其余的记录中再选出最小(大)的数据与第二个数据交换，依次类推，直至 所有数据排序完成。2 选择排序的实现要素(1) 将数据存放在数组中

5、，确定数组的名称、元素个数。(2) 强调。在第i遍排序中，比较n i次，最多交换1次。(3) 变量k仅用于记录需要寻找的最值(最大值或最小值)位置，比较的是d(j)与d(k)，交换的是。3 选择排序的程序实现(1) 从前向后实现选择排序从前向后实现选择排序的程序结构(升序排序):.让i从1到n 1循环k = i|让j从i + 1到n循环 <如果dj戶d(k ,则把j保存到k中.循环尾如果ko i,则交换d(k和d(i的值1循环尾(2) 从后向前实现选择排序从后向前实现选择排序的程序结构(升序排序):.让i从n到2循环 步长为1k = i| j让j从i -1到1循环彳 < 如果dj戸

6、d(k ,则把j保存到k中循环尾如果ko i,则交换d(k和d(i 的值1循环尾【答案】 先比较，再交换 d(k)和d(i)五查找算法的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置； 反之，查找不成功。?的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较， 如果两者相等，则查找成功；否则根据数组 元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查 找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使 查找成功，或直到子表不存在，查找不成功。【

7、答案】 顺序查找 ？对分查找六、递归算法函数或过程调用它本身，称为？。?的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题， 当问题小到一定 程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小，小 事化了”的基本思想。递归算法必须具备的条件： 每一步骤解决问题的方法要一致。 有边界条件。【答案】？递归 ？递归算法七、VB访问数据库1 通过ADO连接数据库ADO是微软公司提供的一种应用程序访问数据库的编程接口。该接口包含 了多个对象，其中Connection对象用于与数据库建立连接，在建立连接后，可 通过Recordse

8、t对象获取数据表中的数据。在用Connection建立与数据库的连接时，需要设置 ConnectionString属性的 值（即连接字符串），以指定连接数据库所用的驱动程序、数据源名称、用户名和 密码等。方法用于打开到数据源的连接,方法用于关闭连接。2.通过Recordset对象获取数据库中的数据，步骤如下:（右边是对应的代码）:定文利初始化 Re«ordeAl 対鑒dim my record A? N-rw ADoDB. Rwordfrei打开 Hccordcsl<straal =* from Enytabla1'set my record r AclivcCun n

9、tct iciriniHjrconi my rECDrd. open BLrsqli-1Do while No-t myrccord+EOF便用 R ecord.es!对 媳的方Sfe移 动指tL移勃弭棚 应的记录tZid.fi）二 myrecDril. Fielda（，fczd'K）. Valuei = i+ 1nnyrc（brdlM|iivc!Nr?i.lConn ection对象具有 Open Close等方法，其中？ieiyrc!ffircl. t Jijkh myrconl = Nalhing说明：myrecord是定义的Recordset对象的名字 mytable是数据库中

10、某张表的名称。 EOF属性：若当前记录的位置在最后的记录之后，则返回True，否则返回 Falseo MoveNext方法：指针移到下一条记录。 这段代码应该在连接数据库后，关闭数据库前。【答案】？ Open ? Close学考真题试做1. (2012年6月浙江会考)计算三角形面积的算法如下：输入三角形三边长a, b, c计算半周长p= (a+ b+ c)/2计算三角形面积 s= Sqr(p*(p a)*(p b)*(p c)输出面积 s上述算法属于()A .排序算法C.枚举算法B .解析算法D .查找算法B 本题主要考查各种算法的基本思想。本题中算法的基本思想是通过数学表达式的计算来解决问题

11、，符合解析算法的基本思想。2. (2014年3月浙江学考)运行下列VB程序，在文本框Text1中输入28, 界面如图所示。Private Sub Comma nd1_Click()Dim s As Si ngleDim v As Si ngleDim t As Sin gles= 0v = l0t = Val ( Text I.Text )s= s+ v*tLabell .Capti on = Str(s)End Sub单击“计算”按钮Command1后，标签Labell中显示的内容是。该程序采用了 (2)(填：解析/排序/查找)算法。【解析】 本题主要考查各种算法的基本思想特点及程序阅读能力

12、。 s的值 通过s= s+ v*t计算得到，s的初值是0,将v = 10, t = 28(从文本框中输入)代入, 得到s= 280,符合解析算法的基本思想。【答案】(1)280解析重点深度剖析一、冒泡排序与选择排序对比冒泡排序与选择排序冒泡排序选择排序思想方法边比较边交换先选出最大值或最小值，再交换核心代码For i = 1 To n 1For i = 1 To n 1For j = n To i + 1 Step 1If a(j)<a(j 1) The ntemp= a(j 1) a(j 1)= a(j) a (j) = temp End IfNext j Next ik = iFor

13、 j = i + 1 To n If a(j) <a(k) The n k 二 jNext jIf k<>i Then temp = a(i) a(i)二 a(k) a (k) = temp End IfNext i相同点n个数都需要n-1遍排序，其中变量i控制排序 的遍数比较的次数一样多，都是(n 1) + (n 2)+ 3 + 2+ 1 次最好的情况下，交换的次数一样，都是0次不同点边比较边交换， 最坏的情况下先选择再交换，最坏的情况下交 换的次数是n1次交换的次数是(n1) + (n 2)+ + 3 + 2+ 1 次如何区分因为是相邻两 数比较，因此代 码中有类似“ a

14、（j）和 a（j 1）”比较的条件 表达式因为是先选出最大值或最小值， 再交换，因此代码中有寻找最大 值或最小值的代码，并且用变量 （如k）来记录该值所在的位置。如 果k o i则交换、枚举算法与顺序查找枚举算法顺序查找思想方法列举所有可能解并验证数据源从头到尾 逐个比较核心代码For（列举所有可能的 解）If可能解是正确解then输出该解n extFor（从数组的第一 个元素到最后一 个元素）If当前元素二关 键词then输出该位置n extFor语句用于列举 所有可能的解，即解 的范围For语句用于访 问整个查找源的 数据，一般是从开 始位置到结束位 置区分方法If语句是验证当前 列举的可

15、能解是否 是正确解If语句用于判断 当前访问的元素 是不是等于关键 词正确解可能有多 个，因此找到一个正 确解后，循环继续， 直到所有可能的解 都被检验过一旦某个位置 的数据等于关键 词，则记录该位 置，并且查找任务 结束，通常用语句 exit for退出循环不管是枚举算法还是顺序查找，都可以写成For循环语句，区分的方法是要分析问题的本质：for语句是为了一一列举所有可能的解还是从头到尾逐个访问 数据源中的数据；if语句是检验可能解还是比较关键词。三、对分查找对分查找的基本思想：查找的数据源a(1)到a(n)是有序的(如从小到大排序)， 查找的关键词是key，则第一次查找的范围是1，n，如果

16、中间位置为 m，则m =fix(1 + n)/2)。如果key= a(m)，则查找成功；如果key<a(m)，则下一次查找的 范围变为1，m 1；如果key>a(m)，则下一次查找的范围变为m + 1，n。在 新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，则查找成 功；或直到子表不存在，则查找不成功。说明：对分查找的前提是被查找的数据必须是有序的。对分查找每次访问的是当前查找范围里中间位置上的数据， 并根据该数据 与关键词的大小关系，将下一次的查找范围缩小一半。规模为n个数的数据源，使用对分查找时，最多经过Int(log2n)+ 1次查找。题组对点训练1.7位学生的

17、身高(单位：cm)从高到低依次为：178,177,175,172,170,165,162用对分查找法找到178的过程中，依次被访问到的数据是(B. 172,175,178C. 172,177,178D. 172,175,177,1787个数据从1到7m= Fix(1 + 7)/2) =C 本题主要考查对对分查找算法基本思想的理解。将进行编号。第一次访问到的数据是第 4个，即172(中间位置4), 178> 172，因此下一次查找的范围是前半部分，即第1个到第3个。因此第二次访问的数据应该是第2个，即177(中间位置m= Fix(1 + 3)/2) = 2),178> 177,因此下

18、一次查找的范围是前半部分，即第1个，因此第三次访问的数据是第 1个，即178。2 .某校通过政府招投标中心采购一套多媒体教学设备，有 5家单位参加竞 标，竞标价分别为19万、15万、21万、13万、12万元人民币。若采用选择排 序算法对标价从大到小排序，需要进行数据互换的次数是 ()C3D4B 原始数据 19、 15、21、13、 12，第一遍排序 19 与 21 互换，得到 21,15,19,13,12；第二遍排序 15 与 19 互换，得到 21,19,15,13,12；第三遍排序与 第四遍排序都不需要数据互换。因此总共是 2次数据互换。 3实现某排序算法的部分 VB 程序如下：For i

19、 = 1 To 6k = iFor j= i + 1 To 7If a(j)<a(k) The n k = jNext jIf i<>k Thent = a(i)： a(i) = a(k) : a(k) = tEnd IfNext i在排序过程中，经过某一遍排序“加工”后，数组元素 a到a的数据依 次为“ 10,41,75,12,63,11,85。则下一遍排序“加工”后数组元素 a(1)到a(7)的 数据依次是 ()A10,11,41,75,12,63,85B10,11,75,12,63,41,85C10,11,12,75,63,41,85D10,11,12,41,63,75

20、,85B 本题主要考查选择排序算法的代码特点。选择排序的基本操作是先找出最小数或最大数所在的位置， 记录在一个变量中， 再根据需要进行数据交换， 因 此代码中会出现“ k= j”以及“ If i v> k”的代码，根据代码特点，可确定本题的排序算法是选择排序。 一旦确定是选择排序， 接着就可以用选择排序的思想方 法来对数据进行排序。根据第一遍排序结果可得知排序的结果是数据从小到大 排，选择排序的基本思想是从所有的记录中选出最小 (从小到大排)的数据，把它与第一个数据交换，然后在其余的记录中再选出最小的数据与第二个数据交换以此类推，直至所有数据排序完成。因此“ 10,41,75,12,63,11,85的下一遍选择排序的结果应该是： “ 10,11,75,12,63,41,85。4 有如下对a(1)到a(6)进行升序排序的程序片段：For i= 1 To 5k = iFor j= i + 1 To 6Next jIf k<>i Then t = a(i)： a(i) = a(k)： a(k) = tNext i划线部分应填()A .If a(j)<a(k)Then k = jB. If a(j)<a(k)Then k = iC. If a(j)>a(k)Then k = jD. I