必修3 第2单元算法与程序实现(教师版).docxVIP

第二单元　算法的程序实现[考试标准]考试内容考试要求考试属性1.枚举算法及程序实现c加试2.解析算法及程序实现c3.排序算法及程序实现c(1)冒泡排序(2)选择排序4.查找算法及程序实现c(1)顺序查找(2)对分查找5.递归算法a6.VB访问Access数据库a(1)通过ADO对象连接数据库(2)通过Recordset对象获取数据表中的数据一、排序算法及程序实现1．排序的含义及方式(1)所谓排序就是将无序的数列变成有序的数列。(2)排列方式分为升序(也称递增，即从小到大排列)和降序(也称递减，即从大到小排列)。2．冒泡排序(1)冒泡排序基本思想将n个数据看作竖向排列的一组数据，每趟排序自下而上对每对相邻数据进行比较，若次序不符合要求就进行交换。每趟排序结束时都能使排序范围内关键字最小的记录像一个气泡一样升到上端的对应位置，整个排序过程共进行n－1趟，依次将关键字最小、次小……的各个数据冒到表的第一个、第二个……位置上。用冒泡排序对n个数据进行排序时，共需进行n－1趟排序，比较的总次数为。(2)冒泡排序算法框架For i＝1 To n－1 　’n个数据进行排序，共需进行n－1趟第i趟排序：从第n个数到第i个数，比较相邻两个数，符合条件则进行互换。(3)冒泡排序程序实现说明：要排序的n个数据已存放d数组中，以升序为例的程序如下：For i＝1 To n－1　’n个数排序共需进行n－1趟　For j＝n To i＋1 Step－1　’每一趟从后往前，相邻两数两两比较If d(j)＜d(j－1)Then　’若满足条件则进行互换temp＝d(j)d(j)＝d(j－1)d(j－1)＝tempEnd If　Next jNext i温馨提示：若要按降序排列，只需将程序中的语句“If d(j)＜d(j－1) then”改为“If d(j)＞d(j－1)Then”即可。3．选择排序(1)选择排序的基本思想每趟排序是在所有的数据中找出最小(或最大)的数据，使它与第一个数据相互交换位置，然后再在剩下的数据中找出最小(或最大)的数据，与第二个数据相互交换位置，以此类推，直到所有元素成为一个有序序列。(2)选择排序算法框架For i＝1 To n－1　’n个数排序共需进行n－1趟　’第i趟排序在第i至第n个位置中找到最小数的位置k将找到的最小数(k位置上的数)与i位置上的数互换Next i注意：当ki时，将k位置上的数与i位置上的数互换。(3)选择排序的程序实现说明：要排序的n个数据已存放d数组中。以升序为例的程序如下：For i＝1 To n－1　’n个排序共进行n－1趟排序　k＝i　’第i趟排序时，首先用k记录i　For j＝i＋1 To n　’k位置上的数依次与j位置上的数进行比较If d(k)d(j)　Then k＝j　’若找到比k位置上更小的数，则更新k的值Next jIf k＜＞i Then　’若i位置上的数不是最小数，则和k位置上的数进行互换　temp＝d(i)　d(i)＝d(k)　d(k)＝temp End IfNext i温馨提示：若要按降序排列，只要将语句If d(k)＞d(j) Then k＝j改成If d(k)＜d(j－1) Then k＝j即可。二、查找算法及程序实现1．查找算法所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种，即找到(查找成功)和未找到(查找失败)。2．顺序查找(1)顺序查找的基本思想从第一个数据开始，从左往右(或从上到下)将数据按顺序逐个与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到并输出所查数据的位置；反之，查找失败。若有n个数，则可能的最多查找次数为n。(2)顺序查找算法基本框架设要查找的数为key，待查找的数存放在数组d中。For语句框架：　For i＝1 to n若d(i)＝key，则表示找到，做相应处理　Next i　若i＞n表示未找到Do While语句框架：　i＝1　Do while i＜＝n若d(i)＝key，则表示找到，做相应处理i＝i＋1Loop　若i＞n表示未找到(3)顺序查找的程序实现在n个数组元素中依次查找，找到第1个满足条件的值，查找即结束，输出找到元素所在的位置；若找不到，输出“未找到”。程序实现：设要查找的数据是key(在文本框Text1中输入)，查找的数据存放在数组d中。pos为找到数的位置，pos＝0表示未找到。P表示查找的次数。　key＝Val(Text1.Text)　’Val要根据实际情况决定是否要添加　p＝0　pos＝0　find＝False　’find表示查找结果　i＝1　Do While i＜＝n And Not find　’表示还没找完并且还未找到，则继续查找，Not find也可表示为find＝falsep＝p＋1If key＝d(i