Re: [問題] 情境式問題：問題商品

看板puzzle作者Favonia (小西風最乖了*^^*)時間10年前 (2013/07/27 21:23)推噓5(5推 0噓 1→)

留言6則, 3人參與討論串2/2 (看更多)

※ 引述《Akerker (阿克克(*〞︶〝)/)》之銘言： : 推 hirabbitt:11、17、20、22、23、24 這串數字怎麼來的試誤? 07/25 17:24 這有個非常有系統的試誤法。想像每一罐都拿出大約一億顆豆子，一看重量馬上就知道幾罐有問題，因為一億實在太多了。例如有兩罐有問題，那大概就是兩億。接著如果每罐拿出的數量差一點點，我們只要看跟兩億差多少逆推哪兩罐壞掉就好。簡單來說，我們假設可以拿出足夠多的豆子，先判斷有幾罐壞掉。就先假設拿出最多顆豆子的罐子拿了 X 顆吧，我們先算出一個 X 夠大時的可行方案，再逆推在那個方案下 X 至少要多少才能「先判斷壞幾罐」。所有罐子拿出來的豆子就以 X - a_i 表示。由大到小排列，第一罐就是 0 因為拿了 X - 0 顆豆子。1 代表拿了 X - 1 顆。以下從只有一罐開始列出所有的重量組合。壞 N 罐後面有個數字 Y 代表數量 N*X - Y 可能會發生。這罐要碼有壞或是沒壞，所以數量是 0 或 X - 0, 也就是壞 0 罐： 0 (代表 0 = 0 * X - 0) 壞 1 罐： 0 (代表 X - 0 = 1 * X - 0) 第二罐加上去後不能讓同一列之中有重複的數字，發現到數字 1 (代表 X - 1) 符合。也就是壞一罐時可能是 X - 0 或 X - 1, 壞兩罐時 2X - 1. 壞 0 罐： 0 壞 1 罐： 0 1 壞 2 罐： 1 在前兩罐不變的情況下，第三罐可以取的最小值是 2 壞 0 罐： 0 壞 1 罐： 0 1 2 壞 2 罐： 1 2 3 壞 3 罐： 3 再來是 4. 如果取 3 的話壞 2 罐時有兩個 3. 壞 0 罐： 0 壞 1 罐： 0 1 2 4 壞 2 罐： 1 2 3 4 5 6 壞 3 罐： 3 5 6 7 壞 4 罐： 7 再來是 7 和 13 壞 0 罐： 0 壞 1 罐： 0 1 2 4 7 13 壞 2 罐： 1 2 3 4 5 6 7 8 9 11 13 14 15 17 20 壞 3 罐： 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 壞 4 罐： 7 10 12 13 14 16 18 19 20 21 22 23 24 25 26 壞 5 罐： 14 23 25 26 27 壞 6 罐： 27 現在來逆推這種方案下 X 至少要多大才不會讓數字相撞。這邊一個簡單的偷懶作法就是讓數字的範圍不會相撞就好啦。例如壞 3 罐最多有 3*X - 3 顆，壞 4 罐最少有 4*X - 26 顆，只要讓 X 比 26-3 大就好。基本上就是看頭尾取差：壞 0 罐： 0 壞 1 罐： 0 1 2 4 7 13 壞 2 罐： 1 2 3 4 5 6 7 8 9 11 13 14 15 17 20 壞 3 罐： 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 壞 4 罐： 7 10 12 13 14 16 18 19 20 21 22 23 24 25 26 壞 5 罐： 14 23 25 26 27 壞 6 罐： 27 要比 13-0, 20-0, 24-1, 26-3, 27-7, 27-14 都還多... X 取 24 就可以讓所有數字範圍分開啦。這六罐就是： 24-0=24, 24-1=23, 24-2=22, 24-4=20, 24-7=17, 24-13=11 （我沒有寫程式幫我算，難免過程有錯，請大家不吝指正）如果有 100 罐豆子，也不要寫程式了，請看 OEIS A005255 和 A005318. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.39 ※ 編輯: Favonia 來自: 140.112.30.39 (07/27 21:56)

推

allen65535

07/27 22:07, , 1^F

07/27 22:07, 1^F

推

jurian0101

07/28 17:07, , 2^F

07/28 17:07, 2^F

推

jurian0101

07/28 17:12, , 3^F

07/28 17:12, 3^F