24点游戏的算法与源程序.doc

24点游戏的算法与源程序 高一7 高雅 Jan 5th. 2002 任务说明 24点游戏是一个大众化的益智游戏。任意给四张扑克牌（不包括大小王），只能够用加、减、乘、除以及适当的括号连接这四张牌，无论顺序，使计算结果为24，或者宣布根本就是无解的。需要注意的是，每张牌必须运算，并且只能运算一次，J、Q、K可设置为11、12、13。 本程序目的就是算出一组牌的所有解（不同形式的式子算不同解），如没有则输出无解。 算法说明 首先解决图形扑克牌的显示问题。我选择了Qcard.dll。运用其中的DrawCard过程可轻松实现扑克的显示问题，在源程序中会有具体用法。 接下来是24点算法的讨论。首先想到的是用穷举表达式的方法，然后求值。然而，由于括号的存在，使穷举表达式并非易事。实际上，括号的作用仅仅是提高运算的优先级而已，如果我们规定符号的优先级，一样可以达到要求。具体来说，设四张牌为a、b、c、d，运算符为①、②、③，表达式为a ① b ② c ③ 。如果强制规定①、②、③的优先顺序，就不必考虑括号问题了。而这3个运算符的运算顺序有3！=6种，分别是： 1．①②③ 2.①③② 3.②①③ 4.②③① 5.③①② 6.③②① 等价的表达式分别是： 1.((a①b②)c③) 2.(a①b)②(c③d) 3.(a①(b②c))③d 4.a①((b②c)③d) 5.(a①b)②(c③d) 6. a①(b②(c③d)) 显然，2和5是相同的，因此只考虑5种情况。这样，括号的问题就解决了。 接下来，就是生成a、b、c、d的全排列，注意去掉其中的相同排列。去除的方法很多，比如字典排序等，我用的是另一种方法。 用循环的嵌套生成a、b、c、d的24种全排列，记录在数组中。把每一组数当作一个四位的14进制数，把这24个数全部转化为十进制（如（6529）14=6*143+5*142+2*14+9）。这样，如果两个排列完全相同，则得到的十进制数是相等的。这样，通过对这些十进制的比较，就可以比较这些排列的相同情况。一旦遇到相同的排列，就标记上。最后生成一组没有重复的排列。 对这组排列进行以上方法的运算，就可以得到所有的结果了。注意在运算过程中除法的特殊性——除数不能为零。因为可能会用到除法，所以要考虑精度问题，这里通过结果减去24取绝对值与一个接近0的小数比较，如小于它，即可判定结果是24。 附：其他待决的问题： 图形扑克牌的遮挡问题。当窗口中的扑克牌被遮挡后，扑克牌不会重新画上，造成扑克牌遮挡后显示不全问题。应寻找Qcard.dll的有关参数。 形式不同而实质相同的解的问题。有些解虽然形式不同，但其实质是完全相同的。如3*((11+4)-7)和3*(11+(4-7))，实际上只是一种解。去掉这些相同解的问题情况较多，其较为繁琐，有待解决。 多余括号好问题。有些解的括号是多余的，应在输出前去掉。 改进程序的可玩性。增加玩家输入表达式的功能，并判断对错，还可以加上时间限制，使玩家参与到游戏中。 程序框图 VB源程序代码 需要声明所有用到的变量 Option Explicit 声明全局变量、数组 Dim cards(1 To 4) As Single, card(1 To 4) As Single Dim result(1 To 24, 0 To 4) As Integer, final(1 To 24, 1 To 4) As Integer, temp(1 To 24) As Long Dim nokey As Boolean, total As Integer, n1 As Integer, n2 As Integer, n3 As Integer, n4 As Integer, a As Integer, b As Integer, c As Integer, d As Integer, op1 As Integer, op2 As Integer, op3 As Integer, answer1 As Single, answer2 As Single, answer3 As Single, color As Integer Dim i As Integer, j As Integer, t As Integer 声明zero常量，设置0的标准，处理除法的精度问题 Const zero = 0.00001 初始化QCARD32.DLL Private Declare Function InitializeDeck Lib qcard32.dll (ByVal hwin As Long) As Integer DrawCard 子程序，画出扑克牌图样