算法及程序实现知识点

《算法及程序实现知识点》由会员分享，可在线阅读，更多相关《算法及程序实现知识点（8页珍藏版）》请在装配图网上搜索。

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

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

3、 if j=j+1 j每次增加1直到99 loopFOR循环c=0 如果需要统计符合要求的单据的张数的话，用c做计数器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 符合要求的单据加一张 end ifNext j在for循环中不需要j=j+1，因为for循环j的值每次会自己增加步长，此处步长省略没写，即表示步长为1，所以j每次会自动增加1。课本例题变形金刚问题：小盒5个，大盒

4、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=240 第一重循环，x的范围是0至240 do while y=100 第二重循环，y的范围是0至100n=5*x+12*y 通过x,y把所有的可能装法情况列出来 if n=1200 then 判断是否符合要求（5*x+12*y=1200） print x,y 通过判断把符合要求的装法情况输出 c=c+1 符

5、合要求的装法增加一次 end if y=y+1 y每次增加1直到100 loop 第二重循环结束 x=x+1 x每次增加1直到240loop 第一重循环结束FOR循环c=0for x=0 to 240 第一重循环，x的范围是0至240for y=0 to 100 第二重循环，y的范围是0至100n=5*x+12*y 通过x,y把所有的可能装法情况列出来 if n=1200 then 判断是否符合要求（5*x+12*y=1200） print x,y 通过判断把符合要求的装法情况输出 c=c+1 符合要求的装法增加一次 end ifnext y 第二重循环结束next x 第一重循环结束同样在f

6、or循环中也不需要x=x+1、y=y+1，因为for循环x、y的值每次会自己增加步长，此处步长省略没写，即表示步长为1，所以x、y每次会自动增加1。二、解析算法及程序实现是指用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。例：同学们在数学的应用题中、物理、化学的计算题中通过理解题意得出表达式，再通过计算得到答案，所使用的算法就是解析算法。解题方法：主要是要得出前提条件与所求结果之间关系的数学表达式，并且在程序中这个数学表达式必须符合VB格式。储蓄问题，不考虑复利，年利率2.8%，M元钱需存多少年，才能得到K元本息？设需要y年，根据题意得出的数

7、学表达式为：y=，但是在VB中表达式必须符合VB语法：y=(k-m)/(0.028*m)流程图及程序实现略。三、排序算法及程序实现1冒泡排序冒泡排序的基本思想是把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工（一趟冒泡）。当第一遍加工完成时，最小的数据已经上升到第一个元素的位置。然后对余下的n-1个元素重复上述过程，直至最后进行余下两个数据的比较和交换。冒泡排序算法举例 设有数列 65,13,76, 27,49第1趟比较第1次 65,13,7

8、6, 27,49不需要交换第1趟比较第2次 65,13,76, 27,4976,27交换第1趟比较第3次 65,13,27, 76,49不需要交换第1趟比较第4次 65,13,27, 76,4965,13交换第1趟结束：13,65,27,76,49 第1趟比较4次，交换2次第2趟比较第1次：1365,27,76,4976,49交换第2趟比较第2次：1365,27,49,76不需要交换第2趟比较第3次：1365,27,49,7665,27交换第2趟结束：13,27,65,49,76 第2趟比较3次，交换2次第3趟比较第1次：13,2765,49,76不需要交换第3趟比较第2次：13,2765,4

9、9,7665,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、3、2、1，交换次数根据实际情况确定。所以可以总结出，n个元素的数组系列通过冒泡排序，需要经过n-1趟冒泡，总的比较次数为：(n-1)+(n-2)+(n-3)+1=次。两个元素中的数据交换一般需要通过第三个变量来进行D(1)=5:D(2)=8交换的过程为：T=D(1)D(1)=D(2)D(2)=T流程图：冒泡排序的程序实现：通过例子我们

10、知道，5个元素的数据系列，一共冒泡了4趟，分别比较次数为4、3、2、1。所以在程序设计中，我们通过循环来进行控制，需要两重循环，大循环控制冒泡了4趟：For i=1 to 4（5-1）Next i小循环控制每趟冒泡比较的次数：For j=5 to i（i的值根据大循环分别为1到4）Next i所以小循环是在大循环里面的通过判断if d(j)d(j-1)来控制是否需要交换程序主体部份如下：For i=1 to n-1 For j=n to I step -1 If d(j)d(j-1) then T=d(j) D(j)=d(j-1) D(j-1)=t End if Next jNext i2选择

11、排序选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。流程图：选择排序算法举例 设有数列 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 寻找最

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

13、j)d(k) then k=j 找出最小的数据next j结束第二重循环if ki then把最小数据与待排序数据中的第一个交换 kt=d(j) 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顺序查找顺序查找的基本思想是从第一

14、个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。流程图： 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对分查找对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分

15、继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使查找成功，或直到子表不存在，查找不成功。对分查找的条件是被查找的数据必须是有序的。对分（二分）查找过程：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(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（fix（1+9）/2）=d（5）比较，比d（5）大，下次在d（5）的右边找d(1)=13；d

16、(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 in

17、teger） as integer i=1 i代表待查找数列中的第一个元素的下标，刚开始时是1 j=9j代表待查找数列中的最后一个元素的下标，刚开始时是9（因为一共9个元素） nc=0 统计查找次数 do while i=j 第一个元素的下标要小于或等于最后一个元素的下标，否则待查找数列就不存在了 nc=nc+1 每找一次增加一次 m=fix（i+j）/2 求等查找数列中间数的下标 if d（m）=key then 判断是否找到了 search=m 找到了把下标存到变量search中 exit function 退出函数 end if if keyd（m） then 要找的数key比现在比较的中间数小 j=m-1 要找的数key比现在比较的中间数小，在待查找数列的左边找，所以新的待查找数列的最后一个元素的下标是现在中间元素下标m左边的一个 else i=m+1要找的数key比现在比较的中间数小，在待查找数列的右边找，所以新的待查找数列的最后一个元素的下标是现在中间元素下标m右边的一个 end if loop search=0end function