父亲，两个儿子，999幅绘画

这是一个工作申请的问题： “父亲有两个儿子和999幅绘画，每幅画都有不同的价值：第一个是价值1，第二个是价值2等等，直到最后的绘画价值999.他想把他所有的绘画分给他的两个儿子，这样每个儿子都能得到同样的价值。有999种绘画可以用多少种方式来做？例子：如果父亲有7幅绘画，他可以通过给予第一个儿子的绘画1,6和7来公平地分配他们。第二个儿子将得到2,3,4和5.两者总和等于14。如果有7个绘画，父亲可以将其分为4种方式（其他3种不在这里列出），因此解决方案为4. 提示：数字可能很大，因此请向我们发送解决方案的最后10位数字和草图。“父亲，两个儿子，999幅绘画

我所做的就是尝试使用蛮力的方法，通过写这写它与环内环路自己的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 (total == 249750) 
{ 
    count++; //count is a BigInteger 
} 
total = 1;

这种做法应该在技术上的工作（如在画一个小数目测试），但问题是它是一个HUUUGE号，它会采取像一万年或者在我的电脑上计算结果这样...有一些数学技巧在合理的时间内做到这一点？

来源

2014-10-02 infamous

要问...你真的打算申请这份工作吗？如果你不能通过最初的面试问题而没有进入SO，你确定这是你真正想要/准备好的工作吗？ – 2014-10-02 01:05:26

地狱没有，这是我的联盟的方式：D 目前，至少... – infamous 2014-10-02 01:08:43

是的我明白，我不问，所以我可以欺骗面试，我问，所以我可以学习新的东西并希望为我的技能组添加新内容。我发布了这个链接，以防万一能够解决的人可以申请，如果他想要并且符合要求。（它被mod编辑出来，显然这违反了规则） – infamous 2014-10-02 01:13:59

确定第一个儿子获得价值的方式有多少种更为普遍的问题比较容易k，其中k是一个参数。有一种艺术来确定适当的概括;它在名为动态编程的算法课程中教授。

让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中评估此产品。因此，我们可以减少中间系数的模数以避免诉诸双数。这个技巧，在竞争性编程社区中广为人知，在抽象代数或数论的课程中正式涉及。

在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]); 
    } 
}

来源

2014-10-02 01:59:13

“这个技巧，对于竞争性编程社区而言是众所周知的......” 我知道这里有一个诀窍：D现在，因为我不明白你说的大部分内容，你知道一个很好的免费在线课程代数或数论？ – infamous 2014-10-02 02:39:21

@infamous我个人可以推荐的东西。仅仅学习模块化算术就足以应付最后n位（模m）的输出要求。请注意，真正的加速是来自切换多项式乘法算法。 – 2014-10-02 02:48:18

答案几乎是有道理的.. **除了**模块化算术部分的应用，这是为了保持数字低，不需要BigInteger ...事实证明，10^10是一个很好的数字用于mod，是基于假设答案少于10位长......但是，情况并非如此......在这段代码中用BigInteger代替long给出了完全不同的答案。 ...如果我仍然错误，请澄清一下。 – 2014-10-03 00:45:16

这是数学的工作。

您基本上正在寻找一个number partition，其中一个distinct parts。

所有作品的总价值是整数1 ... 999的总和。 (n * (n+1))/2according to Gauss，所以我们得到：(999 * 1000)/2 = 499500。因此，每个儿子应该得到的绘画总价值为249750.

现在，我们只需要找到不同部分不超过999的那个值的数字分区。我们将我们找到的每个分区分配为集为一个儿子绘画，第二个儿子将获得剩余的绘画（总价值相同）。

所以唯一棘手的部分是找出不同和有界部分的分区函数。但我想你也可以通过编程来实现。

来自德黑兰谢里夫科技大学的Mohammadreza Bidar实际上写了一篇论文，题目为“将整数划分为不同的有限零件，标识和边界”。你可以在INTEGERS, volume 12（这是第8篇文章）中阅读它。

来源

2014-10-02 01:37:58 poke

499500是总价值，所以每个儿子都应该得到一半（249750），这是很容易的部分。不知道高斯公式，但我已经做了一个for循环，我跳过了这个问题的部分，对不起，应该更清楚... ... – infamous 2014-10-02 01:48:10

对不起，我打算写这个号码，不知道为什么我没有。 – poke 2014-10-02 01:51:11

这是如何解决问题的？ – mybirthname 2014-10-02 02:46:59

父亲，两个儿子，999幅绘画

回答

相关问题