(答案參考至
這裡)
以下解析說明的部分會用小括號括起並且縮小上提
(像這樣)
想像題目是:現在有十袋金幣,每袋有A枚,不知道幾袋真幾袋假,要怎麼秤一次就秤出來?(換成這邊的毒糖果也行)
參考該網頁下面的方法:
取:A, A-1
一:A, A-1
二:2A-1
(2A-1)-1 = A-2 < A-1
取:A, A-1, A-2
一:A ~ A-2
二:2A-1 ~ 2A-3
三:3A-3
(3A-3)-1-(2A-1) = A-3 , (2A-3)-1-A = A-4
取:A, A-1, A-2, A-4
一:A ~ A-4
二:2A-1 ~ 2A-6
三:3A-3 ~ 3A-7
四:4A-7
就這樣一直做到十~
不過這樣太辛苦了,我們可以好好研究裡面出現的數字。
要找下一個是多少時,必須從[(n)袋中最小的數字]-1-[(n-1)袋中最大的數字],並且取最小值
因為前後相減,如果只看A的部分一定會剩一個A;互相比大小又可以省略中間的-1
所以只要看減號後面的數字即可,即[(n)袋中最大的數字
(這裡指的是減號後面的數字)]-[(n-1)袋中最小的數字],並且取最大值
以下以第五袋為例
三(7)-二(1) = 6 , 二(6)-一(0) = 6
取:A, A-1, A-2, A-4, A-7
(-6-1)
一:A ~ A-7
二:2A-1 ~ 2A-11
三:3A-3 ~ 3A-13
四:4A-7 ~ 4A-14
五:5A-14
接者再研究我們拿來減的數字
如上面三(7)其來由是(A-1)+(A-2)+(A-4)得到A-7來的
所以取的數字也只看減號後面的數字的話
三的最大值即是最大的三個數相加,二的最小值即是最小的兩個數相加
以下以第六袋舉例
已取:0, 1, 2, 4, 7
需檢查:(7+4)-0、(7+4+2)-(0+1)、(7+4+2+1)-(0+1+2)
我們可以發現上式減號左邊的數是從右邊
(0,1,2,4,7的7)一個一個加進來;右邊的數是從左邊
(0,1,2,4,7的0)一個一個加進來。並且左邊的數會比右邊的數多一個。
也就是說,從第一式的左邊取7+4右邊取0,到第二式再+2-1,第三式再+1-2,可以發現,如果所有的數字都被取完了,那其得到的結果就是我們要的最大值。
第六袋就是後三減前二 = (7+4+2)-(0+1) = 12
取:0, 1, 2, 4, 7, 13
(12+1)
到此已經不需要把每種情況寫出來,故略。
第七袋:前四減後三 = (13+7+4+2)-(0+1+2) = 23
取:0, 1, 2, 4, 7, 13, 24
依此類推,到十是0, 1, 2, 4, 7, 13, 24, 46, 88, 172
現在列出範圍
一:A ~ A-172
二:2A-1 ~ 2A-260
三:3A-3 ~ 3A-306
(略)
在這些範圍彼此不能重覆到的最小的A,就是我們要的答案
所以(2A-260)要大於A,(3A-306)要大於(2A-1)
移項就會發現,我們要找的A,正好是第十一袋的值 = (172+88+46+24+13)-(0+1+2+4)+1 = 337
把337帶回A,就得到此題的答案了。
稍微列出幾項來找那串數列的規律:
0 |
1 |
2 |
4 |
7 |
13 |
24 |
46 |
a |
b |
c |
d |
e |
f |
g |
h |
|
a+1 |
b+1 |
c+b-a+1 |
d+c+b-b-a+1 |
e+d+c-b-a+1 |
f+e+d+c-c-b-a+1 |
g+f+e+d-c-b-a+1 |
被右減 |
b-a |
c-a |
d-b |
e-b |
f-c |
g-c |
|
f(1)=0,f(2)=1,f(n)=f(n-1)×2-f([n/2])
([]是高斯符號) ,n為大於2的自然數。
用此方法的優點是不用寫程式就可以知道答案
缺點是答案並不一定是最小值(從7袋開始就不是,而且越差越大)
原因是我們把每袋的情況弄成一個範圍,而這個範圍裡面不是每個數字都被用到,所以可能可以減得更少,但這樣就不方便計算了。