解限制条件下线性不定方程的解组数 - VB6论坛

第 31 楼

得分:0

回复 30楼 jklqwe111

似乎第一组不符合题意。mod3是否为限制条件。那个N=8时，六个自变量，自变量不能取3的倍数，不定方程有多少组解？
第二组，粗略看符合题意，四个自变量，自变量不能取3的倍数，当N=14时，是那90组解吗？

素数问题的解决是我学习编程永恒的动力。

第 32 楼

得分:0

N=8时，六个自变量，自变量不能取3的倍数，不定方程有 21 组解
90 是下面一组解的个数
第一组还会有别的解吗

第 33 楼

得分:0

回复 32楼 jklqwe111

要么我理解错了，要么你理解错了。重复的没有，是说未知数等于3的倍数不符合题意（我要求的结果），六个未知数，最大值只能取3，但是不符合条件，所以全部舍去，那么只剩下未知数取2的情况，两个是2，四个是1，它们的全排列数为：C（6,2）=C(6,4)=15组解。
或许你是展示不限制的情况下。此时，无需用程序求解，用隔板法即可解决，把8个1排成一排，1与1之间有7个空位，我们拿5块板放在空位上，则有C（7,5）=21.

素数问题的解决是我学习编程永恒的动力。

第 34 楼

得分:0

上次第一组给出的是没有限制条件的数据，去除3的倍数是15组合数为9时是26 为10时是51 下面是解的列表

x+y+z+a+b+c=8  - mod 3

15

1     1     1     1     2     2
2     1     1     1     1     2
2     1     1     1     2     1
1     2     1     1     1     2
1     2     1     1     2     1
2     2     1     1     1     1
1     1     2     1     1     2
1     1     2     1     2     1
2     1     2     1     1     1
1     2     2     1     1     1
1     1     1     2     1     2
1     1     1     2     2     1
2     1     1     2     1     1
1     2     1     2     1     1
1     1     2     2     1     1

x+y+z+a+b+c=9  - mod 3

26

1     1     1     1     1     4
1     1     1     1     4     1
2     1     1     1     2     2
4     1     1     1     1     1
1     2     1     1     2     2
2     2     1     1     1     2
2     2     1     1     2     1
1     4     1     1     1     1
1     1     2     1     2     2
2     1     2     1     1     2
2     1     2     1     2     1
1     2     2     1     1     2
1     2     2     1     2     1
2     2     2     1     1     1
1     1     4     1     1     1
1     1     1     2     2     2
2     1     1     2     1     2
2     1     1     2     2     1
1     2     1     2     1     2
1     2     1     2     2     1
2     2     1     2     1     1
1     1     2     2     1     2
1     1     2     2     2     1
2     1     2     2     1     1
1     2     2     2     1     1
1     1     1     4     1     1

x+y+z+a+b+c=10  - mod 3

51

1     1     1     1     1     5
1     1     1     1     2     4
1     1     1     1     4     2
1     1     1     1     5     1
2     1     1     1     1     4
2     1     1     1     4     1
4     1     1     1     1     2
4     1     1     1     2     1
5     1     1     1     1     1
1     2     1     1     1     4
1     2     1     1     4     1
2     2     1     1     2     2
4     2     1     1     1     1
1     4     1     1     1     2
1     4     1     1     2     1
2     4     1     1     1     1
1     5     1     1     1     1
1     1     2     1     1     4
1     1     2     1     4     1
2     1     2     1     2     2
4     1     2     1     1     1
1     2     2     1     2     2
2     2     2     1     1     2
2     2     2     1     2     1
1     4     2     1     1     1
1     1     4     1     1     2
1     1     4     1     2     1
2     1     4     1     1     1
1     2     4     1     1     1
1     1     5     1     1     1
1     1     1     2     1     4
1     1     1     2     4     1
2     1     1     2     2     2
4     1     1     2     1     1
1     2     1     2     2     2
2     2     1     2     1     2
2     2     1     2     2     1
1     4     1     2     1     1
1     1     2     2     2     2
2     1     2     2     1     2
2     1     2     2     2     1
1     2     2     2     1     2
1     2     2     2     2     1
2     2     2     2     1     1
1     1     4     2     1     1
1     1     1     4     1     2
1     1     1     4     2     1
2     1     1     4     1     1
1     2     1     4     1     1
1     1     2     4     1     1
1     1     1     5     1     1

第 35 楼

得分:0

对遍历算法优化了下，速度提升了不少。还是没理解题主用那种表表达的意思，相信题主的算法更优秀（没有vb，只能在excel中实现，vb中相同算法估计速度有提升）。
想到另外一种算法，就是逐步丢掉最大元素法，通过排列组合公式计算存在最大元素的组数，就不需要遍历了，速度肯定有大幅度提升。

程序代码：

Sub inc(a() As Integer, l As Integer, m As Integer)
  '6位任意进制计数器，调用一次递增一下
  Dim i As Integer
  i = l
  a(i) = a(i) + 1
  While i > 0 And a(i) > m
    a(i) = 0
    i = i - 1
    a(i) = a(i) + 1
  Wend
End Sub

Sub 按钮1_Click()
  Dim i As Integer, j As Integer, k As Integer, l As Integer, ll As Integer, n As Integer, m As Integer, inc_n(6) As Integer, add_n(100) As Integer, sum As Long
  Dim tt As Double
  tt = Timer
  n = Val(Sheet2.Range("A2"))
  m = Val(Sheet2.Range("B2"))
  For i = 0 To 6
    inc_n(i) = 0
  Next
  j = n - 5
  k = 0
  If m = 0 Then m = n + 1       '如果模值为0表示所有元素参与运算
  For i = 1 To j
    If (i Mod m) > 0 Then       '获取参与运算的所有元素（1至n-5,排除能整除m的元素）
      add_n(k) = i
      k = k + 1
    End If
  Next
  sum = 0
  While inc_n(0) = 0
    l = 0
    For i = 1 To 6
      l = l + add_n(inc_n(i))   '根据计数器每位值对应的元素相加，获取实际x+y+z+...和值
    Next
    ll = 0
    If l = n Then sum = sum + 1
    If k > 0 Then ll = ll * 6
    inc inc_n, 6, k - 1
  Wend
  Sheet2.Range("C2") = sum
  Sheet2.Range("D2") = Timer - tt
End Sub

Sub 按钮3_Click()
  Dim i As Integer, j As Integer, k As Integer, l As Integer, ll As Integer, n As Integer, m As Integer, inc_n(6) As Integer, add_n(100) As Integer, sum As Long
  Dim tt As Double
  '优化后的遍历算法
  tt = Timer
  n = Val(Sheet2.Range("A8"))
  m = Val(Sheet2.Range("B8"))
  For i = 0 To 6
    inc_n(i) = 0
  Next
  j = n - 5
  If m = 0 Then m = n + 1
  For i = 0 To j
    add_n(i) = 0
    If (i Mod m) > 0 Then add_n(i) = 1
  Next
  sum = 0
  While inc_n(0) = 0
    l = 0
    For i = 1 To 5
      l = l + inc_n(i) + 1
      If add_n(inc_n(i) + 1) = 0 Or l > n Then
        l = n
        Exit For
      End If
    Next
    sum = sum + add_n(n - l)
    inc inc_n, 5, j
  Wend
  Sheet2.Range("C8") = sum
  Sheet2.Range("D8") = Timer - tt
End Sub

图片附件: 游客没有浏览图片的权限，请登录或注册

能编个毛线衣吗？

第 36 楼

得分:0

回复 35楼 wmf2014

专业性很强！佩服。如果知道了解题原理，估计速度猛进。我所设计的模型，不是遍历，而是模块（区域）替换，相当于二分法。

素数问题的解决是我学习编程永恒的动力。

第 37 楼

得分:0

算法再次优化，速度提升了一个量级。接下来在要解决的非遍历算法里，我感觉N<=500的6个未知数函数解总数可以在1秒内得到。

图片附件: 游客没有浏览图片的权限，请登录或注册

程序代码：

Sub 按钮4_Click()
  Dim i As Integer, j As Integer, k As Integer, l As Integer, ll As Integer, n As Integer, m As Integer, inc_n(6) As Integer, add_n(500) As Integer, sum As Long
  Dim tt As Double
  '再次优化后的遍历算法，速度提升了一个量级
  tt = Timer
  n = Val(Sheet2.Range("A13"))
  m = Val(Sheet2.Range("B13"))
  For i = 0 To 6
    inc_n(i) = 0
  Next
  j = n - 5
  If m = 0 Then m = n + 1
  For i = 0 To j
    add_n(i) = 0
    If (i Mod m) > 0 Then add_n(i) = 1
  Next
  sum = 0
  While inc_n(0) = 0
    l = 0
    For i = 1 To 5
      If add_n(inc_n(i) + 1) = 0 Then   '碰到无效元素的处理
        l = n + 1
        i = i + 1
      End If
      If l < n Then
        l = l + inc_n(i) + 1
      Else
        inc_n(i) = j        '无效元素（能被整除的）或前5个未知数和大于N的处理
      End If
    Next
    If l < n Then sum = sum + add_n(n - l)
    inc inc_n, 5, j
  Wend
  Sheet2.Range("C13") = sum
  Sheet2.Range("D13") = Timer - tt
End Sub

能编个毛线衣吗？

第 38 楼

得分:0

回复 37楼 wmf2014

做几层嵌套，把符合条件的计数，不符合的不计数（或许没有这个必要考虑），在每层嵌套中设置一个选择语句，非整除3时，正常运行，整除时，此变量增加1执行（在正常的基础上执行）；又或者设置分道执行，首先执行第一选择，选取标准，加1后，不整除；后选择第二步，加2执行（非此即彼，它们互不相容）。

素数问题的解决是我学习编程永恒的动力。

第 39 楼

得分:0

如果只需要解的数目，递归就可以，如计算n个未知数的和等于sum,模mo为0的解的数目：

程序代码：

Function Sol(ByVal sum&, ByVal n&, Optional ByVal mo&) As Long
    Dim s&, i&
    If sum < 1 Or n < 1 Or sum < n Then Exit Function
    If mo < 2 Then mo = sum + 1
    If sum = n Or (n = 1 And (sum Mod mo)) Then Sol = 1: Exit Function
    For i = 1 To sum - n + 1
        If i Mod mo Then Sol = Sol + Sol(sum - i, n - 1, mo)
    Next
End Function

Sub Calc()
    Dim t!
    t = Timer
    MsgBox Sol(60, 6, 3), , Timer - t & " seconds"
End Sub

返回 580678，用时0.1秒
即6个未知数的和等于60,模3为0的解的数目为580678

第 40 楼

得分:0

以下是引用独木星空在2022-11-1 13:03:24的发言：

可以用递归算法。如果在加条件，程序还能用吗？比如，未知数除了不能取5的倍数外，还不能取模5余2的数，两个条件了，又如何呢？

这个加一个paramarray参数即可，如：

程序代码：

Function Sol(sum&, n&, ParamArray mo()) As Long
    Dim s&, i&, j&, b()
    If sum < 1 Or n < 1 Or sum < n Then Exit Function
    If sum = n Then Sol = 1: Exit Function
    ReDim b(sum)
    For j = 1 To sum
        b(j) = 1
        For i = 0 To UBound(mo) - 1 Step 2
            If j Mod mo(i) = mo(i + 1) Then b(j) = 0: Exit For
        Next
    Next
    If n = 1 Then
        If b(sum) = 1 Then Sol = 1: Exit Function
    End If

    For j = 1 To sum - n + 1
        If b(j) = 1 Then Sol = Sol + Sol(sum - j, n - 1, mo)
    Next
End Function

Sub Calc()
    Dim t!
    t = Timer
    MsgBox Sol(60, 6, 3, 0, 5, 0, 5, 2, 7, 1, 7, 5, 11, 3), , Timer - t & " seconds"
End Sub

6个未知数的和等于60，若每个解模3<>0,模5<>0,模5<>2,模7<>1,模7<>5,模11<>3，则有957075组解，运行1秒左右