2 sheeranchau sheeranchau 于 2015.05.29 15:39 提问

用C++解决下列数字划分问题的组合数

n,A,Xk均为整数

0<=Xk<=A

X1>=X2>=.....>=Xn

X1+X2+.....+Xn=A

问(X1,X2,.... ,Xn)有多少种组合?
图片说明

3个回答

a1193561652
a1193561652   Rxr 2015.05.29 16:46

没想到什么好方法,最常规的思路是用递归将A一个数一个数的拆分,如果拆分出不合理的数就返回false结束这一支,如果递归n次全部合理的就记为合理的一组。

devmiao
devmiao   Ds   Rxr 2015.05.29 17:28
devmiao
devmiao   Ds   Rxr 2015.05.29 17:28

再贴一个C#的

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
var query = Split(arr, 2);
int max = 0;
foreach (var item in query)
{
// Console.WriteLine(string.Join("|", item.Select(x => string.Join(", ", x))));
int r = item.Sum(x => x.Aggregate(1, (a, b) => a * b));
if (max < r) max = r;
}
Console.WriteLine(max);
}
static IEnumerable<IEnumerable<IEnumerable<int>>> Split(IEnumerable<int> source, int n)
{
int[] splitter = Enumerable.Range(1, n - 1).ToArray();
splitter[n - 2]--;
int[] lastsp = Enumerable.Range(source.Count() - n, n -1).ToArray();
while (splitter.Zip(lastsp, (x, y) => x != y).Any(x => x == true))
{
for (int i = n - 2; i >= 0; i--)
{
if (splitter[i] < lastsp[i])
{
splitter[i]++;
for (int j = i + 1; j < n - 1; j++)
{
splitter[j] = splitter[i] + j - i;
}
break;
}
}
IEnumerable<int>[] result = new IEnumerable<int>[n];
int acc = 0;
for (int i = 0; i < n; i++)
{
if (i == n - 1)
{
result[i] = source.Skip(acc);
}
else
{
result[i] = source.Skip(acc).Take(splitter[i] - acc);
acc = splitter[i];
}
}
yield return result;
}
}
}
}
Csdn user default icon
上传中...
上传图片
插入图片