使用VBA解决具有九个未知变量的方程的强力方法

Question

这个等式:a+(13*b/c)+d+(12*e)-f+(g*h/i)=87当试图解决最近在互联网上传播的越南八岁儿童的数学难题时出现.在数学中,这样的方程称为欠定系统.当然它有多个解决方案,蛮力方法似乎是找到所有解决方案的最简单方法.

我有兴趣知道如何使用VBA解决方程并在MS Excel工作表中提供解决方案,因为由于缺乏VBA编程知识,我无法找到制作此类程序的方法.

我知道在堆栈溢出类似的职位像这样和这个,但答案有不帮我很多.

这是我的尝试:

Sub Vietnam_Problem()
Dim StartTime As Double

StartTime = Timer
j = 2   'initial value for number of rows
For a = 1 To 9
    For b = 1 To 9
        For c = 1 To 9
            For d = 1 To 9
                For e = 1 To 9
                    For f = 1 To 9
                        For g = 1 To 9
                            For h = 1 To 9
                                For i = 1 To 9
                                If a <> b And a <> c And a <> d And a <> e And a <> f And a <> g And a <> h And a <> i And b <> c And b <> d And b <> e And b <> f And b <> g And b <> h And b <> i And c <> d And c <> e And c <> f And c <> g And c <> h And c <> i And d <> e And d <> f And d <> g And d <> h And d <> i And e <> f And e <> g And e <> h And e <> i And f <> g And f <> h And f <> i And g <> h And g <> i And h <> i And a + (13 * b / c) + d + (12 * e) - f + (g * h / i) = 87 Then
                                Cells(j, 1) = a
                                Cells(j, 2) = b
                                Cells(j, 3) = c
                                Cells(j, 4) = d
                                Cells(j, 5) = e
                                Cells(j, 6) = f
                                Cells(j, 7) = g
                                Cells(j, 8) = h
                                Cells(j, 9) = i
                                j = j + 1
                                End If
                                Next i
                            Next h
                        Next g
                    Next f
                Next e
            Next d
        Next c
    Next b
Next a
Cells(2, 11) = j - 2 'number of solutions
Cells(2, 12) = Round(Timer - StartTime, 2)  'running time of VBA code
End Sub

它似乎工作,但它不好,非常慢.

Answer 1

Anastasiya-Romanova秀,因为你没有声明变量(a到j),你的代码运行时那些变量默认为Variant类型.虽然变体非常有用,但不应在此处使用.

我没有改变你的代码,在我的机器上,完成了851秒.

由于VBA针对Longs进行了优化,只需在代码中添加一行以将变量(a到j)声明为Longs,就可以将我的机器上的运行时间降低到120秒.因此,使用适当的变量类型快七倍!

我在VBA中解决这个难题的尝试运行速度要快得多.事实上,它比目前在此页面上发布的内容要快得多(也更短).在我的同一台机器上,它在不到一秒的时间内返回所有136个正确的组合.

有很多废话(世界,网络,甚至在这个页面!)关于VBA太慢了.不要相信.当然,编译的语言可以更快,但在很多时候,它取决于你如何知道如何处理你的语言.自20世纪70年代以来,我一直在用BASIC语言编程.

这是我为你的问题精心设计的越南拼图的解决方案.请将其放在新的代码模块中:

Option Explicit
Private z As Long, v As Variant

Public Sub Vietnam()
    Dim s As String
    s = "123456789"
    ReDim v(1 To 200, 1 To 9)
    Call FilterPermutations("", s)
    [a1:i200] = v
    End
End Sub

Private Sub FilterPermutations(s1 As String, s2 As String)

    Dim a As Long, b As Long, c As Long, d As Long, e As Long, f As Long, _
        g As Long, h As Long, i As Long, j As Long, m As Long, n As Long

    n = Len(s2)
    If n < 2 Then
        a = Mid$(s1, 1, 1):  b = Mid$(s1, 2, 1):  c = Mid$(s1, 3, 1)
        d = Mid$(s1, 4, 1):  e = Mid$(s1, 5, 1):  f = Mid$(s1, 6, 1)
        g = Mid$(s1, 7, 1):  h = Mid$(s1, 8, 1):  i = s2
        If a + (13 * b / c) + d + (12 * e) - f + (g * h / i) = 87 Then
            z = z + 1
            v(z, 1) = a:  v(z, 2) = b:  v(z, 3) = c
            v(z, 4) = d:  v(z, 5) = e:  v(z, 6) = f
            v(z, 7) = g:  v(z, 8) = h:  v(z, 9) = i
        End If
    Else
        For m = 1 To n
            FilterPermutations s1 + Mid$(s2, m, 1), Left$(s2, m - 1) + Right$(s2, n - m)
        Next
    End If

End Sub

方法#2:

Anastasiya,我会在今天晚些时候尝试解释,当我有更多时间.但与此同时,请检查我的下一次尝试.它现在更短,并在大约1/10秒内完成.我现在使用Heap的置换算法:

Option Explicit
Private z As Long, v As Variant

Public Sub VietnamHeap()
    Dim a(0 To 8) As Long
    a(0) = 1:  a(1) = 2:  a(2) = 3:  a(3) = 4:  a(4) = 5:  a(5) = 6:  a(6) = 7:  a(7) = 8:  a(8) = 9
    ReDim v(1 To 200, 1 To 9)
    Generate 9, a
    [a1:i200] = v
    End
End Sub

Sub Generate(n As Long, a() As Long)
    Dim t As Long, i As Long
    If n = 1 Then
        If a(0) + (13 * a(1) / a(2)) + a(3) + (12 * a(4)) - a(5) + (a(6) * a(7) / a(8)) = 87 Then
            z = z + 1
            For i = 1 To 9:  v(z, i) = a(i - 1):  Next
        End If
    Else
        For i = 0 To n - 2
            Generate n - 1, a
            If n Mod 2 = 1 Then
                t = a(0):  a(0) = a(n - 1):  a(n - 1) = t
            Else
                t = a(i):  a(i) = a(n - 1):  a(n - 1) = t
            End If
        Next
        Generate n - 1, a
    End If
End Sub

方法#3

这是一个更短的版本.任何人都可以提出更短的版本或更快的版本？

Const q = 9
Dim z As Long, v(1 To 999, 1 To q)

Public Sub VietnamHeap()
    Dim a(1 To q) As Long
    For z = 1 To q: a(z) = z: Next: z = 0
    Gen q, a
    [a1].Resize(UBound(v), q) = v: End
End Sub

Sub Gen(n As Long, a() As Long)
    Dim i As Long, k As Long, t As Long
    If n > 1 Then
        For i = 1 To n - 1
            Gen n - 1, a
            If n Mod 2 = 1 Then k = 1 Else k = i
            t = a(k): a(k) = a(n): a(n) = t
        Next
        Gen n - 1, a
    Else
        If 87 = a(1) + 13 * a(2) / a(3) + a(4) + 12 * a(5) - a(6) + a(7) * a(8) / a(9) Then z = z + 1: For i = 1 To q: v(z, i) = a(i): Next
    End If
End Sub