这是工作申请中的一个问题:
“父亲有两个儿子和999幅画。每幅画具有不同的值(value):第一幅值1幅，第二幅值2幅，依此类推，直到最后一幅画的幅值999为止。他想将他的所有画均分为两幅。儿子，以便每个儿子都获得同等的值(value)。用999幅画作有多少种方法？
例如:如果父亲有7幅画，他可以通过给第一个儿子1、6和7来公平地划分它们。第二个儿子将得到2、3、4和5。两者的总和为14。有7幅画，父亲可以用4种方法公平地将它们划分(其他3种未在此处列出)，因此解决方案是4。
提示:这个数字可能很大，所以请向我们发送您的最后10位数字和解决方案的略图。”
我所做的是尝试使用蛮力方法，通过编写一个C#程序来加总所有可能的组合，该程序使用循环内的循环编写它自己的C#程序，如下所示:
StringBuilder sb = new StringBuilder();
for (short i = 2; i <= 999; i++) //starts from 2 because 1 is always added to the total for one side
{
sb.AppendLine("for (byte i" + i.ToString() + " = 0; i" + i.ToString() + " < 2; i" + i.ToString() + "++)");
sb.AppendLine("{");
}
for (int i = 2; i <= 999; i++)
{
sb.Append("if (i" + i.ToString() + " == 1) { total += " + i.ToString() + "; }\n");
}
for (short i = 2; i <= 999; i++)
{
sb.AppendLine("}");
}
然后在if块中将其添加到结果中:
if (total == 249750)
{
count++; //count is a BigInteger
}
total = 1;
这种方法在技术上应该可以工作(在较少数量的绘画上进行测试)，但是问题是它是一个HUUUGE数，以这种方式在我的计算机上计算结果大约需要一百万年...是否有一些方法？在合理的时间内完成此操作的数学技巧？
最佳答案
确定第一个儿子可以通过多少种方式获得值k(其中k是一个参数)时，更容易解决更普遍的问题。找出适当的概括是一门艺术。在算法类(class)中以动态编程的名称进行教授。
令x为变量。需要的数学见解是，对于n绘画，多项式乘积中x^k的系数
x (1 + x^2) (1 + x^3) ... (1 + x^n)
x中的数字是长子获得k值的方式(包括绘画1的方式)。这是因为该产品分发到(sum for i_2 = 0 to 1) (sum for i_3 = 0 to 1) ... (sum for i_n = 0 to 1)
x^(1 + 2 i_2 + 3 i_3 + ... + n i_n),
有效地是您的蛮力解决方案评估该产品的方式。这里的动态程序等效于一次分配一个因子，而不是一次分配所有因子，例如，
x (1 + x^2) = x + x^3
x (1 + x^2) (1 + x^3) = (x + x^3) (1 + x^3)
= x + x^3 + x^4 + x^6.
x (1 + x^2) (1 + x^3) (1 + x^4) = (x + x^3 + x^4 + x^6) (1 + x^3)
= x + x^3 + x^4 + x^6 + x^4 + x^6 + x^7 + x^9
= x + x^3 + 2 x^4 + 2 x^6 + x^7 + x^9.
节省的时间来自重复的条款。我们只需要处理六个术语，而不是八个(两个至第三次幂)。
仅保留最后十位数字意味着我们可以将整数乘以
10^10模来评估此乘积。结果，我们可以减少中间系数的模数，以避免求大数。在竞争性编程社区中广为人知的该技巧已在抽象代数或数论类(class)中正式涉及。在Mathematica中:
In[1]:= Coefficient[x Product[1+x^i,{i,2,7}],x^(Sum[i,{i,1,7}]/2)]
Out[1]= 4
In[2]:= Coefficient[x Product[1+x^i,{i,2,8}],x^(Sum[i,{i,1,8}]/2)]
Out[2]= 7
在Java中:
public class PartitionPaintings {
public static void main(String[] args) {
long[] p = new long[] {0, 1};
for (int i = 2; i <= Integer.parseInt(args[0]); i++) {
long[] q = new long[p.length + i];
for (int k = 0; k <= p.length - 1; k++) {
for (int j = 0; j <= 1; j++) {
q[k + i * j] = (q[k + i * j] + p[k]) % 10000000000L;
}
}
p = q;
}
System.out.println(p[(p.length - 1) / 2]);
}
}
关于c# - 父亲，两个儿子，999幅画，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26152992/