用VBA解欧拉计划题目（93）--算术表达式

grf1973

算术表达式

使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号，可以得到不同的正整数。

例如，

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

注意不允许直接把数字连起来，如12 + 34。

使用集合{1, 2, 3, 4}，可以得到31个不同的数，其中最大值是36，以及1到28之间所有的数。

若使用包含有四个不同数字a < b < c < d的集合可以得到从1到n之间所有的数，求其中使得n最大的集合，并将你的答案写成字符串：abcd。

香川群子

1可能不是必须的吧。

grf1973

这个有点象编写算24的算法。不是很难，但比较烦。需要遍历abcd组合及中间穿插+-*/()的组合。
好在Vba有Evaluate函数可以直接计算字符串。
结果是1258。可以输出1--51之间的数字。

香川群子

你这结果不正确。我已经说了，1不是必须的。
a      b      c       d    首个空缺值
1        2        3        4        29
1        2        4        5        33
1        2        4        7        38
1        2        5        6        44
1        2        5        8        52
2        3        4        22        53

因此，最后一组 2，3，4，22 能得到覆盖1-52才是最大。

香川群子

1 | =3*4-22/2
2 | =22-(2+3)*4
2 | =2*3*4-22
2 | =22/(2*4+3)
2 | =(22/2-3)/4
2 | =(22-2)/4-3
2 | =(2+22)/3/4
3 | =(22-4)/2/3
3 | =(2+22)/4-3
4 | =22/(3/2+4)
4 | =22/4-3/2
4 | =(22-2*3)/4
4 | =22-(2+4)*3
4 | =22/2-3-4
4 | =(2+22)/3-4
4 | =(22-4)/3-2
5 | =(4+22/2)/3
5 | =(22-3*4)/2
5 | =(22/4-3)*2
6 | =(22-4)/2-3
7 | =3/2+22/4
7 | =(2*3+22)/4
8 | =2*22/4-3
8 | =(4/2+22)/3
8 | =22/(4-2)-3
8 | =(4+22-2)/3
8 | =22-2-3*4
8 | =(22-2)/4+3
8 | =3-(2-22)/4
8 | =22-(3+4)*2
8 | =22/(2+3/4)
8 | =(22-4)/3+2
8 | =2-(4-22)/3
9 | =(2+22)/4+3
10 | =(2*4+22)/3
10 | =3+22/2-4
10 | =(4+22)/2-3
11 | =22/(2*3-4)
11 | =3*22/(2+4)
11 | =22-2*4-3
11 | =(4-3)*22/2
11 | =22/(4-3)/2
12 | =(22-4)*2/3
12 | =22-2*3-4
12 | =4+22/2-3
12 | =(2+22)/3+4
12 | =2+22-3*4
12 | =(22-4)/2+3
12 | =3-(4-22)/2
13 | =22-2-3-4
14 | =2*22/4+3
14 | =3+22/(4-2)
14 | =3-22/(2-4)
15 | =(22-2)*3/4
16 | =22-3*4/2
16 | =22-(4-2)*3
16 | =(2-4)*3+22
16 | =(2*22+4)/3
16 | =(3*22-2)/4
16 | =(4+22)/2+3
17 | =2+22-3-4
17 | =22-3-4/2
17 | =3+22-2*4
17 | =(3*4+22)/2
17 | =(2+3*22)/4
17 | =(3+22/4)*2
18 | =22-4/(3-2)
18 | =22-(3-2)*4
18 | =(22-4)/(3-2)
18 | =(3-2)*(22-4)
18 | =22/(3-2)-4
18 | =(3-2)*22-4
18 | =4/(2-3)+22
18 | =(2-3)*4+22
18 | =(4-22)/(2-3)
18 | =(2-3)*(4-22)
18 | =3+4+22/2
18 | =(2+22)*3/4
19 | =3+22-2-4
20 | =4+22-2*3
20 | =22-(2+4)/3
20 | =(4-3)*(22-2)
20 | =(22-2)/(4-3)
20 | =(2-22)*(3-4)
20 | =(2-22)/(3-4)
20 | =22-2/(4-3)
20 | =22-(4-3)*2
20 | =22/(4-3)-2
20 | =(4-3)*22-2
20 | =2/(3-4)+22
20 | =(3-4)*2+22
20 | =(22-3*4)*2
21 | =4+22-2-3
21 | =4/2+22-3
21 | =(22/2-4)*3
22 | =22/(2+3-4)
22 | =(2+3-4)*22
22 | =22/(3-4/2)
22 | =(3-4/2)*22
23 | =2+3+22-4
23 | =3+22-4/2
23 | =3*4+22/2
24 | =2*3+22-4
24 | =(2+4)/3+22
24 | =(2+22)*(4-3)
24 | =(2+22)/(4-3)
24 | =2/(4-3)+22
24 | =(4-3)*2+22
24 | =2+22/(4-3)
24 | =(4-3)*22+2
24 | =22-2/(3-4)
24 | =22-(3-4)*2
24 | =2-22/(3-4)
24 | =2-(3-4)*22
25 | =2+4+22-3
26 | =4/(3-2)+22
26 | =(3-2)*4+22
26 | =(4+22)/(3-2)
26 | =(3-2)*(4+22)
26 | =4+22/(3-2)
26 | =(3-2)*22+4
26 | =22-4/(2-3)
26 | =22-(2-3)*4
26 | =4-22/(2-3)
26 | =4-(2-3)*22
27 | =(22-4)*3/2
27 | =3+4+22-2
27 | =3+4/2+22
27 | =2*4+22-3
28 | =3*4/2+22
28 | =(4-2)*3+22
28 | =22-(2-4)*3
29 | =3*22/2-4
30 | =(22-3-4)*2
30 | =(2+4*22)/3
31 | =2+3+4+22
31 | =(3*22-4)/2
32 | =2*3+4+22
32 | =(22/2-3)*4
32 | =3*4+22-2
32 | =(2+22)*4/3
32 | =2*22-3*4
33 | =2*3*22/4
33 | =3*22/(4-2)
33 | =2*4+3+22
33 | =(22-4)*2-3
34 | =(22-3)*2-4
35 | =(3*22+4)/2
36 | =2+3*4+22
36 | =(3+4)*2+22
37 | =3*22/2+4
37 | =2*22-3-4
38 | =(22-3)*4/2
38 | =(4-2)*(22-3)
38 | =(2-4)*(3-22)
39 | =(4+22)*3/2
39 | =(22-4)*2+3
39 | =3-(4-22)*2
40 | =(2+4)*3+22
41 | =4*22/2-3
41 | =(4-2)*22-3
42 | =(2+3)*4+22
42 | =(22-2*4)*3
42 | =(3+22-4)*2
42 | =(22-3)*2+4
42 | =4-(3-22)*2
43 | =2*22+3-4
44 | =(2*3-4)*22
44 | =(2+4)*22/3
44 | =(4-3)*2*22
44 | =2*22/(4-3)
45 | =(4+22/2)*3
45 | =2*22+4-3
46 | =2*3*4+22
46 | =(4+22-3)*2
46 | =(3+22)*2-4
47 | =3+4*22/2
47 | =(4-2)*22+3
47 | =3-(2-4)*22
48 | =(22-2-4)*3
49 | =(4+22)*2-3
50 | =(3+22)*4/2
50 | =(3+22)*(4-2)
51 | =2*22+3+4
52 | =(22-4)*3-2
53 空缺
54 | =(3+22)*2+4
55 | =(4-3/2)*22
55 | =(3-2/4)*22
55 | =(4+22)*2+3
56 | =(3+22/2)*4
56 | =(22-2)*3-4
56 | =2*22+3*4
56 | =(22-4)*3+2
56 | =2-(4-22)*3
57 空缺
58 | =3*22-2*4
58 | =(3+4+22)*2
59 空缺
60 | =(22-4/2)*3
60 | =(2+22-4)*3
60 | =3*22-2-4

grf1973

是翻译不够精确？
Arithmetic expressions

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, &#8722;, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) &#8722; 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

题目意思，a,b,c,d应该是4个不同的一位数。

香川群子

4个正整数，进行加减乘除四则混合运算，最多只有1260种不同的计算式。

计算他们的结果，用CountIf()函数统计结果中含1-100的个数，再用Match()函数找出第一个结果为0的整数值位置n，即可知道覆盖1 - n-1的能力。

香川群子

a<b<c<d 都是1个数字，那就大大缩小计算范围了。

1        2        3        4        29
1        2        3        8        36
1        2        4        7        38
1        2        4        9        41
1        2        5        6        44
1        2        5        8        52

香川群子

今天花半个小时，专门写了检查四则运算结果的递归计算过程。

1. '欧拉计划题目（93）--算术表达式：
   
2. '使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, -, *, /)四则运算和括号，可以得到不同的正整数。例如：
   
3. '8 = (4 * (1 + 3)) / 2
   
4. '14 = 4 * (3 + 1 / 2)
   
5. '注意不允许直接把数字连起来，如12 + 34。
   
6. '使用集合{1, 2, 3, 4}，可以得到31个不同的数，其中最大值是36，以及1到28之间所有的数。
   
7. '若使用包含有四个不同数字a < b < c < d的集合可以得到从1到 n之间所有的数，求其中使得n最大的集合，并将答案写成字符串：abcd
   
8. 
   
9. Sub test() 'by kagawa 2017-12-22
   
10.     ReDim ar(1 To 4)
    
11.     For a = 1 To 6
    
12.       For b = a + 1 To 7
    
13.         For c = b + 1 To 8
    
14.           For d = c + 1 To 9
    
15.             ar(1) = a: ar(2) = b: ar(3) = c: ar(4) = d '产生1234-6789全部4个数字的组合
    
16.             For n = 1 To 99 '检查1-n的连续覆盖
    
17.                 If Not dg(ar, n) Then Exit For '不能覆盖时退出
    
18.             Next
    
19.             If n > r Then r = n: s = a & b & c & d: Debug.Print n - 1; s '更新最大值记录
    
20.     Next d, c, b, a
    
21.     MsgBox s & vbCr & "1 - " & r - 1 '输出结果
    
22. End Sub
    
23. Function dg(ar, n) '对数组中数值 反复进行两两组合的四则运算的递归过程
    
24.     k = UBound(ar)
    
25.     For i1 = 1 To k - 1
    
26.         t1 = ar(i1)
    
27.         For i2 = i1 + 1 To k
    
28.             t2 = ar(i2)
    
29.             For j = 1 To 6 'a+b;a-b;b-a;a*b;a/b;b/a 共6种运算
    
30.                 r = js(t1, t2, j) '本次两两组合的计算结果
    
31.                 If r <> "!Div" Then '如非除0无效结果则继续
    
32.                     If k = 2 Then '最后2个数的运算结果
    
33.                         If r = n Then dg = True: Exit Function '如=n则判断True 结束递归
    
34.                     Else
    
35.                         ReDim ar2(1 To k - 1): ar2(1) = r: k2 = 1 '剩余数写入新数组ar2
    
36.                         For j2 = 1 To k
    
37.                             If j2 <> i1 And j2 <> i2 Then k2 = k2 + 1: ar2(k2) = ar(j2)
    
38.                         Next
    
39.                         If dg(ar2, n) Then dg = True: Exit Function '如判断=n则结束递归 否则继续
    
40.                     End If
    
41.                 End If
    
42.             Next
    
43.         Next
    
44.     Next
    
45. End Function
    
46. Function js(t1, t2, l) '加减乘除四则运算 a+b;a-b;b-a;a*b;a/b;b/a 共6种运算
    
47.     If l = 1 Then
    
48.         js = t1 + t2
    
49.     ElseIf l = 2 Then
    
50.         js = t1 - t2
    
51.     ElseIf l = 3 Then
    
52.         js = t2 - t1
    
53.     ElseIf l = 4 Then
    
54.         js = t1 * t2
    
55.     ElseIf l = 5 Then
    
56.         If t2 = 0 Then js = "!Div" Else js = t1 / t2
    
57.     ElseIf l = 6 Then
    
58.         If t1 = 0 Then js = "!Div" Else js = t2 / t1
    
59.     End If
    
60. End Function

复制代码

香川群子

又改进了一下，可以输出计算式过程结果。

1. Sub test()
   
2.     br = Split(" " & InputBox("输入4个数字(空格键隔开):", "四则混合运算"))
   
3.     k = UBound(br): ReDim ar(1 To k)
   
4.     For i = 1 To k
   
5.         ar(i) = Val(br(i))
   
6.     Next
   
7.     n = Val(InputBox("输入目标数字:", "四则混合运算", 24))
   
8.     MsgBox dg(ar, br, n)
   
9. End Sub
   
10. Sub test2() 'by kagawa 2017-12-22
    
11.     tms = Timer
    
12.     ReDim ar(1 To 4), br(1 To 4)
    
13.     For a = 1 To 6
    
14.       For b = a + 1 To 7
    
15.         For c = b + 1 To 8
    
16.           For d = c + 1 To 9
    
17.             
    
18.             ar(1) = a: ar(2) = b: ar(3) = c: ar(4) = d '产生1234-6789全部4个数字的组合
    
19.             br(1) = a: br(2) = b: br(3) = c: br(4) = d '产生1234-6789全部4个数字的组合
    
20.             For n = 1 To 99 '检查1-n的连续覆盖
    
21.                 k = k + 1
    
22.                 If Len(dg(ar, br, n)) = 0 Then Exit For '不能覆盖时退出
    
23.             Next
    
24.             If n > r Then r = n: s = a & b & c & d ': Debug.Print n - 1; s '更新最大值记录
    
25.     Next d, c, b, a
    
26.     Debug.Print Format(Timer - tms, "0.000s")
    
27.     MsgBox Format(Timer - tms, "0.000s") & vbCr & s & vbCr & "1 - " & r - 1 '输出结果
    
28. End Sub
    
29. Function dg(ar, br, n) ' As Boolean '对数组中数值 反复进行两两组合的四则运算的递归过程
    
30.     k = UBound(ar)
    
31.     For i1 = 1 To k - 1
    
32.         t1 = ar(i1): s1 = br(i1)
    
33.         For i2 = i1 + 1 To k
    
34.             t2 = ar(i2): s2 = br(i2)
    
35.             For j = 1 To 6 'a+b;a-b;b-a;a*b;a/b;b/a 共6种运算
    
36.                 r = js(t1, t2, j) '本次两两组合的计算结果
    
37.                 s = jg(s1, s2, j) '本次两两组合的计算式
    
38.                 If r <> "!Div" Then '如非除0无效结果则继续
    
39.                     If k = 2 Then '最后2个数的运算结果
    
40.                         If r = n Then dg = s: Exit Function '如=n则判断True 结束递归
    
41.                     Else
    
42.                         ReDim ar2(1 To k - 1), br2(1 To k - 1)
    
43.                         ar2(1) = r: br2(1) = s
    
44.                         k2 = 1 '剩余数写入新数组ar2
    
45.                         For j2 = 1 To k
    
46.                             If j2 <> i1 And j2 <> i2 Then k2 = k2 + 1: ar2(k2) = ar(j2): br2(k2) = br(j2)
    
47.                         Next
    
48.                         t = dg(ar2, br2, n): If Len(t) Then dg = t: Exit Function
    
49.                     End If
    
50.                 End If
    
51.             Next
    
52.         Next
    
53.     Next
    
54. End Function
    
55. Function js(t1, t2, j) '加减乘除四则运算 a+b;a-b;b-a;a*b;a/b;b/a 共6种运算
    
56.     If j = 1 Then
    
57.         js = t1 + t2
    
58.     ElseIf j = 2 Then
    
59.         js = t1 - t2
    
60.     ElseIf j = 3 Then
    
61.         js = t2 - t1
    
62.     ElseIf j = 4 Then
    
63.         js = t1 * t2
    
64.     ElseIf j = 5 Then
    
65.         If t2 = 0 Then js = "!Div" Else js = t1 / t2
    
66.     ElseIf j = 6 Then
    
67.         If t1 = 0 Then js = "!Div" Else js = t2 / t1
    
68.     End If
    
69. End Function
    
70. Function jg(s1, s2, j) '加减乘除四则运算 a+b;a-b;b-a;a*b;a/b;b/a 共6种运算
    
71.     If j = 1 Then
    
72.         jg = "(" & s1 & "+" & s2 & ")"
    
73.     ElseIf j = 2 Then
    
74.         jg = "(" & s1 & "-" & s2 & ")"
    
75.     ElseIf j = 3 Then
    
76.         jg = "(" & s2 & "-" & s1 & ")"
    
77.     ElseIf j = 4 Then
    
78.         jg = "(" & s1 & "*" & s2 & ")"
    
79.     ElseIf j = 5 Then
    
80.         jg = "(" & s1 & "/" & s2 & ")"
    
81.     ElseIf j = 6 Then
    
82.         jg = "(" & s2 & "/" & s1 & ")"
    
83.     End If
    
84. End Function

复制代码