主题:[讨论]哎!QBasic真的没什么人了,再出个缩水的算法问题
这是一个关于彩票的算法:
在数学上一个复式投注单假设有n个三选,m个双选,其中n+m<=13,
所有的投注单构成了一个集合C(n,m),C(n,m)共有3的n次方乘以
2的m次方个元素,每一个元素可以表示成一个13位长的三重码,
在组合数学中已经证明存在至少一个C(n,m)的子集K(n,m),每一
个C(n,m)中的元素,都存在一个K(n,m)中的元素,他们之间仅有
1位的差别,即所谓的汉明距离(Hamming Distance)等于1。满足
上述条件的最小子集K(n,m)称为问题的一个最优解
这个问题在网上看到好多人提,但没有看到有人说解法,我说简单一点:
如果有这样6个数 1,2,3,4,5,6
将它们以3个一组尽可能不重复的分组则有:
C{n,m}=
1-2-3 1-2-4 1-2-5 1-2-6 1-3-4 1-3-5 1-3-6 1-4-5 1-4-6 1-5-6
2-3-4 2-3-5 2-3-6 2-4-5 2-4-6 2-5-6 3-4-5 3-4-6 3-5-6 4-5-6
共是20组
现在求在C{n,m}中取一个子集K{n,m}使取任意二个数:
1-2 1-3 1-4 1-5 1-6 2-3 2-4 2-5 2-6 3-4 3-5 3-6 4-5 4-6 5-6
都能够在K{n,m}这个子集中找到元素
请在C{n,m}找到这个子集(要使K{n,m}尽可能的小)
数可以不是6个这么多,这里便于说明才说6个,这个问题是有多个解的
请高手用QBasic编写算法[em1][em1][em1]
在数学上一个复式投注单假设有n个三选,m个双选,其中n+m<=13,
所有的投注单构成了一个集合C(n,m),C(n,m)共有3的n次方乘以
2的m次方个元素,每一个元素可以表示成一个13位长的三重码,
在组合数学中已经证明存在至少一个C(n,m)的子集K(n,m),每一
个C(n,m)中的元素,都存在一个K(n,m)中的元素,他们之间仅有
1位的差别,即所谓的汉明距离(Hamming Distance)等于1。满足
上述条件的最小子集K(n,m)称为问题的一个最优解
这个问题在网上看到好多人提,但没有看到有人说解法,我说简单一点:
如果有这样6个数 1,2,3,4,5,6
将它们以3个一组尽可能不重复的分组则有:
C{n,m}=
1-2-3 1-2-4 1-2-5 1-2-6 1-3-4 1-3-5 1-3-6 1-4-5 1-4-6 1-5-6
2-3-4 2-3-5 2-3-6 2-4-5 2-4-6 2-5-6 3-4-5 3-4-6 3-5-6 4-5-6
共是20组
现在求在C{n,m}中取一个子集K{n,m}使取任意二个数:
1-2 1-3 1-4 1-5 1-6 2-3 2-4 2-5 2-6 3-4 3-5 3-6 4-5 4-6 5-6
都能够在K{n,m}这个子集中找到元素
请在C{n,m}找到这个子集(要使K{n,m}尽可能的小)
数可以不是6个这么多,这里便于说明才说6个,这个问题是有多个解的
请高手用QBasic编写算法[em1][em1][em1]