父親，兩個兒子，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幅繪畫

回答

相關問題