用穷举法求解问题的实践示例

1、枚举算法及其程序实现（复习） 谢丹,知识回顾 枚举算法的基本思想 根据问题本身的性质,将问题的可能解一一列举,并根据题目的条件逐一作出判断,从中找出符合条件的解。即使中途找到合适的解也要继续找下去，要将所有可能的解找完才结束。在列举的过程中,既不能遗漏,也不能重复。,枚举算法的程序实现,1.根据枚举算法的主要思想：一一列举，逐个判断。因此，一般情况下枚举算法的代码具有以下特点： （1）用循环语句在一定范围内列举所有可能的解。 （2）用选择语句判断和选择真正的解。 2.枚举算法的一般格式： For（列举所有可能的解） If 可能是正确解 Then 输出该解或计数 Next,例题解析 例1 鸡兔同

2、笼问题。一群鸡和兔关在一个笼子里,其中共有头30个,脚60只,问鸡和兔各几只?现用VB程序求解,程序如下: Private Sub Command1_Click() Dim i As Integer, j As Integer For i=1 to 30 j= If Then List1.additem 鸡:+str(i)+只,兔+str(j)+只。 End if Nxt i End Sub,(1)该事件处理过程采用的算法是。(填:解析算法/枚举算法) (2)在程序中和划线处,填入适当的语句或表达式,把程序补充完整。 程序中划线处应填入。 程序中划线处应填入。 解析:由语句list1.addi

3、tem 鸡:+str(i)+只,兔+str(j)+只。可知,变量i表示鸡的数量,j表示兔的数量,所以处应填入30-i。处判断脚的数量是否等于60,即处的条件表达式i*2+j*4=60,只要满足两个条件,即把数据展示在列表框中。由上分析可知,循环变量i表示鸡的数量,其值由1到30,逐一与条件“i*2+j*4=60”进行比对,若符合的进行展示,由此特征可判断该程序是典型的枚举算法程序。 答案: (1)枚举算法(2)30-i i*2+j*4=60,例2 水仙花数是指其各位数字的3次幂之和等于它自身的数,例如153是水仙花数，因为153=1+125+27。打印100999中的水仙花数的算法如下: Pr

4、ivate Sub command1_click() For i=100 to 999 a=i100 得到i的百位数字 b=i10 mod 10 得到i的十位数字 c= Ifi= Then print i Next i End Sub 程序中划线处应填入。 程序中划线处应填入。 答案: i mod 10或 i-a*100-b*10 a3+b3+c3,在设定多个变量的列举范围时，可以利用验证条件，尽可能缩小列举范围，减少列举变量，从而减少循环的嵌套。 例3 百鸡百钱问题：100元钱买100只鸡，公鸡5元一只，母鸡3元一只，小鸡一元3只。代码如下： For x=1 To 100 For y=1 T

5、o 100 For z=1 To 100 If x+y+z=100 and 5*x+3*y+z/3=100 Then 输出该数组解或计数 Next z Next y Next x,利用验证条件，代码可优化为: For x=1 To 20公鸡最多不超过20只 For y=1 To 33母鸡最多不超过33只 z=100-x-y If 5*x+3*y+z/3=100 Then 输出该数组解或计数 Next y Next x,巩固提高 例3 编写“加法练习题生成器”程序，实现如下功能：在文本框Text1中输入题数n，单击“生成”按钮Command1，在列表框List1中显示n个两数之和小于100的加法练习题。实现上述功能的VB程序如下，请在划线处填入合适的代码。 Private Sub Command_Click() Dim n As Integer, i As Integer, a As Integer, b As Integer Randomize n=Val(Text1.Text) i=_ Do While i=n a=Int(Rnd * 100) b=Int(Rnd * 100),If_ Then List1.AddItem”(”+Str(i)+”)”+Str(a)+”+”+Str(b)+”=” i=i+1 End If Loop End Sub 解析：循环变量i的初值