注册 登录
编程论坛 → VB6论坛

解限制条件下线性不定方程的解组数

独木星空 发布于 2022-10-30 07:24， 4306 次点击
实际上就是解决这么一类问题：x+y+z+u+v+m=N，未知数取值不是5的倍数，求线性不定方程满足条件的正整数解组数。用vfp程序解决。
       也可以是非6的倍数，非7的倍数，.....，当然，非4的，非3的倍数都行，只要你愿意，除了非1的倍数外，你可以所以，指定一个不能取的倍数，做vb6编程解决这类问题。
54 回复
#2
独木星空2022-10-30 07:26
在vfp中我提供一种模式解决此问题的算法，主要是二元运算。
#3
独木星空2022-10-30 19:40
看来，没有一个流程图，很难把一个具体问题转化成vb6的编程语言。
#4
独木星空2022-10-31 08:54
在vfp版块，有网友发了自己的见解，有的发了自己的困惑。所以，说，一种好的算法是建立在，自己对问题熟知程度之上的。
#5
独木星空2022-10-31 20:11
好与赖，没有人介入。
#6
wmf20142022-10-31 20:56
主要是字都认得，连起来读却不明就里。比如x+y+z+u+v+m=N里谁是“不是5的倍数，也可以是非6的倍数，非7的倍数，.....的未知数”？各变量输入有什么条件限制没有？你想输入什么，得到什么输出？
#7
独木星空2022-11-01 04:01
回复 6楼 wmf2014
就是一个线性不定方程，限制条件是，未知数不能取5的倍数（其他的暂时不要考虑了），然后是，随便给个N值，输出此值N时，满足条件的正整数解组数。
#8
wmf20142022-11-01 10:40
正整数，也就是未知数>0，假如n=6则只有（1，1，1，1，1，1）这一组解？这不就是找零钱算法，只是零钱里没有5的倍数的零钱， 一个递归就可以实现。
#9
独木星空2022-11-01 13:03
回复 8楼 wmf2014
可以用递归算法。如果在加条件，程序还能用吗？比如，未知数除了不能取5的倍数外，还不能取模5余2的数，两个条件了，又如何呢？
#10
wmf20142022-11-01 14:21
100个条件都行。
把取模的数放进一个一维数组，把不同的余数放进一个二维数组（二维数组最后一个条件用-1作为结束），然后用两个嵌套循环判断，就可以设置任意多个条件了。
#11
独木星空2022-11-01 19:24
模7矩阵    1    2    3    4    5    6
1    2    3    4    5    6    7
2    3    4    5    6    7    8
3    4    5    6    7    8    9
4    5    6    7    8    9    10
5    6    7    8    9    10    11
6    7    8    9    10    11    12

7的剩余类    统计2
2    1
3    2
4    3
5    4
6    5
7    6
8    5
9    4
10    3
11    2
12    1
合计    36
第一步
#12
独木星空2022-11-01 19:25
7的剩余类    2    3    4    5    6    7    8    9    10    11    12
2    4    5    6    7    8    9    10    11    12    13    14
3    5    6    7    8    9    10    11    12    13    14    15
4    6    7    8    9    10    11    12    13    14    15    16
5    7    8    9    10    11    12    13    14    15    16    17
6    8    9    10    11    12    13    14    15    16    17    18
7    9    10    11    12    13    14    15    16    17    18    19
8    10    11    12    13    14    15    16    17    18    19    20
9    11    12    13    14    15    16    17    18    19    20    21
10    12    13    14    15    16    17    18    19    20    21    22
11    13    14    15    16    17    18    19    20    21    22    23
12    14    15    16    17    18    19    20    21    22    23    24

统计2*2    1    2    3    4    5    6    5    4    3    2    1
1    1    2    3    4    5    6    5    4    3    2    1
2    2    4    6    8    10    12    10    8    6    4    2
3    3    6    9    12    15    18    15    12    9    6    3
4    4    8    12    16    20    24    20    16    12    8    4
5    5    10    15    20    25    30    25    20    15    10    5
6    6    12    18    24    30    36    30    24    18    12    6
5    5    10    15    20    25    30    25    20    15    10    5
4    4    8    12    16    20    24    20    16    12    8    4
3    3    6    9    12    15    18    15    12    9    6    3
2    2    4    6    8    10    12    10    8    6    4    2
1    1    2    3    4    5    6    5    4    3    2    1

7的剩余类    统计4
4    1
5    4
6    10
7    20
8    35
9    56
10    80
11    104
12    125
13    140
14    146
15    140
16    125
17    104
18    80
19    56
20    35
21    20
22    10
23    4
24    1
合计    1296
第二步
#13
独木星空2022-11-01 19:28
7的剩余类    2    3    4    5    6    7    8    9    10    11    12
4    6    7    8    9    10    11    12    13    14    15    16
5    7    8    9    10    11    12    13    14    15    16    17
6    8    9    10    11    12    13    14    15    16    17    18
7    9    10    11    12    13    14    15    16    17    18    19
8    10    11    12    13    14    15    16    17    18    19    20
9    11    12    13    14    15    16    17    18    19    20    21
10    12    13    14    15    16    17    18    19    20    21    22
11    13    14    15    16    17    18    19    20    21    22    23
12    14    15    16    17    18    19    20    21    22    23    24
13    15    16    17    18    19    20    21    22    23    24    25
14    16    17    18    19    20    21    22    23    24    25    26
15    17    18    19    20    21    22    23    24    25    26    27
16    18    19    20    21    22    23    24    25    26    27    28
17    19    20    21    22    23    24    25    26    27    28    29
18    20    21    22    23    24    25    26    27    28    29    30
19    21    22    23    24    25    26    27    28    29    30    31
20    22    23    24    25    26    27    28    29    30    31    32
21    23    24    25    26    27    28    29    30    31    32    33
22    24    25    26    27    28    29    30    31    32    33    34
23    25    26    27    28    29    30    31    32    33    34    35
24    26    27    28    29    30    31    32    33    34    35    36

统计4/2    1    2    3    4    5    6    5    4    3    2    1
1    1    2    3    4    5    6    5    4    3    2    1
4    4    8    12    16    20    24    20    16    12    8    4
10    10    20    30    40    50    60    50    40    30    20    10
20    20    40    60    80    100    120    100    80    60    40    20
35    35    70    105    140    175    210    175    140    105    70    35
56    56    112    168    224    280    336    280    224    168    112    56
80    80    160    240    320    400    480    400    320    240    160    80
104    104    208    312    416    520    624    520    416    312    208    104
125    125    250    375    500    625    750    625    500    375    250    125
140    140    280    420    560    700    840    700    560    420    280    140
146    146    292    438    584    730    876    730    584    438    292    146
140    140    280    420    560    700    840    700    560    420    280    140
125    125    250    375    500    625    750    625    500    375    250    125
104    104    208    312    416    520    624    520    416    312    208    104
80    80    160    240    320    400    480    400    320    240    160    80
56    56    112    168    224    280    336    280    224    168    112    56
35    35    70    105    140    175    210    175    140    105    70    35
20    20    40    60    80    100    120    100    80    60    40    20
10    10    20    30    40    50    60    50    40    30    20    10
4    4    8    12    16    20    24    20    16    12    8    4
1    1    2    3    4    5    6    5    4    3    2    1

7的剩余类    统计6
6    1
7    6
8    21
9    56
10    126
11    252
12    456
13    756
14    1161
15    1666
16    2247
17    2856
18    3431
19    3906
20    4221
21    4332
22    4221
23    3906
24    3431
25    2856
26    2247
27    1666
28    1161
29    756
30    456
31    252
32    126
33    56
34    21
35    6
36    1
合计    46656
第三步，单位矩阵
运算步骤完成，这里是对未知数不是7的倍数的一个分析过程。
#14
独木星空2022-11-01 19:29
周期10    0    1    2    3    4    5    6    7    8    9
0    0    1    2    3    4    5    6    7    8    9
1    1    2    3    4    5    6    7    8    9    10
2    2    3    4    5    6    7    8    9    10    11
3    3    4    5    6    7    8    9    10    11    12
4    4    5    6    7    8    9    10    11    12    13
5    5    6    7    8    9    10    11    12    13    14
6    6    7    8    9    10    11    12    13    14    15
7    7    8    9    10    11    12    13    14    15    16
8    8    9    10    11    12    13    14    15    16    17
9    9    10    11    12    13    14    15    16    17    18

周期数    统计2
0    1
1    2
2    3
3    4
4    5
5    6
6    7
7    8
8    9
9    10
10    9
11    8
12    7
13    6
14    5
15    4
16    3
17    2
18    1
合计    100
周期矩阵，第一步。
#15
独木星空2022-11-01 19:34
周期数    0    1    2    3    4    5    6
0    0    1    2    3    4    5    6
1    1    2    3    4    5    6    7
2    2    3    4    5    6    7    8
3    3    4    5    6    7    8    9
4    4    5    6    7    8    9    10
5    5    6    7    8    9    10    11
6    6    7    8    9    10    11    12
7    7    8    9    10    11    12    13
8    8    9    10    11    12    13    14
9    9    10    11    12    13    14    15
10    10    11    12    13    14    15    16
11    11    12    13    14    15    16    17
12    12    13    14    15    16    17    18
13    13    14    15    16    17    18    19
14    14    15    16    17    18    19    20
15    15    16    17    18    19    20    21
16    16    17    18    19    20    21    22
17    17    18    19    20    21    22    23
18    18    19    20    21    22    23    24

统计2    1    2    3    4    5    6    7
1    1    2    3    4    5    6    7
2    2    4    6    8    10    12    14
3    3    6    9    12    15    18    21
4    4    8    12    16    20    24    28
5    5    10    15    20    25    30    35
6    6    12    18    24    30    36    42
7    7    14    21    28    35    42    49
8    8    16    24    32    40    48    56
9    9    18    27    36    45    54    63
10    10    20    30    40    50    60    70
9    9    18    27    36    45    54    63
8    8    16    24    32    40    48    56
7    7    14    21    28    35    42    49
6    6    12    18    24    30    36    42
5    5    10    15    20    25    30    35
4    4    8    12    16    20    24    28
3    3    6    9    12    15    18    21
2    2    4    6    8    10    12    14
1    1    2    3    4    5    6    7

周期数    统计4
0    1
1    4
2    10
3    20
4    35
5    56
6    84
7    120
8    165
9    220
10    282
11    348
12    415
13    480
14    540
15    592
16    633
17    660
18    670
19    660
20    633
21    592
22    540
23    480
24    415
25    348
26    282
27    220
28    165
29    120
30    84
31    56
32    35
33    20
34    10
35    4
36    1
合计    10000
周期矩阵，第二步，仅仅列出了7列数据，还有12列数据未上传，把周期+周期，（行，列数据对称矩阵，交叉点为实际数据区域）。
#16
独木星空2022-11-01 19:36
周期数    0    1    2    3    4    5    6
0    0    1    2    3    4    5    6
1    1    2    3    4    5    6    7
2    2    3    4    5    6    7    8
3    3    4    5    6    7    8    9
4    4    5    6    7    8    9    10
5    5    6    7    8    9    10    11
6    6    7    8    9    10    11    12
7    7    8    9    10    11    12    13
8    8    9    10    11    12    13    14
9    9    10    11    12    13    14    15
10    10    11    12    13    14    15    16
11    11    12    13    14    15    16    17
12    12    13    14    15    16    17    18
13    13    14    15    16    17    18    19
14    14    15    16    17    18    19    20
15    15    16    17    18    19    20    21
16    16    17    18    19    20    21    22
17    17    18    19    20    21    22    23
18    18    19    20    21    22    23    24
19    19    20    21    22    23    24    25
20    20    21    22    23    24    25    26
21    21    22    23    24    25    26    27
22    22    23    24    25    26    27    28
23    23    24    25    26    27    28    29
24    24    25    26    27    28    29    30
25    25    26    27    28    29    30    31
26    26    27    28    29    30    31    32
27    27    28    29    30    31    32    33
28    28    29    30    31    32    33    34
29    29    30    31    32    33    34    35
30    30    31    32    33    34    35    36
31    31    32    33    34    35    36    37
32    32    33    34    35    36    37    38
33    33    34    35    36    37    38    39
34    34    35    36    37    38    39    40
35    35    36    37    38    39    40    41
36    36    37    38    39    40    41    42

统计4/2    1    2    3    4    5    6    7
1    1    2    3    4    5    6    7
4    4    8    12    16    20    24    28
10    10    20    30    40    50    60    70
20    20    40    60    80    100    120    140
35    35    70    105    140    175    210    245
56    56    112    168    224    280    336    392
84    84    168    252    336    420    504    588
120    120    240    360    480    600    720    840
165    165    330    495    660    825    990    1155
220    220    440    660    880    1100    1320    1540
282    282    564    846    1128    1410    1692    1974
348    348    696    1044    1392    1740    2088    2436
415    415    830    1245    1660    2075    2490    2905
480    480    960    1440    1920    2400    2880    3360
540    540    1080    1620    2160    2700    3240    3780
592    592    1184    1776    2368    2960    3552    4144
633    633    1266    1899    2532    3165    3798    4431
660    660    1320    1980    2640    3300    3960    4620
670    670    1340    2010    2680    3350    4020    4690
660    660    1320    1980    2640    3300    3960    4620
633    633    1266    1899    2532    3165    3798    4431
592    592    1184    1776    2368    2960    3552    4144
540    540    1080    1620    2160    2700    3240    3780
480    480    960    1440    1920    2400    2880    3360
415    415    830    1245    1660    2075    2490    2905
348    348    696    1044    1392    1740    2088    2436
282    282    564    846    1128    1410    1692    1974
220    220    440    660    880    1100    1320    1540
165    165    330    495    660    825    990    1155
120    120    240    360    480    600    720    840
84    84    168    252    336    420    504    588
56    56    112    168    224    280    336    392
35    35    70    105    140    175    210    245
20    20    40    60    80    100    120    140
10    10    20    30    40    50    60    70
4    4    8    12    16    20    24    28
1    1    2    3    4    5    6    7

周期数    统计6
0    1
1    6
2    21
3    56
4    126
5    252
6    462
7    792
8    1287
9    2002
10    2997
11    4332
12    6062
13    8232
14    10872
15    13992
16    17577
17    21582
18    25927
19    30492
20    35127
21    39662
22    43917
23    47712
24    50877
25    53262
26    54747
27    55252
28    54747
29    53262
30    50877
31    47712
32    43917
33    39662
34    35127
35    30492
36    25927
37    21582
38    17577
39    13992
40    10872
41    8232
42    6062
43    4332
44    2997
45    2002
46    1287
47    792
48    462
49    252
50    126
51    56
52    21
53    6
54    1
合计    1000000
周期矩阵，第三步，仅仅列出了7列数据，还有12列数据未上传，把周期+周期，统计4*统计2（行，列数据对称矩阵，交叉点为实际数据区域）。
#17
独木星空2022-11-01 19:46
最后一步是单位矩阵，与周期矩阵耦合，即列为，周期数*周期值，行是单位矩阵合成值；周期统计6*单位矩阵统计6；原来是自运算，最后一步为混合运算。
     原理是把未知数表示成：tP+r的形式，P为周期值，即未知数不能取P的倍数，t为周期数，从0开始，r是余数，0<r<P-1.
     周期t的实现，与单位矩阵r的实现，各自独立，最后一步在关联在一起，它们属于分步关系，所以用乘法（方法数）。
     这是Excel的流程图，转化成VB6即可。
#18
独木星空2022-11-02 07:21
回复 10楼 wmf2014
希望先生给出一个实例。
#19
wmf20142022-11-02 10:10
所以这些表和x+y+z+u+v+m=N有什么关系呢？谁是N？哪些又是对应xyzuvm的？模7是剔除被7整除的吗？看不懂。
#20
独木星空2022-11-03 14:45
回复 19楼 wmf2014
这些表与它的关系，第一步，相当于x+y=N
                  第二步，相当于(x+y)+(z+u)=N
                  第三步，相当于[(x+y)+(z+u)]+(v+m)=N
     这三步，周期矩阵，与单位矩阵，操作步骤一样，只是起点，与参与的元素不同。
     
     单位矩阵，用1到P-1之间的几个元素，不能用0，也不能用P（限制条件值，比如，未知数，或者说变量，不能取7的倍数，则P=7，所用值就是1,2,3,4,5,6了）

      但是周期矩阵是从0开始，到某一个值即可，如果，想获得10个周期的数据，则此时，是从0到9，即0代表第一个周期，9实际上是第10个周期的。
      如N=36时，可以写成7*5+1的形式，7是限制条件（不能取它的倍数），5是周期值，5个周期，实际求出来的是第六个周期上的数据，在周期矩阵与单位矩阵耦合时，周期矩阵的值（周期数），需要乘7（周期值，或不能取得某数的倍数中，某数，这里不能取7的倍数，某数即7了）；但是，单位矩阵的合成值不变，直接参与运算，统计值，是得到这个合成值的方法数，即得到对应N的不定方程的解组数。
       第一步，统计用的是Excel中的COUNTIF(B$2:G$7,I2)计数函数
       以后各步，统计用的是Excel中的SUMIF(B$16:L$26,AA16,O$16:Y$26)计数函数
#21
独木星空2022-11-03 21:20
好的编程都是建立在对问题的熟练程度上，对问题的来龙去脉不清楚，你就不可能有好的算法。
#22
wmf20142022-11-04 09:04
以下是引用独木星空在2022-11-3 14:45:41的发言：

这些表与它的关系，第一步，相当于x+y=N
                  第二步，相当于(x+y)+(z+u)=N
                  第三步，相当于[(x+y)+(z+u)]+(v+m)=N
     这三步，周期矩阵，与单位矩阵，操作步骤一样，只是起点，与参与的元素不同。
     
     单位矩阵，用1到P-1之间的几个元素，不能用0，也不能用P（限制条件值，比如，未知数，或者说变量，不能取7的倍数，则P=7，所用值就是1,2,3,4,5,6了）

      但是周期矩阵是从0开始，到某一个值即可，如果，想获得10个周期的数据，则此时，是从0到9，即0代表第一个周期，9实际上是第10个周期的。
      如N=36时，可以写成7*5+1的形式，7是限制条件（不能取它的倍数），5是周期值，5个周期，实际求出来的是第六个周期上的数据，在周期矩阵与单位矩阵耦合时，周期矩阵的值（周期数），需要乘7（周期值，或不能取得某数的倍数中，某数，这里不能取7的倍数，某数即7了）；但是，单位矩阵的合成值不变，直接参与运算，统计值，是得到这个合成值的方法数，即得到对应N的不定方程的解组数。
       第一步，统计用的是Excel中的COUNTIF(B$2:G$7,I2)计数函数
       以后各步，统计用的是Excel中的SUMIF(B$16:L$26,AA16,O$16:Y$26)计数函数

搞不懂，太专业了，又是耦合，又是周期的。
为什么不一步到位？单论[(x+y)+(z+u)]+(v+m)=N这个式子，在不考虑排除模数的情况下，似乎总解数是有公式的，比如N=36,在xyzuvm>0的情况下，xyzuvm最大值就是31，在前五个数确定的情况下，最后一个数只有唯一值，前4个值确定的情况下，后两个数有31种组合，所以总解数应该是31×31×31×31×31×1=28629151组解。如果排除1至31被7整除的4个数，总解数应该是27×27×27×27×27×1=14348907组解。
不知道理解的正确不。
#23
独木星空2022-11-04 10:29
回复 22楼 wmf2014
可以一步到位，但是那样的话，数据量会惊人，就比方算10个周期的，限制条件是不能为7的倍数（指未知数（变量）不为7的倍数），10*6个元素=60个元素，60^6=46656000000,这样大的数据量，你如何去处理，即便电算化，程序也是勉为其难，再想大点，根本就不现实，所以有必要，分别处理，把未知数（变量）表示成：tP+r的形式，分别处理r，及周期t即可，它们用乘法原理（也就是最后一步的耦合矩阵），这种处理是把加法，变成乘法，其目的就是大大缩减数据量，用程序可能多少算大点（指你说的一步到位法），要是手工在Excel上计算，那是不可能办到的，所以单位矩阵（即r的处理），和周期矩阵（即对周期的处理），应分步完成，而不是一步到位法，那样处理的结果就是计算机瘫痪，死机。  所以，要拆分，划块，分区，分步完成，而后合到一起。
#24
jklqwe1112022-11-04 20:19
题目是说求满足一定条件的线性方程的解的组数，现在要确认一下是只要数目，还是要列出各个解的值，如果是后者，小规模可以做出，规模大了很难实现，如果只要组数，是有成熟的数学模型和算法的，计算量也不是很大。
#25
独木星空2022-11-04 22:52
回复 24楼 jklqwe111
只要解组数，不要具体解。如N=6，有1组解；N=7时，有6组解；等等。
#26
jklqwe1112022-11-05 08:44
'型如 x1+x2+x3+x4+x5+x6=N 解的个数
'设定 变量个数 number 和值 sum  过滤整除数 modK 变量能否取0

'最简单的形式 modk=1
'可取0的情况 公式为 C(sum+number-1,sum)= C(sum+number-1,number-1)
'当number=2时  sum + 1

'以下是递归代码
Public Function nums0(ByVal sum As Long, ByVal number As Long) As Long
  If number = 2 Then
      nums0 = sum + 1
      Exit Function
  End If
  
  Dim s As Long
  nums0 = 0
  
  For s = 0 To sum
  
     nums0 = nums0 + nums0(sum - s, number - 1)
  
  Next
  
  
End Function

'最简单的形式 modk=1
'不可取0的情况 公式为 C(sum-1,number-1) C(sum-1,sum-number)
'当number=2时  sum - 1

'以下是递归代码

Public Function nums1(ByVal sum As Long, ByVal number As Long) As Long
If number = 2 Then
      nums1 = sum - 1
      Exit Function
  End If
  
  Dim s As Long
  nums1 = 0
  
  For s = 1 To sum - 1
  
     nums1 = nums1 + nums1(sum - s, number - 1)
  
  Next
  
  
End Function
' 有过滤条件，写出组合公式很困难，但还有其他的数学模型，以后再说
'在函数nums1基础上添加过滤条件，写出代码还是可以的
'


Public Function nums1ModK(ByVal sum As Long, ByVal number As Long, ByVal ModK As Long)
  Dim k As Long
  Dim r As Long
  
  If number = 2 Then
      nums1ModK = sum - 1
      k = (sum - 1) \ ModK '需要过滤的个数
      r = sum Mod ModK
      If r = 0 Then 'sum能被整除
         nums1ModK = nums1ModK - k '当sum能被整除时，两个变量必定同被整除或同式不被整除，那么两个同被整除变量要剪掉两个解的个数
      Else
         nums1ModK = nums1ModK - k * 2
      End If
      Exit Function
  End If
  
  Dim s As Long
  nums1ModK = 0
  
  For s = 1 To sum - 1
     If (s Mod ModK) <> 0 Then nums1ModK = nums1ModK + nums1ModK(sum - s, number - 1, ModK)
      
  Next
End Function

'当sum增大时，解的个数迅速增加，sum<500时解的个数没超过long范围，如果要计算更大的值，就要增加大数处理了
#27
独木星空2022-11-05 20:18
我看，有重复。直接计算，是我们最终追求的目标。
#28
独木星空2022-11-08 17:20
一般的数论方法是用母函数法，但是，对于一个多变的题型，它（指母函数法）并不适应。
#29
wmf20142022-11-09 16:22
感觉只需要解总数应该有公式直接运算，用最笨的遍历法写了个excel vba探索，建议和值取小于25的数做实验，否则太慢了。有数学高手可以试着摸索一下规律。
只有本站会员才能查看附件，请 登录

只有本站会员才能查看附件，请 登录
#30
jklqwe1112022-11-09 17:02
我看，有重复


以下是两组数据，看看其中是否有重复的
x+y+z+a+b+c=8 - mod 3

21

1     1     1     1     1     3     
1     1     1     1     2     2     
1     1     1     1     3     1     
2     1     1     1     1     2     
2     1     1     1     2     1     
3     1     1     1     1     1     
1     2     1     1     1     2     
1     2     1     1     2     1     
2     2     1     1     1     1     
1     3     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     3     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     
1     1     1     3     1     1     


x+y+z+a=14 - mod 3

90

1     1     1     11   
1     1     2     10   
1     1     4     8     
1     1     5     7     
1     1     7     5     
1     1     8     4     
1     1     10    2     
1     1     11    1     
2     1     1     10   
2     1     4     7     
2     1     7     4     
2     1     10    1     
4     1     1     8     
4     1     2     7     
4     1     4     5     
4     1     5     4     
4     1     7     2     
4     1     8     1     
5     1     1     7     
5     1     4     4     
5     1     7     1     
7     1     1     5     
7     1     2     4     
7     1     4     2     
7     1     5     1     
8     1     1     4     
8     1     4     1     
10    1     1     2     
10    1     2     1     
11    1     1     1     
1     2     1     10   
1     2     4     7     
1     2     7     4     
1     2     10    1     
2     2     2     8     
2     2     5     5     
2     2     8     2     
4     2     1     7     
4     2     4     4     
4     2     7     1     
5     2     2     5     
5     2     5     2     
7     2     1     4     
7     2     4     1     
8     2     2     2     
10    2     1     1     
1     4     1     8     
1     4     2     7     
1     4     4     5     
1     4     5     4     
1     4     7     2     
1     4     8     1     
2     4     1     7     
2     4     4     4     
2     4     7     1     
4     4     1     5     
4     4     2     4     
4     4     4     2     
4     4     5     1     
5     4     1     4     
5     4     4     1     
7     4     1     2     
7     4     2     1     
8     4     1     1     
1     5     1     7     
1     5     4     4     
1     5     7     1     
2     5     2     5     
2     5     5     2     
4     5     1     4     
4     5     4     1     
5     5     2     2     
7     5     1     1     
1     7     1     5     
1     7     2     4     
1     7     4     2     
1     7     5     1     
2     7     1     4     
2     7     4     1     
4     7     1     2     
4     7     2     1     
5     7     1     1     
1     8     1     4     
1     8     4     1     
2     8     2     2     
4     8     1     1     
1     10    1     2     
1     10    2     1     
2     10    1     1     
1     11    1     1     
#31
独木星空2022-11-10 12:40
回复 30楼 jklqwe111
似乎第一组不符合题意。mod3是否为限制条件。那个N=8时，六个自变量，自变量不能取3的倍数，不定方程有多少组解？
第二组，粗略看符合题意，四个自变量，自变量不能取3的倍数，当N=14时，是那90组解吗？
#32
jklqwe1112022-11-10 13:37
N=8时，六个自变量，自变量不能取3的倍数，不定方程有 21 组解
90 是下面一组解的个数
第一组还会有别的解吗
#33
独木星空2022-11-10 15:03
回复 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
jklqwe1112022-11-10 16:24
上次第一组给出的是没有限制条件的数据，去除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
wmf20142022-11-13 15:36
对遍历算法优化了下，速度提升了不少。还是没理解题主用那种表表达的意思，相信题主的算法更优秀（没有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
独木星空2022-11-13 17:47
回复 35楼 wmf2014
专业性很强！佩服。如果知道了解题原理，估计速度猛进。我所设计的模型，不是遍历，而是模块（区域）替换，相当于二分法。
#37
wmf20142022-11-17 15:12
算法再次优化，速度提升了一个量级。接下来在要解决的非遍历算法里，我感觉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
独木星空2022-11-17 15:49
回复 37楼 wmf2014
做几层嵌套，把符合条件的计数，不符合的不计数（或许没有这个必要考虑），在每层嵌套中设置一个选择语句，非整除3时，正常运行，整除时，此变量增加1执行（在正常的基础上执行）；又或者设置分道执行，首先执行第一选择，选取标准，加1后，不整除；后选择第二步，加2执行（非此即彼，它们互不相容）。
#39
mrexcel2022-11-18 23:24
如果只需要解的数目，递归就可以，如计算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
mrexcel2022-11-19 01:04
以下是引用独木星空在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秒左右
#41
jklqwe1112022-11-19 11:10
我认为这个题目就是一个计数问题，解决这类问题最基本的方法就是枚举了，如果没有限制条件，那么就可以用组合的方法计算，循环迭代或者递归，其实就是枚举，写出程序不难关键在于找到优化的方法，下面的代码是递归程序，只有一些优化，没有找到更好的优化方法  6 数相加和值100 模 3 用时 0.24秒 和 200  用时 3.1 秒 和 300 用时 15.5 秒
Public Function nums1ModK(ByVal sum As Long, ByVal number As Long, ByVal ModK As Long)
  Dim n As Long
  Dim r As Long
  Dim i As Long
  Dim j As Long
   Dim k As Long
  Dim str As String
  
  If sum < number Then
      nums1ModK = 0
      Exit Function
     
   End If
     
     
  
  If number = 2 Then
      nums1ModK = sum - 1
      n = (sum - 1) \ ModK '需要过滤的个数
      r = sum Mod ModK
      If r = 0 Then 'sum能被整除
         nums1ModK = nums1ModK - n '当sum能被整除时，两个变量必定同被整除或同式不被整除，那么两个同被整除变量要剪掉两个解的个数
      Else
         nums1ModK = nums1ModK - n * 2
      End If
      
      
      Exit Function
  End If
  
  Dim s As Long
  nums1ModK = 0
 
  For s = 1 To sum - (number - 1)
     If (s Mod ModK) <> 0 Then
         
         nums1ModK = nums1ModK + nums1ModK(sum - s, number - 1, ModK)
     End If
  Next
End Function
#42
jklqwe1112022-11-19 11:22
这道题可以使用生成函数来解决，但是这个模型计算量与枚举法等同，只是比较容易找到优化的方法，比如保存中间计算结果，空间换时间，下面计算程序用三个数组保存中间结果，效果很明显，计算速度很快

 6 数相加和值100 模 3 用时 0.00724秒 和 200  用时 0.051 秒 和 300 用时 0.07 秒

Public Function numsModK(ByVal sum As Long, ByVal number As Long, ByVal ModN As Long)
   '多项式乘的展开式中幂等于sum 的系数(x^1+ ...+x^k )^number (k=iif(k mod ModK =0,0,k) k<=sum-(number-1))
   Dim c() As Long
   
   Dim a() As Long
  
   Dim b() As Long
  
   Dim n As Long
   Dim k As Long
   Dim i As Long
   Dim j As Long
    Dim u(1) As Variant
   
   Dim v1 As Long
   Dim v2 As Long
   Dim tmp As Long
   ReDim c(1 To sum)
   
   ReDim a(1 To sum)
   
   ReDim b(1 To sum)
  
   
   
   For n = 1 To sum
     If (n Mod ModN) = 0 Then
        a(n) = 0
        
        b(n) = 0
        
      Else
        a(n) = 1
            
        b(n) = 1
      End If
     Next
     v1 = 0
     v2 = 1
     u(v1) = b
   
     u(v2) = c
     For k = 2 To number
       For n = 1 To sum
         u(v2)(n) = 0
       Next
       For i = 1 To sum - (number - 1)
              
              For j = 1 To sum - 1
               
                   If i + j <= sum Then
                      u(v2)(i + j) = u(v2)(i + j) + u(v1)(j) * a(i)
                   Else
                      Exit For
                   End If
               
              Next
                        
      Next
      v1 = v1 Xor 1&
      v2 = v2 Xor 1&
     
     Next
   
  numsModK = u(v1)(sum)
 
End Function
#43
jklqwe1112022-11-19 11:29
sum 100  num 6  mod 3    number  7131432
sum 200  num 6  mod 3    number  231122463
sum 300  num 6  mod 3    number  1832583390
#44
独木星空2022-11-19 16:26
回复 43楼 jklqwe111
6个未知数，只是不能取3的倍数，解组数感觉有点小。当然，去掉1/3的数不参与运算，它的选择性是少的太多，但是6个未知数，解组数的数量公式是周期值的5次多项式形式，100/3=33.3个周期。
#45
jklqwe1112022-11-19 18:04
回复 44楼 独木星空
不知你认为的大的规模是什么样地
#46
wmf20142022-11-24 11:26
回复 42楼 jklqwe111
已经很快了！
#47
mrexcel2022-11-24 21:33
递归效率太低，改成数组快了很多：
程序代码：
Function Sol(ByVal sum&, ByVal n&, Optional ByVal mo&) 'As Long
    Dim s(), i&, j&, k&
    ReDim s(1 To sum, 1 To n)
    For i = 1 To sum
        If i Mod mo Then s(i, 1) = 1
    Next

    For k = 2 To n
        For i = 1 To sum - 1
            If s(i, k - 1) Then
                For j = 1 To sum - i
                    If s(j, 1) Then s(i + j, k) = s(i + j, k) + s(i, k - 1)
                Next
            End If
        Next
    Next
    Sol = s(sum, n)
End Function
Sub Calc()
    Dim t!
    t = Timer
    Debug.Print Sol(2000, 6, 3); Timer - t & " seconds"
End Sub


6 数相加和值2000 模 3 共计 23053345578333 个， 用时0.309375 seconds
7 数相加和值2000 模 3 共计 81958890960219 个， 用时0.9640625 seconds
20 数相加和值3000 模 3 共计 2.87277983642225E+45 个， 用时3.265625 seconds
#48
mrexcel2022-11-24 22:42
数值计算还是Python相对更好些，vb6大于10^15的结果都是科学计数法，精确数字还得自己写大数运算模块。

50 数相加和值5000 模 3 共计 45745843619405329412424426930045641589286621640968244656258153368255323476091005934810174314429835433406626992 个
#49
mrexcel2022-11-24 22:55
多条件稍作修改即可，如：
程序代码：
Function Sol(ByVal sum&, ByVal n&, ParamArray mo()) 'As Long
    Dim s(), i&, j&, k&
    ReDim s(1 To sum, 1 To n)
    For j = 1 To sum
        s(j, 1) = 1
                For i = 0 To UBound(mo) - 1 Step 2
            If j Mod mo(i) = mo(i + 1) Then s(j, 1) = 0: Exit For
        Next
    Next

    For k = 2 To n
        For i = 1 To sum - 1
            If s(i, k - 1) Then
                For j = 1 To sum - i
                    If s(j, 1) Then s(i + j, k) = s(i + j, k) + s(i, k - 1)
                Next
            End If
        Next
    Next
    Sol = s(sum, n)
End Function
Sub Calc()
    Dim t!
    t = Timer
    Debug.Print Sol(1000, 9, 3, 0, 5, 0, 5, 2, 7, 1, 7, 5, 11, 3); Timer - t & " seconds"
End Sub


返回：
104857006764168  0.0715625 seconds

即9个未知数的和等于1000，若每个解模3<>0,模5<>0,模5<>2,模7<>1,模7<>5,模11<>3，则有104857006764168  组解，运行0.07秒左右

[此贴子已经被作者于2022-11-25 08:12编辑过]
#50
独木星空2022-11-25 07:41
回复 47楼 mrexcel
的确够快。主要是给出了不同的算法。
我的也是划块，分区进行计算，矩阵化处理。
#51
jklqwe1112022-11-25 19:03
如果增加未知数，还是有优化的空间的，这个问题是可以用多项式乘法来表达的，由于多项式是一个式子，就可以看做是多项式乘方，由此可以用快速幂方法计算。
程序代码：

Function Solaa(ByVal sum&, ByVal n&, Optional ByVal mo&) As Double

    Dim i&, j&, a&, b&, xa&, xb&
    If sum < n Then
      Solaa = 0
      Exit Function
    End If
    Dim s() As Double
    Dim x() As Double
    ReDim s(1 To sum, 0 To 1)
    ReDim x(1 To sum, 0 To 1)
   
   
    For i = 1 To sum
        If i Mod mo Then
        
           x(i, 1) = 1
           s(i, 1) = 1
        End If
           
    Next
   
    a = 0
    b = 1
    xa = 0
    xb = 1
    n = n - 1
    Do While n > 0
   
    If n And 1& Then
           
        For i = 1 To sum - 1
              If s(i, b) Then
                For j = 1 To sum - i
                    If x(j, xb) Then s(i + j, a) = s(i + j, a) + s(i, b) * x(j, xb)
                Next
              End If
        Next
        
      
        a = a Xor 1&
        b = b Xor 1&
      
        
         For i = 1 To sum
          s(i, a) = 0
         Next
         
     End If
     
     n = n \ 2
     
     If n = 0 Then Exit Do
        For i = 1 To sum - 1
              If x(i, xb) Then
                For j = 1 To sum - i
                    If x(j, xb) Then x(i + j, xa) = x(i + j, xa) + x(i, xb) * x(j, xb)
                    
                Next
               
              End If
        Next
        xa = xa Xor 1&
        xb = xb Xor 1&
      
        
         For i = 1 To sum
            x(i, xa) = 0
         Next
        
   
    Loop
   
    Solaa = s(sum, b)
End Function


在未知数比较多的情况下，速度的提升还是比较明显的

和 5000 ，50 未知数 模 3 时间 6.5 秒 未优化前要运行 26.5 秒
12
©2024, BCCN.NET
电脑版