”复杂“的代码，简单的算法→【多过程递归】算24代码

香川群子

最近正在学习递归用法。

按照间接递归的思路，写了个算24的代码，给大家分享。


同时，给出一组算24难题，基本上是常规算法算不到的。


1,3,4,6
1,4,5,6
1,4,5,6
1,5,5,5
1,6,6,8
2,4,10,10
2,5,5,10
2,5,7,9
2,7,7,10
3,3,7,7
3,3,8,8
3,8,8,10
4,4,7,7
4,4,10,10
4,4,8,9
4,6,6,10
4,6,7,9
5,6,6,9
6,6,6,10
7,8,8,10

香川群子

下面进入代码过程。


首先，思考算24的实质，就是任取4个数(一般为1-10)【例如取4个数：a1、a2、a3、a4】

通过每次2个数值的加、减、乘、除4种算法中的一个，得到一个【2元素计算结果】
【例如 a1 和 a2 用加法：计算结果=a1+a2】

接着将这个【2元素计算结果】继续以加、减、乘、除4种算法中的一个，
和剩余的2个数中的一个，或者剩余两个数的另一次计算结果，继续计算，得到【3元素计算结果】
【例如对于计算结果(a1+a2)用乘法：（a1+a2）*a3，或（a1+a2）*a4】
或者，也包含直接以a3、a4也同样计算一次，如用减法得到结果【(a3-a4)】

最后，将这个【3元素计算结果】继续以加、减、乘、除4种算法中的一个，
和剩余的最后一个数，继续计算，就最后得到4元素计算结果了
【例如：（a1+a2）*a3-a4，或（a1+a2）*a3/a4等】
或者，也包含第一次计算结果（a1+a2）和第二次计算结果（a3-a4）的计算结果【如(a1+a2)*(a3-a4)】

这样，一般说来，4个元素通过3次计算过程，就可以得到一个最终的，【仅使用加、减、乘、除4种算法的】计算结果。
即：

如果这个最终计算结果正好=24，计算找到了一个解。



…………
实际人脑计算时，大多凭借经验，
无法做遍历计算的。

因为，4个数的排列顺序，就有4*3*2*1=24种，再加上加、减、乘、除的排列，就更多了。

剔除等效计算结果，实际会有2250种不同的计算方法。
（如果4个数中有重复，则计算结果会减少，但即使4个数全部相同，也最少有100多种计算方式，约40种不同的计算结果。）



因此，使用VBA来计算，成为保证搜寻到所有符合条件解的必然。

香川群子

接下来，用递归的思路：

递归的要求：
1. 每次计算以后，复杂度要降低。
2. 计算过程是可以重复的。即，代入参数不同，但参数类型和计算方法，以及判断标准一致。

用术语来说，就是，具有相同的入口、出口和处理条件。


…………

我是采用正向处理过程来处理的。

但是，思考递归时的思路，则是逆向的。


下面进入正题：

首先，思考计算最终结果的出口，那就是，计算结果=24.

入口呢？
前面已经分析过了，应该是第三步计算过程，即两个计算结果参数，

而处理过程，也很简单，就是【加、减、乘、除】


因此，写出代码如下：

Sub calc2(c(), t1, t2)
……
End Sub

递归子过程命名为【calc2】，即最后两个元素的计算。参数1为数组c()含两个计算对象元素就够了。
……
后来发现，需要输出中间计算结果的文字列，所以后来又增加了t1,t2两个入口参数。
（实际可以用数组储存的方式解决，但考虑到代码可读性，后来就没有改。）


……
下面，举例为加法的处理过程。

s = c(1) + c(2) '计算c(1)和c(2)最后两个元素的加法结果，
    If Round(s, 12) = t Then '如果计算结果=t（即计算最终目标值，算24时当然就会在代码开始时将t赋值为=24）
        k = k + 1 '结果数组序号+1
        d(k) = "=" & t1 & "+" & t2 '在结果数组d中写入计算结果
        e(k) = " =" & t1 & "+" & t2 '在结果数组e中写入计算结果的文字表达式（其实两者内容几乎一样，只差一个空格）
    End If


…………
好了，处理过程就是这么简单。

如果略去输出结果到数组的代码部分，代码可以省略为一行。

即：if 【最终计算结果】=【目标值】 then 【输出结果到数组，结束】



……
然而，考虑到加、减、乘、除四种运算结果的排列，代码显然就【复杂】了。
（实际上，这里的复杂，仅仅是指写的复杂，或代码行数较多，实际上理解非常简单。）

请看实际代码如下：

1. Sub calc2(c(), t1, t2)
   
2.     s = c(1) + c(2)
   
3.     If Round(s, 12) = t Then
   
4.         k = k + 1
   
5.         d(k) = "=" & t1 & "+" & t2
   
6.         e(k) = " =" & t1 & "+" & t2
   
7.     End If
   
8.    
   
9.     s = c(1) - c(2)
   
10.     If Round(s, 12) = t Then
    
11.         k = k + 1
    
12.         d(k) = "=" & t1 & "-" & t2
    
13.         e(k) = " =" & t1 & "-" & t2
    
14.     End If
    
15.    
    
16.     s = c(2) - c(1)
    
17.     If Round(s, 12) = t Then
    
18.         k = k + 1
    
19.         d(k) = "=" & t2 & "-" & t1
    
20.         e(k) = " =" & t2 & "-" & t1
    
21.     End If
    
22.    
    
23.     s = c(1) * c(2)
    
24.     If Round(s, 12) = t Then
    
25.         k = k + 1
    
26.         d(k) = "=" & t1 & "*" & t2
    
27.         e(k) = " =" & t1 & "*" & t2
    
28.     End If
    
29.         
    
30.     If c(1) <> 0 Then
    
31.         s = c(2) / c(1)
    
32.         If Round(s, 12) = t Then
    
33.             k = k + 1
    
34.             d(k) = "=" & t2 & "/" & t1
    
35.             e(k) = " =" & t2 & "/" & t1
    
36.         End If
    
37.     End If
    
38.    
    
39.     If c(2) <> 0 Then
    
40.         s = c(1) / c(2)
    
41.         If Round(s, 12) = t Then
    
42.             k = k + 1
    
43.             d(k) = "=" & t1 & "/" & t2
    
44.             e(k) = " =" & t1 & "/" & t2
    
45.         End If
    
46.     End If
    
47.    
    
48. End Sub

复制代码

其中，使用Round函数的目的，在于解决除法精度误差的问题。

如果直接使用=判断，则很多除法结果会因为产生误差而被舍去。

呵呵。

香川群子

下面的递归过程，是最终二元素计算的上一层，即三元素计算过程。

Sub calc3(b(), t1, t2, t3)
    ……
End Sub

递归子过程命名为【calc3】，即三个元素的计算。
参数1为数组b()含三个计算对象元素，以及文字结果t1、t2、t3。

思考计算最终结果的出口，就是递归过程【calc2】需要的入口，即两个元素的计算结果。


入口呢？那么就是三个元素b()，以及它们的文字表达式，t1,t2,t3

而处理过程，也很简单，仍然是【加、减、乘、除】
但也需要包含3个元素的所有排列方式。


具体代码如下：
（同样是：代码很【复杂=行数很多】，但是理解很容易，很简单）

1. 
   
2. Sub calc3(b(), t1, t2, t3)
   
3.    
   
4.     c(1) = b(1) + b(2)
   
5.     c(2) = b(3)
   
6.     calc2 c, "(" & t1 & "+" & t2 & ")", t3
   
7.    
   
8.     c(1) = b(2) + b(3)
   
9.     c(2) = b(1)
   
10.     calc2 c, "(" & t2 & "+" & t3 & ")", t1
    
11.    
    
12.     c(1) = b(3) + b(1)
    
13.     c(2) = b(2)
    
14.     calc2 c, "(" & t3 & "+" & t1 & ")", t2
    
15.    
    
16.     If b(1) >= b(2) Then
    
17.         c(1) = b(1) - b(2)
    
18.         c(2) = b(3)
    
19.         calc2 c, "(" & t1 & "-" & t2 & ")", t3
    
20.     End If
    
21.     If b(2) > b(1) Then
    
22.         c(1) = b(2) - b(1)
    
23.         c(2) = b(3)
    
24.         calc2 c, "(" & t2 & "-" & t1 & ")", t3
    
25.     End If
    
26.    
    
27.     If b(2) >= b(3) Then
    
28.         c(1) = b(2) - b(3)
    
29.         c(2) = b(1)
    
30.         calc2 c, "(" & t2 & "-" & t3 & ")", t1
    
31.     End If
    
32.     If b(3) > b(2) Then
    
33.         c(1) = b(3) - b(2)
    
34.         c(2) = b(1)
    
35.         calc2 c, "(" & t3 & "-" & t2 & ")", t1
    
36.     End If
    
37.    
    
38.     If b(3) >= b(1) Then
    
39.         c(1) = b(3) - b(1)
    
40.         c(2) = b(2)
    
41.         calc2 c, "(" & t3 & "-" & t1 & ")", t2
    
42.     End If
    
43.     If b(1) > b(3) Then
    
44.         c(1) = b(1) - b(3)
    
45.         c(2) = b(2)
    
46.         calc2 c, "(" & t1 & "-" & t3 & ")", t2
    
47.     End If
    
48.    
    
49.     c(1) = b(1) * b(2)
    
50.     c(2) = b(3)
    
51.     calc2 c, t1 & "*" & t2, t3
    
52.    
    
53.     c(1) = b(2) * b(3)
    
54.     c(2) = b(1)
    
55.     calc2 c, t2 & "*" & t3, t1
    
56.    
    
57.     c(1) = b(3) * b(1)
    
58.     c(2) = b(2)
    
59.     calc2 c, t3 & "*" & t1, t2
    
60.    
    
61.    
    
62.     If b(1) <> 0 Then
    
63.         c(1) = b(2) / b(1)
    
64.         c(2) = b(3)
    
65.         calc2 c, "(" & t2 & "/" & t1 & ")", t3
    
66.         
    
67.         c(1) = b(3) / b(1)
    
68.         c(2) = b(2)
    
69.         calc2 c, "(" & t3 & "/" & t1 & ")", t2
    
70.     End If
    
71.    
    
72.     If b(2) <> 0 Then
    
73.         c(1) = b(1) / b(2)
    
74.         c(2) = b(3)
    
75.         calc2 c, "(" & t1 & "/" & t2 & ")", t3
    
76.         
    
77.         c(1) = b(3) / b(2)
    
78.         c(2) = b(1)
    
79.         calc2 c, "(" & t3 & "/" & t2 & ")", t1
    
80.     End If
    
81.    
    
82.     If b(3) <> 0 Then
    
83.         c(1) = b(1) / b(3)
    
84.         c(2) = b(2)
    
85.         calc2 c, "(" & t1 & "/" & t3 & ")", t2
    
86.         
    
87.         c(1) = b(2) / b(3)
    
88.         c(2) = b(1)
    
89.         calc2 c, "(" & t2 & "/" & t3 & ")", t1
    
90.     End If
    
91. End Sub
    

复制代码

再次强调，【calc3】递归过程的【出口】，就是调用【calc2】过程代码。

呵呵。

所以，本例的递归计算24方法，本质上是一种【间接递归方式】。

香川群子

逆向的继续，到了最后的递归过程【calc4】，即4个元素的加、减、乘、除递归计算过程。

Sub calc4(a(), t1, t2, t3, t4)
……
End Sub

递归子过程命名为【calc4】，即四个元素的计算。
参数1为数组a()含四个计算对象元素，以及文字结果t1、t2、t3、t4。

思考计算最终结果的出口，就是递归过程【calc3】需要的入口，即三个元素的计算结果。


入口呢？那么就是四个元素a()，以及它们的文字表达式，t1,t2,t3,t4

而处理过程，也很简单，仍然是【加、减、乘、除】
但也需要包含全部4个元素的所有排列方式。


具体代码如下：
（同样是：代码很【复杂=行数很多】，但是理解很容易，很简单）

1. 
   
2. Sub calc4(a(), t1, t2, t3, t4)
   
3.     b(1) = a(1) + a(2)
   
4.     b(2) = a(3)
   
5.     b(3) = a(4)
   
6.     calc3 b, "(" & t1 & "+" & t2 & ")", t3, t4
   
7.    
   
8.     b(1) = a(1) + a(3)
   
9.     b(2) = a(2)
   
10.     b(3) = a(4)
    
11.     calc3 b, "(" & t1 & "+" & t3 & ")", t2, t4
    
12.    
    
13.     b(1) = a(1) + a(4)
    
14.     b(2) = a(2)
    
15.     b(3) = a(3)
    
16.     calc3 b, "(" & t1 & "+" & t4 & ")", t2, t3
    
17.    
    
18.     b(1) = a(2) + a(3)
    
19.     b(2) = a(1)
    
20.     b(3) = a(4)
    
21.     calc3 b, "(" & t2 & "+" & t3 & ")", t1, t4
    
22.    
    
23.     b(1) = a(2) + a(4)
    
24.     b(2) = a(1)
    
25.     b(3) = a(3)
    
26.     calc3 b, "(" & t2 & "+" & t4 & ")", t1, t3
    
27.    
    
28.     b(1) = a(3) + a(4)
    
29.     b(2) = a(1)
    
30.     b(3) = a(2)
    
31.     calc3 b, "(" & t3 & "+" & t4 & ")", t1, t2
    
32.     '以上各种加法计算
    
33.    
    
34.     If a(1) >= a(2) Then
    
35.         b(1) = a(1) - a(2)
    
36.         b(2) = a(3)
    
37.         b(3) = a(4)
    
38.         calc3 b, "(" & t1 & "-" & t2 & ")", t3, t4
    
39.     End If
    
40.     If a(2) > a(1) Then
    
41.         b(1) = a(2) - a(1)
    
42.         b(2) = a(3)
    
43.         b(3) = a(4)
    
44.         calc3 b, "(" & t2 & "-" & t1 & ")", t3, t4
    
45.     End If
    
46.    
    
47.     If a(1) >= a(3) Then
    
48.         b(1) = a(1) - a(3)
    
49.         b(2) = a(2)
    
50.         b(3) = a(4)
    
51.         calc3 b, "(" & t1 & "-" & t3 & ")", t2, t4
    
52.     End If
    
53.     If a(3) > a(1) Then
    
54.         b(1) = a(3) - a(1)
    
55.         b(2) = a(2)
    
56.         b(3) = a(4)
    
57.         calc3 b, "(" & t3 & "-" & t1 & ")", t2, t4
    
58.     End If
    
59.    
    
60.     If a(1) >= a(4) Then
    
61.         b(1) = a(1) - a(4)
    
62.         b(2) = a(2)
    
63.         b(3) = a(3)
    
64.         calc3 b, "(" & t1 & "-" & t4 & ")", t2, t3
    
65.     End If
    
66.     If a(4) > a(1) Then
    
67.         b(1) = a(4) - a(1)
    
68.         b(2) = a(2)
    
69.         b(3) = a(3)
    
70.         calc3 b, "(" & t4 & "-" & t1 & ")", t2, t3
    
71.     End If
    
72.    
    
73.     If a(2) >= a(3) Then
    
74.         b(1) = a(2) - a(3)
    
75.         b(2) = a(1)
    
76.         b(3) = a(4)
    
77.         calc3 b, "(" & t2 & "-" & t3 & ")", t1, t4
    
78.     End If
    
79.     If a(3) > a(2) Then
    
80.         b(1) = a(3) - a(2)
    
81.         b(2) = a(1)
    
82.         b(3) = a(4)
    
83.         calc3 b, "(" & t3 & "-" & t2 & ")", t1, t4
    
84.     End If
    
85.    
    
86.     If a(2) >= a(4) Then
    
87.         b(1) = a(2) - a(4)
    
88.         b(2) = a(1)
    
89.         b(3) = a(3)
    
90.         calc3 b, "(" & t2 & "-" & t4 & ")", t1, t3
    
91.     End If
    
92.     If a(4) > a(2) Then
    
93.         b(1) = a(4) - a(2)
    
94.         b(2) = a(1)
    
95.         b(3) = a(3)
    
96.         calc3 b, "(" & t4 & "-" & t2 & ")", t1, t3
    
97.     End If
    
98.    
    
99.     If a(3) >= a(4) Then
    
100.         b(1) = a(3) - a(4)
     
101.         b(2) = a(1)
     
102.         b(3) = a(2)
     
103.         calc3 b, "(" & t3 & "-" & t4 & ")", t1, t2
     
104.     End If
     
105.     If a(4) > a(3) Then
     
106.         b(1) = a(4) - a(3)
     
107.         b(2) = a(1)
     
108.         b(3) = a(2)
     
109.         calc3 b, "(" & t4 & "-" & t3 & ")", t1, t2
     
110.     End If
     
111.     '以上各种减法计算
     
112.    
     
113.     b(1) = a(1) * a(2)
     
114.     b(2) = a(3)
     
115.     b(3) = a(4)
     
116.     calc3 b, "(" & t1 & "*" & t2 & ")", t3, t4
     
117.    
     
118.     b(1) = a(1) * a(3)
     
119.     b(2) = a(2)
     
120.     b(3) = a(4)
     
121.     calc3 b, "(" & t1 & "*" & t3 & ")", t2, t4
     
122.    
     
123.     b(1) = a(1) * a(4)
     
124.     b(2) = a(2)
     
125.     b(3) = a(3)
     
126.     calc3 b, "(" & t1 & "*" & t4 & ")", t2, t3
     
127.    
     
128.     b(1) = a(2) * a(3)
     
129.     b(2) = a(1)
     
130.     b(3) = a(4)
     
131.     calc3 b, "(" & t2 & "*" & t3 & ")", t1, t4
     
132.    
     
133.     b(1) = a(2) * a(4)
     
134.     b(2) = a(1)
     
135.     b(3) = a(3)
     
136.     calc3 b, "(" & t2 & "*" & t4 & ")", t1, t3
     
137.    
     
138.     b(1) = a(3) * a(4)
     
139.     b(2) = a(1)
     
140.     b(3) = a(2)
     
141.     calc3 b, "(" & t3 & "*" & t4 & ")", t1, t2
     
142.     '以上各种乘法计算
     
143.    
     
144.     b(1) = a(1) / a(2)
     
145.     b(2) = a(3)
     
146.     b(3) = a(4)
     
147.     calc3 b, "(" & t1 & "/" & t2 & ")", t3, t4
     
148.    
     
149.     b(1) = a(2) / a(1)
     
150.     b(2) = a(3)
     
151.     b(3) = a(4)
     
152.     calc3 b, "(" & t2 & "/" & t1 & ")", t3, t4
     
153.    
     
154.     b(1) = a(1) / a(3)
     
155.     b(2) = a(2)
     
156.     b(3) = a(4)
     
157.     calc3 b, "(" & t1 & "/" & t3 & ")", t2, t4
     
158.    
     
159.     b(1) = a(3) / a(1)
     
160.     b(2) = a(2)
     
161.     b(3) = a(4)
     
162.     calc3 b, "(" & t3 & "/" & t1 & ")", t2, t4
     
163.    
     
164.     b(1) = a(1) / a(4)
     
165.     b(2) = a(2)
     
166.     b(3) = a(3)
     
167.     calc3 b, "(" & t1 & "/" & t4 & ")", t2, t3
     
168.    
     
169.     b(1) = a(4) / a(1)
     
170.     b(2) = a(2)
     
171.     b(3) = a(3)
     
172.     calc3 b, "(" & t4 & "/" & t1 & ")", t2, t3
     
173.    
     
174.     b(1) = a(2) / a(3)
     
175.     b(2) = a(1)
     
176.     b(3) = a(4)
     
177.     calc3 b, "(" & t2 & "/" & t3 & ")", t1, t4
     
178.    
     
179.     b(1) = a(3) / a(2)
     
180.     b(2) = a(1)
     
181.     b(3) = a(4)
     
182.     calc3 b, "(" & t3 & "/" & t2 & ")", t1, t4
     
183.    
     
184.     b(1) = a(2) / a(4)
     
185.     b(2) = a(1)
     
186.     b(3) = a(3)
     
187.     calc3 b, "(" & t2 & "/" & t4 & ")", t1, t3
     
188.    
     
189.     b(1) = a(4) / a(2)
     
190.     b(2) = a(1)
     
191.     b(3) = a(3)
     
192.     calc3 b, "(" & t4 & "/" & t2 & ")", t1, t3
     
193.    
     
194.     b(1) = a(3) / a(4)
     
195.     b(2) = a(1)
     
196.     b(3) = a(2)
     
197.     calc3 b, "(" & t3 & "/" & t4 & ")", t1, t2
     
198.    
     
199.     b(1) = a(4) / a(3)
     
200.     b(2) = a(1)
     
201.     b(3) = a(2)
     
202.     calc3 b, "(" & t4 & "/" & t3 & ")", t1, t2
     
203.     '以上各种除法计算
     
204.    
     
205. End Sub
     

复制代码

呵呵，代码真的很【复杂】，但同时其含义和作用，又是简单到不能再简单。




最后强调，【calc4】递归过程的【出口】，就是调用【calc3】过程代码。
而接下来，【calc3】过程，将会调用【calc2】过程，直至得到最终结果。
呵呵。

所以，本例的递归计算24方法，是一种【多过程间接递归方式】。

过程总代码 →【calc4】递归→→【calc3】递归→【calc2】递归


每个【calc】递归计算过程，都会把复杂度降低一级，直至最终结果。

香川群子

最后，就是全过程的输入输出及打包、调试运行了。
最终代码如下：

1. 
   
2. Public a(4), b(3), c(2), d() As String, e() As String, k$, t#
   
3. '以上为声明公共变量
   
4. Sub my24()
   
5.     For i = 1 To 4
   
6.         a(i) = Cells(i, 1) '从工作表的a1、a2、a3、a4单元格中获取四个元素
   
7.     Next
   
8.     t = [b1] '获取目标值。 当前工作表为=24，但实际上你可以修改为任意数值如=20来运行
   
9.    
   
10.     ReDim d(1 To 65536) '定义获取计算结果的数组d
    
11.     ReDim e(1 To 65536) '定义获取计算结果文字表达式结果的数组e
    
12.    
    
13.     k = 0 '结果计数器归零
    
14.     calc4 a, a(1), a(2), a(3), a(4) '调用【calc4】递归过程后，自动递归计算并得到所有结果
    
15.    
    
16.     [d1].CurrentRegion.Clear '清除输出结果区域
    
17.     If k > 0 Then
    
18.         [d1] = Join(a) & " Has " & k & " Answers !" '显示有解k个
    
19.         [d2].Resize(k) = WorksheetFunction.Transpose(d) '输出计算结果
    
20.         [e2].Resize(k) = WorksheetFunction.Transpose(e) '输出文字列表达式
    
21.     Else
    
22.         [d1] = Join(a) & " No Answer !" '显示无解
    
23.     End If
    
24. End Sub
    

复制代码

总之，是很简单的递归思路，
但是由于把加、减、乘、除，以及排列等因素一并考虑进去了，
所以代码的行数相当地多，多到让人看了感到很复杂的程度。
但是实际上都是相似结构代码的排列重复而已。

香川群子

有人把排列等因素也用代码算法简化了，大大地减少了代码行数，
但是，实际上就代码本身而言，代码行数少了，但代码真正的复杂程度是大大提高了。


并且，有些人写的算24代码，是一次性递归过程，（但在这个递归过程中用了很多条件判断和反复调用过程）



…………

总之，我今天这样写出一个【多过程递归计算24】的代码，

不是为了什么明确的目的，仅仅是为了便于广大初学者，

可以毫无压力地看懂，并今后能够敢于自己编写递归代码。


呵呵。

如果初学者因此而增加了一些信心，那就是我的荣幸。


…………
也请高手发表意见，也算是抛砖引玉了。


呵呵。

hc2266116

太复杂一时没能弄懂,留个记号以后慢慢啃!

yjh_27

1~13  就是扑克24点游戏

wlianke

出手不凡，支持香川群子！！！