正文:摘要:穷举法是数学竞赛题的一种解题思想方法。解题时,根据题目的要求,把可能的答案逐一列举出来,然后确定正确的答案,这种方法叫做穷举法。穷举法用时间上的牺牲换来问题答案的全面性。在计算机没有发明之前,这种方法在求解一些问题时理论上是可行的,但仅靠人工来操作,效率低下,不能保证解的全面性。随着计算机运算速度的飞速发展,穷举法的形象已经不再是最低等和原始的无奈之举,比如经常有黑客在几乎没有任何已知信息的情况下利用穷举法来破译密码,足见这种方法还是有其适用的领域的。VB语言以其自身的强大功能及其诸多优点得到了广泛应用,特别是在各类中职学校,更是把VB教学作为语言类教学的重中之重。本人从事计算机高级语言类教学多年,对算法有较深的了解,在此就结合穷举法在VB求解趣味程序中的应用进行一些探讨,以求拓宽算法(求解问题的方法)在求解问题中的灵活应用。
关键词:穷举法,VB,趣味程序,应用,算法
穷举法在求解趣味问题程序中体现出强大的作用,下面就例举四个与现实生活有紧密联系的经典趣味问题,采用VB语言进行分析求解,采用的算法为穷举法。
一、趣味程序设计编程案例1(百钱买百鸡?)
1.
问题摘要
中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?
2.
问题分析与算法设计:
设鸡翁、鸡母、鸡雏的个数分别为x,y,z,题意给定共100钱要买百鸡,若全买公鸡最多买20只,显然x的值在0~20之间;同理,y的取值范围在0~33之间,可得到下面的不定方程:
5x+3y+z/3=100
x+y+z=100
所以此问题可归结为求这个不定方程的整数解。
由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下,可通过对未知数可变范围的穷举,验证方程在什么情况下成立,从而得到相应的解。
3.VB程序实现如下:
Private Sub Command1_Click()
List1.FontSize = 15
List1.Clear
List1.AddItem "公鸡 母鸡 小鸡"
For x = 1 To 19
For y = 1 To 33
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
p = Format(x, "@@@@") & Format(y, "@@@@@") & Format(z, "@@@@@@")
List1.AddItem p
End If
Next
Next
End Sub
4.
问题的进一步讨论:
这类求解不定方程总理的实现,各层循环的控制变量直接与方程未知数有关,且采用对未知数的取值范上穷举和组合的方法来复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数,提高程序的执行效率?
二、趣味程序设计编程案例2(谁在说谎?)
1.
问题摘要
张三说李四在说谎,李四说王五在说谎,王五说张三和李四都在说谎。现在问:这三人中到底谁说的是真话,谁说的是假话?
2.
问题分析与算法设计:
分析题目,每个人都有可能说的是真话,也有可能说的是假话,这样就需要对每个人所说的话进行分别判断。假设三个人所说的话的真假用变量A、B、C表示,等于1表示该人说的是真话; 表示这个人说的是假话。由题目可以得到:
*张三说李四在说谎 张三说的是真话:a==1 and b==0
或 张三说的是假话:a==0 and b==1
*李四说王五在说谎 李四说的是真话:b==1 and c==0
或 李四说的是假话:b==0 and c==1
*王五说张三和李四都在说谎 王五说的是真话:c==1 and a+b==0
或 王五说的是假话:c==0 and a+b!=0
上述三个条件之间是“与”的关系。将表达式进行整理就可得到VB语言的表达式。
穷举每个人说真话或说假话的各种可能情况,代入上述表达式中进行推理运算,使上述表达式均为“真”的情况就是正确的结果。
3.VB程序实现如下:
Private Sub Command1_Click()
Dim a As Integer, b As Integer, c As Integer
For a = 0 To 1
For b = 1 To 1
For c = 0 To 1
If (((a = 1 And b = 0) Or (a = 0 And b = 1)) And ((b = 1 And c = 0) Or (b = 0 And c = 1))_ And (((c = 1) And a + b = 0)) Or ((c = 0) And (a + b = 1))) Then
List1.AddItem ""
List1.AddItem " 张三说" & IIf(a = 1, "真话", "假话")
List1.AddItem " 李四说" & IIf(b = 1, "真话", "假话")
List1.AddItem " 王五说" & IIf(c = 1, "真话", "假话")
End If
Next
Next
Next
End Sub
三、趣味程序设计编程案例3(委派任务?)
1.
问题摘要
某侦察队接到一项紧急任务,要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人,但有以下限制条件:1)A和B两人中至少去一人;2)A和D不能一起去;3)A、E和F三人中要派两人去;4)B和C都去或都不去;5)C和D两人中去一个;6)若D不去,则E也不去。问应当让哪几个人去?
2.
问题分析与算法设计:
用A、B、C、D、E、F六个变量表示六个人是否去执行任务的状态,变量的值为1,则表示该人去;变量的值为0,则表示该人不参加执行任务,根据题意可写出表达式:
a+b>1 A和B两人中至少去一人;
a+d!=2 A和D不能一起去;
a+e+f==2 A、E、F三人中要派两人去;
b+c==0或b+c==2 B和C都去或都不去;
c+d==1 C和D两人中去一个;
d+e==0或d==1 若D不去,则E也不去(都不去;或D去E随便)。
上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况,代入上述表达式中进行推理运算,使上述表达式均为“真”的情况就是正确的结果。
3.VB程序实现如下:
Private Sub Command1_Click()
Dim a As Integer, b As Integer, c As Integer, d As Integer, e As Integer, f As Integer
For a = 1 To 0 Step -1
For b = 1 To 0 Step -1
For c = 1 To 0 Step -1
For d = 1 To 0 Step -1
For e = 1 To 0 Step -1
For f = 1 To 0 Step -1
If a + b >= 1 And a + d <> 2 And a + e + f = 2 And (b + c = 0 Or b + c = 2) And c + d = 1 And (d + e = 0 Or d = 1) Then
List1.AddItem "A will " & IIf(a = 1, "", "not") & " be assigned" & "(去)"
List1.AddItem "B will " & IIf(b = 1, "", "not") & " be assigned" & "(去)"
List1.AddItem "C will " & IIf(c = 1, "", "not") & " be assigned" & "(去)"
List1.AddItem "D will " & IIf(d = 1, "", "not") & " be assigned" & "(不去)"
List1.AddItem "E will " & IIf(e = 1, "", "not") & " be assigned" & "(不去)"
List1.AddItem "F will " & IIf(f = 1, "", "not") & " be assigned" & "(去)"
End If
Next
Next
Next
Next
Next
Next
End Sub
四、趣味程序设计编程案例4(邮票组合问题)
1.
问题摘要
某人有四张3分的邮票和三张5分的邮票,用这些邮票中的一张或若干张可以得到多少种不同的邮资?
2.
问题分析与算法设计:
将问题进行数学分析,不同张数和面值的邮票组成的邮资可用下列公式计算:
S=3*i+5*j
其中i为3分邮柰的张数,j为5分的张数
按题目的要求,3分的邮票可以取0、1、2、3、4张,5分的邮票可以取0、1、2、3张。采用穷举方法进行组合,可以求出这些不同面值不同张数的邮标组合后的邮资。
3.VB程序实现如下:
Private Sub Command1_Click()
List1.Clear
For san = 0 To 4
For wu = 0 To 3
youzi = san * 3 + wu * 5
If youzi > 0 Then
List1.AddItem "三分的邮票取" & san & "张" & " 五分的邮票取" & wu & "张" _
& "邮资为:" & Format(youzi, "@@") & "分"
List1.AddItem Chr(13) & Chr(10)
End If
Next
Next
MsgBox "共有" & List1.ListCount / 2 & "种邮资组合!", 64, "输出结果:"
End Sub
19种邮资组合: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27
总之,灵活应用穷举法,可以很方便的求解许多现实生活中的趣味问题,同时也可以进一步拓宽自己解决问题的思维,体味到计算机程序设计的乐趣,从而提高自己编程解决实际问题的能力。