Excel精英培训网

 找回密码
 注册
数据透视表40+个常用小技巧,让你一次学会!
查看: 4892|回复: 23

[VBA] 用VBA解欧拉计划题目(106)--特殊的子集和:元检验

[复制链接]
发表于 2017-12-30 19:30 | 显示全部楼层 |阅读模式
特殊的子集和:元检验
记S(A)是大小为n的集合A中所有元素的和。若任取A的任意两个非空且不相交的子集B和C都满足下列条件,我们称A是一个特殊的和集:
  • S(B) ≠ S(C);也就是说,任意子集的和不相同。
  • 如果B中的元素比C多,则S(B) > S(C)。
在这个问题中我们假定集合中包含有n个严格单调递增的元素,并且已知其满足第二个条件。
令人惊奇的是,当n = 4时,在所有可能的25组子集对中只有1组需要检验子集和是否相等(第一个条件)。同样地,当n = 7时,在所有可能的966组子集对中只有70组需要检验。
当n = 12时,在所有可能的261625组子集对中有多少组需要检验?

excel精英培训的微信平台,每天都会发送excel学习教程和资料。扫一扫明天就可以收到新教程
发表于 2018-1-1 14:11 | 显示全部楼层
回复

使用道具 举报

 楼主| 发表于 2018-1-1 19:19 | 显示全部楼层
肯定不是。
应该计算是当B,C元素个数相同时,无需检验的情况。
以n=4,(1,2,3,4)4个元素。
B,C元素都是1个时:因为集合是单调递增的,所以无需考察。排除c(4,1)*c(3,1)/2=6组
B,C元素都是2个时:a)因为(1,2)无需检验,所以(14,24),(13,23)也无需检验,。。。,共排除12组
     b)因为单调递增,所以(12,34),(13,24)也无需检验
     综上,只需检验(14,23)
B,C元素都是2个时:。。。。。。
是否可以用递推以f(n)为n个元素无需检验的情况,得出f(n+1)?
想不大清楚。
回复

使用道具 举报

发表于 2018-1-1 20:02 | 显示全部楼层
已经能够手工排出结果了。验证了n=4、n=5、n=6、n=7都正确了。

但是,需要思考如何编写检查规则,才能自动计算n=12时的各种状态?

n=4时,仅需检查 b1/c1/c2/b2这种组合,因为b1<c1<c2<b2 所以有可能会有b1+b2=c1+c2
即有可能 c2-b1=b2-c1

n=5时,有5种可能。……
按位置分别是:
1 2 3 4 5
b c c b _ 有1种
b c c c b 有3种 (标c的位置3选2=3)
_ b c c b 有1种

…………
总结一下规律,凡是c组有2个或2个以上被2个b首尾包含时,就有产生和值相等的可能。
而一个隔开一个这样子是肯定不会相等的。即形成b<c,b<c,……这样就不行,
只有 b<c<c<b 才有可能。

…………
VBA需要先列出所有个数相等的组合,然后检查是否含有b<c<c<b这种排列顺序。

似乎也不太难,但是还需要思考思考。

回复

使用道具 举报

发表于 2018-1-1 20:05 | 显示全部楼层
n=12时一共有36828种组合,需要判断是否含有bccb组合。
回复

使用道具 举报

发表于 2018-1-1 20:48 | 显示全部楼层
结果非常简单,需要检查 21605组 含有 1221 或 2112 类型的、个数相同时和值可能会相等的组合。
0.602s 12  36828  21605

具体是,1221类型有 15968个、2112类型有11582个,
需要用字典排除重复,所以最后只有21605组是状态不同的组合。


哈哈。

  1. Dim ar(), dic, k&, k1&, k2&, m&, n&, tms#
  2. Sub test() 'by kagawa 2018/1/1
  3.     tms = Timer
  4.    
  5.     m = 12
  6.     ReDim ar(1 To m)
  7.    
  8.     k = 0: k1 = 0: k2 = 0
  9.     Set dic = CreateObject("Scripting.Dictionary")
  10.     For n = 2 To Int(m / 2)
  11.         Call dgZH(0, 1) '调用组合递归过程 列出全部S(B)个数等于S(C)的组合 并检查是否可能相等(含1221顺序)
  12.     Next
  13.    
  14.     Debug.Print Format(Timer - tms, "0.000s"); m; k; dic.Count
  15.     MsgBox Format(Timer - tms, "0.000s") & vbCr & m & vbCr & k & vbCr & dic.Count
  16. End Sub
  17. Sub dgZH(i1&, t&) '生成个数较少的S(C)组合
  18.     Dim i&, i2&
  19.     For i = i1 + 1 To m - n + t
  20.         ar(i) = 1 '在ar数组记录该元素已被S(C)使用
  21.         If t < n Then
  22.             Call dgZH(i, t + 1)
  23.         Else
  24.             For i2 = 1 To m
  25.                 If ar(i2) = 1 Then Exit For
  26.             Next
  27.             Call dgZH2(i2, 1) '调用生成S(B)组合的递归
  28.         End If
  29.         ar(i) = ""
  30.     Next
  31. End Sub
  32. Sub dgZH2(i2&, t&) '生成个数较多的S(B)组合
  33.     Dim i&, s$
  34.     For i = i2 + 1 To m - n + t
  35.         If ar(i) = "" Then '检查是否未被S(C)使用
  36.             ar(i) = 2 '在ar数组记录该组合
  37.             If t < n Then
  38.                 Call dgZH2(i, t + 1)
  39.             Else
  40.                 k = k + 1
  41.                 s = Join(ar, "")
  42.                 If InStr(s, "1221") + InStr(s, "2112") Then dic(Join(ar)) = ""
  43. '                If InStr(s, "1221") Then k1 = k1 + 1 ': Debug.Print Join(ar) ': Stop
  44. '                If InStr(s, "2112") Then k2 = k2 + 1 ': Debug.Print Join(ar) ': Stop
  45.             End If
  46.             ar(i) = ""
  47.         End If
  48.     Next
  49. End Sub
复制代码

回复

使用道具 举报

发表于 2018-1-1 21:02 | 显示全部楼层
更新,发现无需使用字典,是部分组合既含有1221、又含有2112造成的重复统计。

改进一下,这样更简单。
  1. Dim ar(), k&, k1&, m&, n&, tms#
  2. Sub test() 'by kagawa 2018/1/1
  3.     tms = Timer
  4.    
  5.     m = 12
  6.     ReDim ar(1 To m)
  7.    
  8.     k = 0: k1 = 0
  9.     For n = 2 To Int(m / 2)
  10.         Call dgZH(0, 1) '调用组合递归 列出S(B)个数等于S(C)的组合 检查是否可能相等(含1221或2112顺序)
  11.     Next
  12.    
  13.     Debug.Print Format(Timer - tms, "0.000s"); m; k; k1
  14.     MsgBox Format(Timer - tms, "0.000s") & vbCr & m & vbCr & k & vbCr & k1
  15. End Sub
  16. Sub dgZH(i1&, t&) '生成个数较少的S(C)组合
  17.     Dim i&, i2&
  18.     For i = i1 + 1 To m - n + t
  19.         ar(i) = 1 '在ar数组记录该元素已被S(C)使用
  20.         If t < n Then
  21.             Call dgZH(i, t + 1)
  22.         Else
  23.             For i2 = 1 To m
  24.                 If ar(i2) = 1 Then Exit For '仅需检查C组开始以后的元素组合
  25.             Next
  26.             Call dgZH2(i2, 1) '调用生成S(B)组合的递归
  27.         End If
  28.         ar(i) = ""
  29.     Next
  30. End Sub
  31. Sub dgZH2(i2&, t&) '生成个数较多的S(B)组合
  32.     Dim i&, s$, ss$
  33.     For i = i2 + 1 To m - n + t
  34.         If ar(i) = "" Then '检查是否未被S(C)使用
  35.             ar(i) = 2 '在ar数组记录该组合
  36.             If t < n Then
  37.                 Call dgZH2(i, t + 1)
  38.             Else
  39.                 k = k + 1
  40.                 s = Join(ar, "")
  41.                 If InStr(s, "1221") + InStr(s, "2112") Then k1 = k1 + 1
  42.             End If
  43.             ar(i) = ""
  44.         End If
  45.     Next
  46. End Sub
复制代码
回复

使用道具 举报

发表于 2018-1-1 21:17 | 显示全部楼层
本帖最后由 pengyx 于 2018-1-1 21:19 编辑

2.如果B中的元素比C多,则S(B) > S(C)。并且已知其满足第二个条件(这是你题目的的表述)。所以我认为(1,2,3,4)时需检验(3,12)(4,12)(4,13)(4,23)(4,123)。不明白为什么只需检验(14,23)。或者说为什么需要检验(14,23)

回复

使用道具 举报

发表于 2018-1-2 09:26 | 显示全部楼层
pengyx 发表于 2018-1-1 21:17
2.如果B中的元素比C多,则S(B) > S(C)。并且已知其满足第二个条件(这是你题目的的表述)。所以我认为(1, ...

如果你刻意构造了一个初步满足条件的数组(相邻数之间保证有一定的间隔),那么原则上,个数不等的两个子集,不会出现和值相等的情况,因此无需检查是否相等。

但是,如果B集合和Cl集合中取相同个数的元素时,仍有一定概率会出现和值相等的情形,需要检查确认,保证数组S(A)满足条件。

即,对于任意数组来说,两个任意子集中的任何个数的和值都有可能相等,即S(B)=S(C)。
但是,对于初步满足条件的特殊数组来说,如果有相等的可能,只会出现在B集合、C集合取相同个数时才有可能发生。

就是这个意思。
回复

使用道具 举报

发表于 2018-1-2 09:28 | 显示全部楼层
看起来是个很复杂的问题,只路过,不参与讨论
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|Archiver|Excel精英培训 ( 豫ICP备11015029号 )

GMT+8, 2024-3-28 17:16 , Processed in 1.520110 second(s), 6 queries , Gzip On, Yac On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表