标题:求24点,学递归   出处:Felix021 时间:Wed, 06 Jun 2007 18:51:29 +0000 作者:felix021 地址:https://www.felix021.com/blog/read.php?198 内容: 求24点,学递归 求24点,学递归 作者:邓蔚 http://blog.csdn.net/som5/archive/2004/12/13/214224.aspx 求算24点是一个极为有趣的大众智力游戏,深得许多人的喜欢。但你有没有遇到过求不出解的情况呢?是自己没有想出来还是确实无解?很难判断吧!有没有想过用电脑来求解呢。如果你有一点点VB的基础,那就让我们一起来看看该怎样用VB来求算24点吧。 电脑的思维可与人脑大相径庭。任意四个数,中间该填加号还是减号或是乘号、除号,我们一般是靠经验迅速判断的。一般来说人脑是不可能把非常复杂的所有可能的情况一一列出来检验的(我们称这种方法叫遍历),而电脑却凭借其计算速度,往往用那种所谓的死办法出奇制胜。并且根据计算机的特点,人们研究出了很多种算法来解决实际中的问题。例如我们这里要用到的递归就是其中的一种。 一、解决思路 不知你听过汉诺塔的游戏吗?那便是递归的一个经典例子。所谓递归,用通俗的语言来讲就是反复做一件类似的事情,将一件复杂的事情化为若干简单的事情而重复做。用程序的语言表示就是一个函数(也可以是多个函数)反复调用自己。其实质目标还是由多化少、由繁至简。求两个数加减乘除的结果为24的解法是显而易见的,无论是谁或电脑都可以轻而易举地解决。那我们要求4个数加减乘除的结果为24,可不可以由繁至简化为只要求两个数加减乘除的结果为24呢?答案当然是肯定的。我们先将求4个数加减乘除的结果为24的问题化为求其中任意两个数的加减乘除的结果与剩余两个数(总共3个数)加减乘除的结果为24的问题。再用类似的方法将求3个数加减乘除的结果为24的问题,化为求2个数的问题。是不是很明白? 举个例子吧:例如1、2、3、4这四个数。先取1和2出来,我们的问题是不是化为了分别求3(=1+2)、3、4;2(=12)、3、4;-1(=1-2)、3、4;1(=2-1)、3、4;2(=2/1)、3、4;0.5(=1/2)、3、4这6组数的加减乘除的结果为24的问题。然后考虑3个数的问题,如第一组3、3、4,再任取两个数如前面两个3,最终化为6(=3+3),4;0(=3-3),4;9(=33),4;1(=3/3),4这4组两个数的问题。结果很快出来了:64=24,而6=33,其中的一个3=1+2。当然一般的结果是要遍历所有的可能才得出的。 思路出来了,我们便开始将它化为程序代码。首先是构造递归主模块Function Iis24ByRef a ByRef i As Boolean,其中数组a中存放我们要求解的数,i是a中数的个数。我们要求解1、2、3、4,便调用Iis24a 4,其中的a1=1a2=2a3=3a4=4。化为3个数时,取a中的两个数进行加减乘除,将结果放入c1,a中剩余的两个数放入c2、c3,再调用Iis24 c 3,依此再类推。Iis24返回的是布尔值,True表示有解,反之无解。然后它还应当包含i=2时的求解。然后还应该有一个计算的模块Function Sumn1 n2 f,n1、n2表示用于计算的2个数,f表示计算符号(1表示加、2表示减……),该模块用于把数字和计算符号转化为相应的结果,因为要用循环遍历加减乘除,用数字表示计算符号更方便一些。然后还有输出模块,将内部的表示(符号1、2、3、4)在转化为外部的表示(+、-、、\)。这样,大概的程序就出来了。最后是界面的制作,考虑输入和输出。我的程序界面如图:4个TextBox是一个控件数组,取名为txtNum ;一个按钮名为cmdCount24;输出的是一个ListBox名为List1。 不知你通过这个程序对递归有一个更深入的了解吗?理解了思路再好好地分析实现的代码,应该会有所收获的。 二、实现代码 具体的代码如下: Function Sumn1 n2 f On Error Resume Next '用错误陷阱排除除数可能为0的错误 '计算模块 Sum = n1 If f = 1 Then Sum = Sum + n2 ElseIf f = 2 Then Sum = Sum - n2 ElseIf f = 3 Then Sum = Sum  n2 ElseIf f = 4 Then Sum = Sum / n2 End If End Function Function ShowSumn1 n2 f '输出模块 ShowSum = CStrn1 If f = 1 Then ShowSum = ShowSum + "+" + CStrn2 ElseIf f = 2 Then ShowSum = ShowSum + "-" + CStrn2 ElseIf f = 3 Then ShowSum = ShowSum + "" + CStrn2 ElseIf f = 4 Then ShowSum = ShowSum + "/" + CStrn2 End If End Function Private Sub cmdCount24_Click List1.Clear Dim a4 f4 For i = 0 To 3 ai + 1 = ValtxtNum i.Text Next i If Iis24a 4 Then '有解 End If End Sub Private Sub Form_Load '初始化界面 For i = 0 To 3 txtNum i.Text = Vali + 1 Next i End Sub Function Iis24ByRef a ByRef i As Boolean '主模块 If i = 2 Then '如果只剩两个数了,直接判断 n1 = a1 n2 = a2 '读入这两个数 For ff = 1 To 4 '遍历加减乘除(1表示加、2表示减……) If Sumn1 n2 ff = 24 Then '得出结果输出 List1.AddItem "-----------" List1.AddItem ShowSumn1 n2 ff + "=" + CStrSumn1 n2 ff Iis24 = True Exit Function ElseIf Sumn2 n1 ff = 24 Then '得出结果输出 List1.AddItem "-----------" List1.AddItem ShowSumn2 n1 ff + "=" + CStrSumn2 n1 ff Iis24 = True Exit Function End If Next ff Else '如果有i个数,先取两个数出来进行加减乘除 Dim b4 c4 For ii = 1 To i '取第一个数 n1 = aii For jj = 1 To i If jj ii Then '取第二个数 n2 = ajj '剩余的数放入数组c nb = 2 For kk = 1 To i If kk ii And kk jj Then cnb = akk nb = nb + 1 Next kk For ff = 1 To 4 '遍历加减乘除(1表示加……) c1 = Sumn1 n2 ff '取出的两个数的结果放到c中 If Iis24c i - 1 Then '递归 List1.AddItem ShowSumn1 n2 ff + "=" + CStrSumn1 n2 ff Iis24 = True Exit Function End If Next ff End If Next jj Next ii End If End Function Generated by Bo-blog 2.1.0