跟我学vb--第15课时 穷举法

穷举法：列举出所有可能的情况，逐个判断有哪些符合问题所要求的条件，从而得到问题的答案。

穷举法也称枚举法穷举法的思路：列举一切与命题相关的情况，然后根据问题设定的条件，逐个加以检查，找到满足条件的解。

但在穷举时，“与命题相关条件地情况”所包含的范围可能广，如果不加限制可能会耗费计算机的运行时间。

设计算法：设计穷举法的关键是如何列举所有可能的情况，绝对不能遗漏，最好不要重复。

在列举时注意变量的范围，可以减少工作量。

⒊某学校组织一次读书活动，计划购买各种各样书写笔作为奖品。

用100元买100支笔，其中钢笔每支5元，圆珠笔每支1元，铅笔1元5支，编程求可行的方案数是多少?⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≤≤≤=++=++1000200100515100b a c b a c b a ⒋一个N 位数的各位数N 次方之和等于这个数，称为armstrong 数（如153=13+53+33，1634=14+64+34+44）。

编一个程序，求出2、3、4位数中所有的armstrong 数。

分段：10——99；100——999；1000——9999⒌编程找出四位整数abcd 中满足下述关系的数有多少种。

abcd cd ab =+2)(四位整数的取值范围：1000——9999算法及程序⒊For a = 0 To 20For b = 0 To 100c = 100 - a - bIf 5 * a + b + 0.2 * c = 100 Then d = d + 1Next bNext aPrint d⒋For m = 10 To 99a = m \ 10b = m Mod 10If a ^ 2 + b ^ 2 = m Then Print mNext mFor m = 100 To 999a = m \ 100b = (m - a * 100) \ 10c = m Mod 10If a ^ 3 + b ^ 3 + c ^ 3 = m Then Print mNext mFor m = 1000 To 9999a = m \ 1000b = (m - a * 1000) \ 100c = (m - a * 1000 - b * 100) \ 10d = m Mod 10If a ^ 4 + b ^ 4 + c ^ 4 + d ^ 4 = m Then Print mNext m⒌For a=1 to 9For b=0 to 9For c= 0 to 9For d= 0 to 9If (a*10+b+c*10+d)^2=a*1000+b*100+c*10+d then e=e+1Next dNext cNext bNext a?e。

算法的程序实现一、解析法：解析法是在分析具体问题的基础上，抽取出一个数学模型，这个数学模型能用若干个解析表达式表示出来，解决了这些表达式，问题也就得以解决了。

解析法是程序设计中最常用的算法之一。

关键：分析问题，得出解析表达式。

二、穷举法：也叫枚举法、列举法，是将求解对象一一列举出来，逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将得以解决。

关键：穷举范围验证条件穷举用for循环和do循环实现。

穷举范围要要包括所有可能，不能遗漏，在此前提下要尽量缩小范围，提高效率。

三、查找：数组：想同类型的变量集合，集合中的每个元素都是独立的变量，它们能够通过数组序号被引用。

（一）顺序查找：从数据的第一个元素开始，从前向后按数据的顺序查找指定的关键值。

程序通式：x=[表达式] ’从表达式获取要查找的关键值for i=0 to [数组最大下标] ’通过循环实现逐一查找。

也可用do循环if x=[数组名](i) then ’验证数据和关键值是否匹配，匹配表示找到……’找到了以后做什么呢？就是这个“。

”……exit do ’如果确信匹配项只有一个，那么找到后就退出循环，不需要继续查找了。

End ifNext iIf i > [数组最大下标] then 。

’如果找到循环就会提前退出，i就会小于等于终值，因此，i大于终值说明没找到到。

如果没找到就。

说明：如果匹配项有很多项的话，找到后就不能用exit do退出循环，而应继续向下查找，此时应该用flag变量做一个标记，初始值为0，找到后，把它改为1。

（二）二分查找：也叫折半查找，设置一个上界和一个下界，然后取上下界的中间元素与指定的关键值比对，如果相符则表示找到，不符则根据关键值在左半部还是右半部舍弃另外一半，调整上、下界，重取中间值查找。

当下界大于上界时则表示没有该数据。

二分查找的数据必须是有序的。

通式：x=[表达式] ’获取查找关键值。

intlow=0inthigh=[数组最大元素下标]intmid= (intlow+inthigh) \ 2 ’最初的一次查找do until intlow > inthigh ’进入循环查找，直到intlow>inthigh时，表示找不到if a (intmid) = x then ’条件匹配，表示找到，则退出循环，不再继续查找exit doelseif a(intmid) < x then ’找到的比目标值小，则调整intlowintlow=intmid+1intmid= (intlow+inthigh) \ 2 ’重设intmid，进行下一次查找else ’以上条件都不满足，表示找到的比目标值大，需调整inthigh inthigh=intmid-1intmid= (intlow+inthigh) \ 2endifloopif intlow>inthigh then ’如何判断找没找到呢？就通过intlow和inthigh比较来实现。

教学设计“穷举法（VB）”教材：《算法与程序设计》教科版内容：用穷举法解决问题学生：南京三中高二（12）班教材分析与教法：首先，我校选择《算法与程序设计》这本教材，对相当一部分学生来说，还是比较难和比较枯燥的。

因此，我在教学中，一直尽量使用趣味性程序等手段，贴近学生生活，将课堂的气氛调动得活跃起来，并可培养学生对这门课的兴趣。

穷举法是算法中比较常见，日常运用很很多的一种。

在课本和等级考试中都作为一个重要的部分出现。

经典问题有鸡兔同笼、百鸡百钱等。

课本在介绍穷举法时用的例子是一个相对复杂的演讲比赛分组的问题。

我个人认为，这样的一个引入部分不适合我们的学生，一是学生不是很感兴趣，二是比较复杂。

其次，在课本第三章，我的教学方法借鉴了数学课的教法：从简单问题详细剖析，推出一般情况，得到结论（算法理论），再从理论推展开区，再解决其他问题。

根据我校学生的特点，我选择了一个反暴力破解的例子引入，要反暴力破截，就必须了解它的原理。

首先让学生自己来尝试暴力破解一个密码。

这样，学生马上就能体会到什么叫穷举。

从简单破解2位数，到学生无法简单破解3位数的密码，自然引出这样单一的重复的过程可以由计算机来解决。

了解了暴力破解的原理，我们也就了解了穷举法的原理、特点。

了解原理后，我使用两个例题让学生练习，以便理解、运用穷举法。

1、元旦义卖会问题。

由于三中每年有元旦各班义卖的传统，因此，这个话题很能引起学生的兴趣（该问题类似鸡兔同笼）。

2、百鸡百钱问题。

通过这两个问题，由简单到复杂，学生便可基本掌握穷举法的应用。

教学目标：1、知识与技能：掌握穷举法的概念、特点，并能初步运用编程。

2、过程与方法：能通过自己分析问题，得出算法思想，从而锻炼自己解决问题的能力3、情感、态度与价值观：通过与生活中的实际例子结合，认识到算法在实际生活中的用途，对这门功课的兴趣更加浓。

教学准备：教师事先编写一个密码门程序，给学生体验用。

教学要点：穷举法的关键点：怎样确定穷举的范围。

第十五课 VB程序设计实战教师通过本课的一个小游戏让学生对前几课的所学的内容进行复习，并根据所学的知识锻炼学生的动手和动脑能力。

通过这个小游戏的制作过程引导学生去理解和学习编写计算机程序的方法。

建议2个课时完成。

编写九宫格拼图游戏程序教师通过活动的介绍引导学生了解这个游戏的原理，同时可以让学生利用前面学过的PHOTOSHOP制作游戏需要的小卡片。

让学生想象游戏可能出现的几种情况，为接下来的游戏做好准备。

游戏分析学生要认真思考、理解游戏完成的每个步骤，想象每个步骤出现的效果，以及每步实现的算法，并根据空白图片可能出现的位置让同学们去推理，锻炼学生的分析能力。

详细设计可以根据详细设计对游戏功能模块分析指导学生去分析问题，并养成程序设计规范化的良好习惯。

引导学生根据自己的理解去划分模块，设计程序设计结构流程图。

让学生学会用模块化的思想去思考、解决问题，学会制作流程图，帮助整理思路，形成系统化的思维。

编写程序这是一个VB的综合实践课，学生可结合程序代码和相应的注释，理解程序中的语言的具体含义，能比较熟练的使用VB语言编写程序。

程序编写最后是对程序的调试和运行。

让学生对自己的游戏设计过程进行总体设计思路的描述，培养学生良好的分析问题和设计程序习惯。

实践与探索让学生练习修改程序，实现不同的游戏功能，锻炼学生的创新能力。

同时还可以添加一些特殊功能，比如登记游戏者的姓名、成绩及统计排行榜等。

可以根据学生自己的想法去完善游戏，使游戏更好玩。

链接“链接”帮助学生了解更多的VB系统中的工程概念等有关内容，让学生树立工程意识，用工程的思想处理问题。

中国书法艺术说课教案今天我要说课的题目是中国书法艺术，下面我将从教材分析、教学方法、教学过程、课堂评价四个方面对这堂课进行设计。

一、教材分析：本节课讲的是中国书法艺术主要是为了提高学生对书法基础知识的掌握，让学生开始对书法的入门学习有一定了解。

书法作为中国特有的一门线条艺术，在书写中与笔、墨、纸、砚相得益彰，是中国人民勤劳智慧的结晶，是举世公认的艺术奇葩。

V B常用算法4递推穷举积分VB常用算法----递推与穷举一、初等数学1、递推法又称为“迭代法”，其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。

每次重复都在旧值的基础上递推出新值，并由新值代替旧值。

问题：猴子吃桃子小猴子有若干桃子，第一天吃掉一半多一个；第二天吃掉剩下的一半多一个…..；如此，到第七天早上要吃时，只剩下一个桃子。

问小猴子一开始共有多少桃子？分析：可以最后一天桃子数推出倒数第二天的桃子数；再从倒数第二天推出倒数第三天桃子数………..设第n天桃子数为x n，前一天桃子数是：x n－1，则有关系：xn ＝xn－1/2-1 或 xn-1=（xn+1）*2程序如下：Private Sub Command1_Click()Dim n% , i% , x%x = 1 '第七天桃子数Print "第七天桃子数: 1只"For i = 6 To 1 Step -1x = (x + 1) * 2Print "第" & i & "天桃子数:" & x & "只"Next iEnd Sub2、穷举法又称枚举法，即将所有可能情况一一测试，判断是否满足条件，一般用循环实现。

问题：百元买百鸡问题。

假定小鸡每只5角；公鸡每只2元；母鸡每只3元。

现在有100元，要求买100只鸡，编程列出所有可能的购鸡方案。

分析：设母鸡、公鸡、小鸡分别x、y、z只，则有：x＋y＋z＝1003x＋2y＋0.5z＝100程序一：Private Sub Command1_Click()Dim x%, y%, z%Print "百钱买百鸡问题的各种购买方案"Print "母鸡数公鸡数小鸡数"For x = 0 To 100For y = 0 To 100For z = 0 To 100If x + y + z = 100 And 3 * x + 2 * y + 0.5 * z = 100 ThenPrint x, y, zEnd IfNext zNext yNext xEnd Sub程序二（优化）Private Sub Command2_Click()Dim x%, y%Print "百钱买百鸡问题的各种购买方案"Print "母鸡数 公鸡数 小鸡数"For x = 0 To 33For y = 0 To 50If 3 * x + 2 * y + 0.5 * (100 - x - y) = 100 ThenPrint x, y, 100 - x - yEnd IfNext yNext xEnd Sub二、高等数学求积分近似计算积分：s=∫13(x 3+2x+5)dx 分析：矩形法数值积分的思想是，将积分区间划分为n 个等分，以函数y=f(x)曲线和坐标轴x 上的取值a ，b 为上下边界，以n 个小矩形的面积S i 近似小曲边型面积，则所求定积分值近似为：∑≈ni S S 1将积分区间n 等分以后其小区间长度为h=(b-a)/n ，其中a 与b 为积分下、上限，则：S 1=f(a)*h ，S 2=f(a+h)*h ，S 3=f(a+2*h)*h ，…，S n =f(a+(n-1)*h)*h因为在计算小矩形面积时要多次计算函数f(x)，所以将被积函数编写为函数过程。

第16章 穷举算法与实验穷举方法是基于计算机特点而进行解题的思维方法。

一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。

这样解决问题的方法我们称之为穷举算法。

穷举算法特点是算法简单，但运行时所花费的时间量大。

因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

虽然穷举法效率并不高，但是适应一些没有明显规律可循的问题的解决。

因为穷举算法就是从所有可能的情况中搜索正确的答案，所以一般可按如下步骤： 第1步: 对于一种可能的情况，列举出来并计算其结果；第2步：判断结果是否满足要求，如果不满足则执行第1步来搜索下一个可能的情况，如果满足要求，则表示寻找到一个正确的答案，执行下一步操作，如寻找其他正确（合适）的答案或者中断循环。

16.1三角形数问题16.1.1 问题描述将 ,F ,E ,D ,C ,B ,A 这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。

求使三角形三条边上的变量之和相等的全部解。

如图就是一个解。

A 6B C 3 1D F 2 4E 516.1.2 问题分析程序引入变量123456,,,,,i i i i i i ，代表,F ,E ,D ,C ,B ,A 并让它们分别顺序取1至6的正整数，在它们互不相同的前提条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。

当这些变量取尽所有的组合后，程序就可得到全部可能的解。

细节见下面的程序。

【程序1】%穷举法解三角形数 for i1=1:6 for i2=1:6 if i1==i2 continue;endfor i3=1:6if i1==i3 || i2==i3continue;endfor i4=1:6if i1==i4 || i2==i4 || i3==i4continue;endfor i5=1:6if i1==i5 || i2==i5 || i3==i5 || i4==i5continue;endfor i6=1:6if i1==i6 || i2==i6 || i3==i6 || i4==i6 || i5==i6continue;endif i1+i2+i4==i1+i3+i6 && i1+i2+i4==i4+i5+i6fprintf ('%6d\n',i1) ;fprintf ('%4d%4d\n',i2,i3) ;fprintf ('%2d%4d%4d\n\n',i4,i5,i6) ;endendendendendendEnd16.1.3 问题讨论按穷举法编写的程序通常不能适应变化的情况。

穷举法重点：1、穷举法的基本思想2、利用穷举法设计程序的基本步骤和方法3、穷举技巧（方案的确立和变量的安排等）难点：1、确定穷举方案和安排变量2、穷举范围的确定3、写出符合条件的判断语句导入：假设你有这样一个密码箱，已经很久没有打开了，现在你想打开它，但是忘了密码，你会怎么做？对，我们可以先转动一个密码位，然后固定其他密码位，一个一个号码进行尝试。

这个过程就叫做穷举。

案例：穷举法的思路：列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解答。

用于解决“是否存在”和“有多少可能性”等类型问题。

穷举算法模式：（1）问题解的可能搜索的范围：用循环或循环嵌套结构实现；（2）写出符合问题解的条件：用选择语句实现。

实例分析：假设密码是一个5位数。

只记得密码为67□□8，其中百位和十位的数字记不清了，但知道该数能够被78整除，也能被67整除。

同学们能不能设计一个算法帮找出这个密码。

思考：题目的未知数有哪些？所需哪些变量？题目给出的条件是什么？（1）分析问题：求出一个5位数67□□8，能同时被78和67整除。

我们可以从变量的取值范围入手，列举出所有情况：这个密码是个五位数67□□8，有2位数字是未知的，把这2位数字的所有可能性演变一次（0—9），就可以把可能的情况穷举完。

再把各位数字合成一个5位数，判断是否同时被78和67整除就可以了。

（2）设计算法如何确定求解的算法呢?这个问题适合用穷举法进行搜索。

设计穷举法的关键是如何列举所有可能的情况。

因为2位数字未知，而且知道每位的变化范围，所以要用2个循环语句实现2位数字的取值，列举出所有的可能值。

然后组成5位数d，判断d能否同时78和67整除即可得到结果。

所以还需要一个判断语句对列举的五位数进行判断。

分别用a1、a2表示这2位求知数字，在它们各自的范围中变化，然后组成5位数d，判断d 能否同时被78和67整除即可得到结果。

（3）编写程序如下：Private Sub Command8_Click()Dim d As LongDim a1,a2 As IntegerFor a1 = 0 To 9For a2 = 0 To 9d = 67000 + a1 * 100 + a2 * 10 + 8If (d Mod 78 = 0) And (d Mod 67 = 0) Then Print dNext a2Next a1End Sub（4）调试程序程序运行后单击窗体可得结果：67938复核知这个结果是符合题意了。

穷举法穷举法是程序设计中使用最为普遍的一种基础算法。

计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老算法。

它一般是在一时半会找不到解决问题的更好途径，即从数学上找不到求解的公式或规律时，根据问题中的“约束条件”，将求解的所有可能情况一一列举出来，然后再逐一验证它否符合整个问题的求解要求，从而得到问题的所有解。

示例1：求满足表达式A+B=C的所有整数解，其中A,B,C为1~3之间的整数。

【分析】本题非常简单，即枚举变量A，B，C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。

【算法】算法用伪代码描述如下：for A:=1 to 3 dofor B:=1 to 3 dofor C:=1 to 3 doif(A+B=C) thenwriteln(A,’’,B,’’C);【流程图】所谓穷举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定那些是无用的，哪些是有用的。

能使命题成立的，即为解。

在本案例中解变量有3个：A，B，C。

其中：解变量A的可能取值范围A∈｛1,2,3｝解变量B的可能取值范围B∈｛1,2,3｝解变量C的可能取值范围C∈｛1,2,3｝从而问题的可能解有3*3*3=27个，可能解集在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。

穷举法的适用范围：其一，能确定解变量（枚举变量）的个数n，其二，每个解变量Ai（1<=i<=n）的可能值能确定范围且能连续取得。

设解变量的个数是n，Ai1----解变量Ai的最小值；Aik----解变量Ai的最大值（1≤i≤n）；即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank算法框架如下（伪代码）：for A1←A11 to A1k do……for Ai←Ai1 to Aik do……for An←An1 to Ank doif状态（A1,…,Ai,…,An）满足检验条件then 输出问题的解穷举法（枚举法）的特点是算法简单，但是有时运算量大。

穷举法——计算机求解问题的一种方法概述所谓穷举法，就是在列举所有可能的解，逐一检验直至找到真正的解。

例如，“找出整数n的所有因子”这一问题就可以采用穷举法。

所有可能的解（即因子）落在集合{1, 2, 3, …, n}内，分别用n除一除，余数为0则是因子，否则不是因子。

银行卡密码是6位数字，采用穷举法破解就是把所有6位数都试一遍，那一共要试106次。

人来试是受不了的，而计算机也许可以（因为速度更快）。

所谓暴力破解法正是这样做的。

例一题目：一个首项大于0的递增等差数列前四项和为26，前四项积为880，求该数列的第20项的值。

提示：如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，这个常数叫做等差数列的公差。

例如：等差数列：1，3，5，7，9，11。

该数列的公差是2，第5项值是9。

采用穷举法解题说明如下。

假设数列首项为a，差值为d，有：a+ a+d + a+2d + a+3d = 26a*(a+d) * (a+2d)*(a+3d) = 880如何求出a和d？答：穷举（a，d）的组合。

数列首项a从1穷举到5，差值d可从1穷举到5。

a从1开始是因为题目指出首项大于0，a到5为止是因为数列前4项之和为26，而4*5+6*1（差值d至少为1）等于26。

差值d从1开始是因为是等差数列，差值至少为1，到5为止的因为6*5>26。

这样，构造出了所有可能的解，即（a，d）的组合：(1, 1)，(1, 2), (1, 3), (1, 4), (1, 5), (2, 1),(2,2),(2,3),(2,4),(2,5)…(5,1), (5,2),(5,3),(5,4),(5,5)。

算法描述如下：for a=(1,2,3,4,5):for d=(1,2,3,4,5):如果a+ a+d + a+2d + a+3d等于26且a*(a+d) * (a+2d)*(a+3d)等于880，则：求得数列第20项是a+19*d；算法结束。