届高考信息技术浙教版知识点梳理VB选考部分.docx
《届高考信息技术浙教版知识点梳理VB选考部分.docx》由会员分享，可在线阅读，更多相关《届高考信息技术浙教版知识点梳理VB选考部分.docx（14页珍藏版）》请在冰点文库上搜索。
届高考信息技术浙教版知识点梳理VB选考部分
VB选考部分
本章包括对分查找（标准对分、查找第一个大于等于a的数、查找第一个小于等a的数）以及对分的变式。
排序：
冒泡排序，选择排序。
但是在实际解题中还会碰到其他排序，例如桶排序、插入排序、快速排序、索引排序及冒泡排序的优化
递归：
标准递归
对分查找算法专题
（一）标准对分算法
对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
对分查找算法平均比较次数为
在数组中的数据是有序的，如果是增序的，是指下标越小的数组元素中存储的数据也越小，减序则相反。
代码如图1所示
图1
例如：
有数组长度为10的a数组其中值分别为1,2,3,4,5,6,7,8,9,10通过对分查找算法查找8，对应的i,j,m,flag的变化如表1所示
初值
第一次
第二次
m=0
m=5
m=8
i=1
i=6
i=6
j=10
j=10
j=10
flag=false
flag=false
flag=true:
循环退出
表1
当然，对分查找法与数据结构中的二叉树思想一致，所以我们也可以用二叉树来表示对分查找算法的对分过程。
如图2
图2
（二）标准对分算法变式
图3
如图3所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量
计算可得当key在当前数组（a）中不存在时i>j即i=j+1，当key存在于数组中时
i<=j，所以在循环结束后我们可以通过i和j的关系来判断key是否存在。
（三）
求大于等于/小于等于key的第一个/最后一个数
1.求大于等于key的第一个数
图4图5
如图4所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量以及去掉了找到后退出的代码即去掉了ExitDo。
初值
第一轮
第二轮
第三轮
第四轮
第五轮
m
0
9
4
6
7
7
i
1
1
5
7
7
7
j
18
8
8
8
7
6
表2
设key为21当key等于a（m）时j还要往前走一直到到第一个第一个小于key的值即19这个值的位置。
同时根据i<=j可得i=j+1所以最后i是第一个值的位置。
2.求小于等于key的最后一个数
图6图7
如图4所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量以及去掉了找到后退出的代码即去掉了ExitDo。
初值
第一轮
第二轮
第三轮
第四轮
第五轮
m
0
9
14
11
12
13
i
1
10
10
12
13
14
j
18
18
13
13
13
13
表3
设key为21当key等于a（m）时i还要往前走一直到到最后一个大于key的值即19这个值的位置。
同时根据i<=j可得i=j+1所以最后i是第一个值的位置。
（四）使用对分查找算法求值相同的数量
图8图9
观察图8代码可知这是一个求大于等于key的第一个数和求小于等于key的最后一个数的合体，先求出key的第一个位置。
而后求出最后一个的位置。
这样就可以得到长度为最后一个数的位置减去第一个数的位置+1，即j-i+1。
（五）使用二叉树解决实际问题
1.根据对分次数求key
图10图11
观察图10代码可知这是一个标准的对分查找，只是在标准对分上新添加了一个变量c。
观察可知，c是用来记录对分次数。
根据对分查找算法的原理每一次对分都会把范围分成两段（即两种可能）。
在不知道Key不知道是多少的前提下。
需要把两种可能都计算。
这样刚好与二叉树的图一致，见图11。
例如求当C等于2时key等于多少？
可以从图上对分次数中可得第一次对分到5即c=1，第二次对分到2或8即c=2,以此类推。
由此可得当c等于2时key=2或8。
2.根据i、j变换求key
图12图13
观察图12代码可知这是一个标准的对分查找，只是在标准对分上新添加了一个变量c。
观察可知，c是用来求和的。
根据对分查找算法的原理每一次对分都会把范围分成两段（即两种可能）。
在不知道Key不知道是多少的前提下。
需要把两种可能都计算。
这样刚好与二叉树的图一致，即往左走c-1往右走c+1见图13。
例如求当C等于2时key等于多少？
可以从图上对分次数中可得第一次对分到5即c=0，第二次对分到2或8即c=1或-1,以此类推。
由此可得当c等于2时key=9。
（六）其他变式
变式1（取第一个）
L=1:
R=10
DoWhileL+1m=（L+R）\2
Ifkey>a（m）Then
L=m
Else
R=m
EndIf
Loop
PrintStr（L+1）
变式2（取第一个）
L=1:
R=10
DoWhileL+1m=（L+R+1）\2
Ifkey>a（m）Then
L=m
Else
R=m
EndIf
Loop
PrintStr（L+1）
变式3（死循环，无法执行）
L=1:
R=10
DoWhileL<=R
m=（L+R+1）\2
Ifkey>a（m）Then
L=m+1
Else
R=m
EndIf
Loop
PrintStr（L+1）
变式4（死循环，无法执行）
L=1:
R=10
DoWhileL<=R
m=（L+R-1）\2
Ifkey>a（m）Then
L=m+1
Else
R=m
EndIf
Loop
PrintStr（L+1）
变式5（取第一个）
L=1:
R=10
DoWhileLm=（L+R+1）\2
Ifkey>a（m）Then
L=m
Else
R=m-1
EndIf
Loop
PrintStr（L+1）
变式6（取第一个）
L=1:
R=10
DoWhileLm=（L+R-1）\2
Ifkey>a（m）Then
L=m+1
Else
R=m
EndIf
Loop
PrintStr（L）
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序算法，就是如何使得记录按照要求排列的方法。
排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。
一个优秀的算法可以节省大量的资源。
在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
考纲中的排序包括冒泡排序，选择排序。
但是在实际解题中还会碰到其他排序，例如桶排序、插入排序、快速排序、索引排序及冒泡排序的优化。
本文将针对冒泡、选择、插入、桶排序、快速排序、索引排序及冒泡排序优化进行分析。
冒泡排序
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。
这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。
冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第（n一1）个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。
排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。
Fori=1Ton-1
Forj=nToi+1Step-1
Ifa（j）t=a（j）:
a（j）=a（j-1）:
a（j-1）=t
EndIf
Nextj
Nexti
升序排
Fori=1Ton-1
Forj=nToi+1Step-1
Ifa（j）>a（j-1）Then
t=a（j）:
a（j）=a（j-1）:
a（j-1）=t
EndIf
Nextj
Nexti
降序排
DimflagAsBoolean
flag=False
n=10
Fori=1Ton-1
Forj=nToi+1Step-1
Ifa（j）>a（j-1）Then
t=a（j）:
a（j）=a（j-1）:
a（j-1）=t:
flag=True
EndIf
Nextj
Ifflag=FalseThenExitFor
Nexti
冒泡优化1
n=10
DimflagAsBoolean
DimlastAsInteger
flag=True
last=1
DoWhileflag=True
flag=False
Forj=nTolast+1Step-1
Ifa（j）>a（j-1）Then
t=a（j）:
a（j）=a（j-1）:
a（j-1）=t:
last=j:
flag=True
EndIf
Nextj
Loop冒泡优化2
选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
举个例子，序列58529，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
n=10
Fori=1Ton-1
k=i
Forj=i+1Ton
Ifa（j）>a（k）Thenk=j
Nextj
Ifk<>iThen
t=a（k）:
a（k）=a（i）:
a（i）=t
EndIf
Nexti
n=10
Fori=1Ton-1
Forj=i+1Ton
Ifa（i）>a（j）Then
t=a（i）:
a（i）=a（j）:
a（j）=t
EndIf
Nextj
Nexti
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C.A.R.Hoare在1960年提出。
它的基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
（1）首先设定一个分界值，通过该分界值将数组分成左右两部分。
（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
（3）然后，左边和右边的数据可以独立排序。
对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。
右侧的数组数据也可以做类似处理。
（4）重复上述过程，可以看出，这是一个递归定义。
通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。
当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
桶排序（Bucketsort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。
每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
桶排序是鸽巢排序的一种归纳结果。
当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。
但桶排序并不是比较排序，他不受到O（nlogn） 下限的影响。
Dimb（1To100）AsInteger
Fori=1To10
b（a（i））=b（a（i））+1
Nexti
s1=""
Fori=1To100
Forj=1Tob（i）
s1=s1+Str（i）
Nextj
Nexti
Text2.Text=s1
插入排序，一般也被称为直接插入排序。
对于少量元素的排序，它是一个有效的算法 [1] 。
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
DimkeyAsInteger
DimjAsInteger
j=0
n=10
Fori=2Ton
key=a（i）
j=i-1
DoWhilej>=1Andkeya（j+1）=a（j）
j=j-1
Loop
a（j+1）=key
Nexti
索引排序，是基于冒泡排序法的一种优化算法，算法核心是:
用一个数组元素的值做另一个数组元素的下标，然后交换下标。
例如a（b
（1））（2））thent=b
（1）:
b
（1）=b
（2）:
b
（2）=t。
代码如下：
Fori=1To4
Forj=5Toi+1Step-1
Ifa（b（j））>a（b（j-1））Then
t=b（j）:
b（j）=b（j-1）:
b（j-1）=t
EndIf
Nextj
Nexti
Fori=1To10
List1.AddItema（b（i））
Nexti
递归算法（英语：
recursionalgorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。
递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。
绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。
计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
Functionf（xAsInteger）AsInteger
Ifx=1Then
f=1
Else
f=f（x-1）*x
EndIf
EndFunction
Subf（xAsInteger）
Ifx=1Then
ExitSub
Else
f=f（x-1）*x
EndIf
EndSub
升级会员 