求组合算法

Question

已知道1－33个数字里面任意取出6个数字的组合有1107568种（纸上算的。电脑上运行死机。）
每个组合中6个数字相加后，会出现相同的和，如何得到最多的相同和数目
比如： 
1+2+3+4+5+12 = 27 
2+3+4+5+6+7 = 27有多少个组合的和是27？
最多的相同和是多少，有多少？有没有好的思路？

Answer 1

用穷举啊，很快的，不到1s
这个是C写的。改造成C#也不难
#include <iostream>
using namespace std;int main(int argc, char *argv[])
{
int nums[6];
int count = 0, i, sum;

for (nums[0] = 1; nums[0] < 34; nums[0] ++) {
for (nums[1] = nums[0] + 1; nums[1] < 34; nums[1] ++) {
for (nums[2] = nums[1] + 1; nums[2] < 34; nums[2] ++) {
for (nums[3] = nums[2] + 1; nums[3] < 34; nums[3] ++) {
for (nums[4] = nums[3] + 1; nums[4] < 34; nums[4] ++) {
for (nums[5] = nums[4] + 1; nums[5] < 34; nums[5] ++) {
sum = 0;
for (i = 0; i < 6; i ++)
sum +=  nums[i];
if (sum == 27)
count++;
}
}
}
}
}
}
cout<<"count: "<<count<<endl; return 0;
}
结果是11
把if (sum == 27)注释掉就变成1107568了

Answer 2

28+29+30+31+32+33=183，所以
#include <iostream>
using namespace std;int main(int argc, char *argv[])
{
int nums[6], sums[184];
int pos, i, sum;

for (i = 0; i < 184; i ++)
sums[i] = 0; for (nums[0] = 1; nums[0] < 34; nums[0] ++) {
for (nums[1] = nums[0] + 1; nums[1] < 34; nums[1] ++) {
for (nums[2] = nums[1] + 1; nums[2] < 34; nums[2] ++) {
for (nums[3] = nums[2] + 1; nums[3] < 34; nums[3] ++) {
for (nums[4] = nums[3] + 1; nums[4] < 34; nums[4] ++) {
for (nums[5] = nums[4] + 1; nums[5] < 34; nums[5] ++) {
sum = 0;
for (i = 0; i < 6; i ++)
sum +=  nums[i];
sums[sum] ++;
}
}
}
}
}
}

sum = 0;
for (i = 0; i < 184; i ++) {
if (sum < sums[i]) {
sum = sums[i];
pos = i;
}
}
cout<<"max: "<<sum<<" = "<<pos<<endl; return 0;
}
最多的结果是172，有2067个

Answer 3

没有什么优化，但是速度还好：using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
class Program
{
static int nTotalSum; static void Main(string[] args)
{
int nTotal = 0;
int nMax = 0;
for (nTotalSum = 21; nTotalSum <= 183; nTotalSum++)
{
int nTest = test(0, 6, 0);
Console.WriteLine("{0}={1}", nTotalSum, nTest);
if (nTest > nMax)
nMax = nTest;
nTotal += nTest;
}
Console.WriteLine("total={0}", nTotal);
Console.WriteLine("max={0}", nMax);
} static int test(int nSum, int nLevel, int j)
{
int i = nTotalSum - nSum;
if (--nLevel <= 0)
{
if (i > j && i <= 33)
return 1;
else
return 0;
} int nCount = 0;
i--;
if (i >= 33)
i = 32;
while (i > j)
nCount += test(nSum + i, nLevel, i--); return nCount;
}
}
}

Answer 4

可以尝试数学推论。只有两个数的时候。
相加和最多的数应该是值域首尾的两个数相加。
如，从1-33中任取两个组合相加，得到的结果集中出现最多的应该是1+33=34。
因为：
1+33 = 2+32 = .... 33+1 = 34 共计33个组合。
而如果是35，则：
2+33 = 3+32 = .... 33+2 = 35 共计32个组合。即，两个数的情况，
在n-m之中任意取数组合相加结果集中出现最多次的数是n+m，出现的次数是m-n+1，偏离这个的结果在结果集中出现的次数是递减的，即n+m+x和n+m-x在结果集中出现的次数是(m-n+1)- x