算法及程序实现知识点

1、算法及程序实现知识点一、枚举算法及程序实现枚举算法基本思想是根据问题本身的性质，一一列举出该问题所有可能的情况，并根据题目的条件逐个作出判断， 从中挑出符合要求的解。枚举算法属于搜索策略，适用于解变量确定的连续值域的问题。设计枚举算法时要在尽可能小的范围内罗列出所有可能的情况，不能遗漏，也不能重复。例 : 假如我有一个 QQ的密码是一位数字， 如果让同学们来破解的话，会把 0 到 9 十个数字都试一遍，找到密码，这种方法使用的算法就是枚举算法。枚举算法解题的主要方法，必须把所有的可能情况都一一列出来，这种可能情况，一般通过循环列举出来。例如课本例题，一份单据被抹除的数字的推算问题。可能的情况有

2、25006 至 25996 一共 100 种，通过循环把这一百种情况全部列出来，在循环列出来的过程对，对每一种情况进行比较，是否符合要求。n=25006+j*100 ，j 的范围为 0 至 99，此处列出来的表达式只有一个未知数j ，所以只需用一重循环就够了。DO循环c=0如果需要统计符合要求的单据的张数的话，用c 做计数器j=0do while j<100j 的范围是0 至 99，此处也可写成j<=99n=25006+j*100通过 j 把单据的所有的可能情况列出来if n mod 37=0 or n mod 67=0 then判断是否符合要求print nc=c+1通过判断把符

3、合要求的单据的值输出符合要求的单据加一张end ifj=j+1j 每次增加1 直到99loopFOR循环c=0如果需要统计符合要求的单据的张数的话，用For j=0 to 99一重循环，把j 所有可能情况列出来n=25006+j*100通过 j 把单据的所有的可能情况列出来if n mod 37=0 or n mod 67=0 then判断是否符合要求print n通过判断把符合要求的单据的值输出c=c+1符合要求的单据加一张c 做计数器end ifNext j在 for 循环中不需要 j=j+1 ，因为 for 循环 j 的值每次会自己增加步长，此处步长省略没写，即表示步长为 1，所以 j

4、每次会自动增加 1。课本例题变形金刚问题：小盒5 个，大盒 12 个， 1200 个多少种装法。设小盒为x 个，则 x 的范围是： 0 至 240；设大盒为y 个，则 y 的范围是： 0 至 100要求符合的条件为5*x+12*y=1200 ，此处有两个未知数x、y，所以的用二重循环（三个未知数即用三重、四个未知数即用四重循环 ）DO循环c=0：x=0： y=0do while x<=240do while y<=100n=5*x+12*yif n=1200 thenprint x,yc=c+1第一重循环， x 的范围是0 至 240第二重循环， y 的范围是0 至 100通过 x

5、,y 把所有的可能装法情况列出来判断是否符合要求（5*x+12*y=1200 ）通过判断把符合要求的装法情况输出符合要求的装法增加一次end ify=y+1loopx=x+1loopy 每次增加 1 直到第二重循环结束x 每次增加 1 直到第一重循环结束100240FOR循环c=0for x=0 to 240for y=0 to 100n=5*x+12*yif n=1200 thenprint x,yc=c+1第一重循环， x 的范围是0 至 240第二重循环， y 的范围是0 至 100通过 x,y 把所有的可能装法情况列出来判断是否符合要求（5*x+12*y=1200 ）通过判断把符合要求

6、的装法情况输出符合要求的装法增加一次end ifnext y第二重循环结束next x第一重循环结束同样在 for循环中也不需要x=x+1 、 y=y+1，因为 for循环略没写，即表示步长为1，所以 x、y 每次会自动增加1。x、y的值每次会自己增加步长，此处步长省二、解析算法及程序实现是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。例：同学们在数学的应用题中、物理、化学的计算题中通过理解题意得出表达式，再通过计算得到答案，所使用的算法就是解析算法。解题方法：主要是要得出前提条件与所求结果之间关系的数学表达式， 并且在程序中这个数学表达

7、式必须符合 VB格式。储蓄问题，不考虑复利，年利率2.8%， M元钱需存多少年，才能得到K 元本息？设需要 y 年，根据题意得出的数学表达式为：km，但是在VB 中表达式必须符合VB 语法：y=0.028my=(k-m)/(0.028*m)流程图及程序实现略。三、排序算法及程序实现1冒泡排序冒泡排序的基本思想是把待排序的 n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工（一趟冒泡）。当第一遍加工完成时，最小的数据已经上升到第一个元素的位置。然后对余下的

8、 n-1 个元素重复上述过程，直至最后进行余下两个数据的比较和交换。冒泡排序算法举例设有数列 65,13,76, 27,49第 1 趟比较第 1 次 65,13,76, 27,49 不需要交换第 1 趟比较第 2 次 65,13,76, 27,49 76,27 交换第 1 趟比较第 3 次 65,13,27, 76,49 不需要交换第 1 趟比较第 4 次 65,13,27, 76,49 65,13 交换第 1 趟结束： 13,65,27,76,49第 1 趟比较 4 次，交换2 次第 2 趟比较第 1 次： 1365,27,76,49 76,49 交换第 2 趟比较第 2 次： 1365,2

9、7,49,76 不需要交换第 2 趟比较第 3 次： 1365,27,49,76 65,27 交换第 2 趟结束： 13,27,65,49,76第 2 趟比较 3 次，交换2 次第 3 趟比较第 1 次： 13,2765,49,76 不需要交换第 3 趟比较第 2 次： 13,2765,49,76 65,49 交换第 3 趟结束： 13,27,49c65,76第 3 趟比较 2 次，交换1 次第 4 趟比较第 1 次： 13,27,4965,76 不需要交换第 4 趟结束： 13,27,49,65,76第 4 趟比较 1 次，没有交换5 个元素的数据系列，一共冒泡了4 趟，分别比较次数为 4、

10、 3、 2、 1，交换次数根据实际情况确定。所以可以总结出，n 个元素的数组系列通过冒泡排序，需要经过n-1 趟冒泡，总的比较次数为：(n-1)+(n-2)+(n-3)+ +1= ( n 1) * n 次。2两个元素中的数据交换一般需要通过第三个变量来进行D(1)=5:D(2)=8交换的过程为：T=D(1)D(1)=D(2)D(2)=T流程图：冒泡排序的程序实现：通过例子我们知道，5 个元素的数据系列，一共冒泡了4 趟，分别比较次数为设计中，我们通过循环来进行控制，需要两重循环，大循环控制冒泡了4 趟：For i=1 to 4 （ 5-1）4、 3、 2、1。所以在程序Next i小循环控制每

11、趟冒泡比较的次数：For j=5 to i（ i 的值根据大循环分别为1到4）Next i所以小循环是在大循环里面的通过判断if d(j)<d(j-1) 来控制是否需要交换程序主体部份如下：For i=1 to n-1For j=n to I step -1If d(j)<d(j-1) thenT=d(j)D(j)=d(j-1)D(j-1)=tEnd ifNext jNext i2选择排序选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。流程图：选择排序算法举例设有

12、数列 65,97,76,13,27,49,58 第 1 趟 65,97,76,13,27,49,58寻找最小数据 d(k)=d(4)=13 与 d(1)交换第 2 趟 1397,76,65,27,49,58寻找最小数据 d(k)=d(5)=27 与 d(2)交换第 3 趟 13,2776,65,97,49,58寻找最小数据 d(k)=d(6)=49 与 d(3)交换第 4 趟 13,27,4965,97,76,58寻找最小数据 d(k)=d(7)=58 与 d(4)交换第 5 趟 13,27,49,5897,76,65寻找最小数据 d(k)=d(7)=65 与 d(5)交换第 6 趟 13,2

13、7,49,58,6576,97 寻找最小数据 d(k)=d(6)=76 与 d(6)交换结束： 13,27,49,58,65,76977 个元素的数据系列需要寻找6 次。程序实现：d(1)=65 ； d(2)=97for i=1 to 6k=i； d(3)=76； d(4)=13； d(5)=27 ；d(6)=49 ； d(7)=58第一重循环，控制趟数，7 个元素需要6 趟for j=i+1 to 7第二重循环，在待排序中找最小数，待排序元素每次减少一个if d(j)<d(k) then k=jnext jif k<>i thenkt=d(j)找出最小的数据结束第二重循环把

14、最小数据与待排序数据中的第一个交换d(j)=d(k)d(k)=ktend ifnext i结束第一重循环例 1：选择排序的基本思想是在参与排序的所有数组元素中找出最小互换位置，然后再在余下的元素中重复上述过程。有一组数，顺序是“这组数从大到小排序，第一次交换数据后的顺序是：(或最大 )的元素，使它与第一个元素2、 6、 4、 1”，用选择排序法将（ A） 6、2、1、4（B） 6、4、2、1 （C） 6、1、2、4 （D） 6、2、4、1四、查找算法及程序实现1顺序查找顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数

15、据的位置；反之，查找不成功。流程图：d(1)=65 ； d(2)=97 ； d(3)=76 ； d(4)=13 ； d(5)=27 ；d(6)=49 ； d(7)=58查找 key=49程序实现：For i=1 to 7If d(i)=key then输出找到是第d(i)个Exit forEnd ifNext i2对分查找对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找； 在新确定的范围内， 继续按上述方法进行查找， 直到找到要查找的数据

16、，使查找成功，或直到子表不存在，查找不成功。对分查找的条件是被查找的数据必须是有序的。对分（二分）查找过程：d(1)=13 ； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76；d(6)=97； d(7)=102； d(8)=138； d(9)=202查找k=138d(1)=13 第一次 d(1)=13； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202k 与 d（fix （1+9 ） /2） =d（ 5）比较 ，比 d（5）大，下次在d（5）的右边找； d(

17、2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202第二次 k 与 d（5）右边的 d（ fix （ 6+9） /2） =d（ 7）比较 ，比 d（ 7）大，下次在 d（ 7）的右边找 d(1)=13 ； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202第三次 k 与 d（7）右边的d（ fix （ 8+9） /2） =d（ 8）比较 ，与 d（ 8）相等，找到。依次被访问进行比较的数字为：d（5）、 d（7）、 d（8）流程图：课本上的查找函数：Function search（ key as integer） as integeri=1i代表待查找数列中的第一个元素的下标，刚开始时是1j=9j代表待查找数列中的最后一个元素的下标，刚开始时是9（因为一共9 个元素）nc=0统计查找次数do while i<=j第一个元素的下标要小于或等于最后一个元素的下标，否则待查找数列就不存在了nc=nc+1每找一次增加一次m=fix （i+j ） /2求等查找数列中间数的下标if d