一次一題

第一個解出來並且正確者可得獎賞(你要用我的來幫他加也沒差啦！還是你們自己在內定要多少?)

最近發的都將是天平問題

確認正確需要有三個人以上看懂

並表示"當事人看懂了並確認無誤"的意見才可計算

那下面是題目：

理論上難度應該是照題號排列

第一題：

1. 有68枚重量互不相同的硬幣，用天平在100次內要找出最重和最輕的硬幣，試說明該怎樣來做。

頭香~
你發這篇文是為了雪恥嗎？
(至於題目我慢慢思考..

恩，這題最爛的想法是每個都比一次啊
可是這樣做的時間複雜度是T(2n)，所以會TLE!!
ㄎㄎ

字自己變大了
不是我故意的XDDD

囧
68枚分三十四組來比 (每組兩個)
大的放一邊，小的放一邊，如下
大的34個     小的34個    (需比34次)

然後大的分十七組來比 (每組兩個)
大的放一邊，小的放一邊，如下
大的大的17個     小的大的17個    (需比17次)
然後大的分八組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的大的大的8個+多1個     小的大的大的8個    (需比8次)
然後大的分四組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的大的大的大的4個+多1個     小的大的大的大的4個    (需比4次)
然後大的分兩組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的大的大的大的大的2個+多1個     小的大的大的大的大的2個    (需比2次)
最後挑其中兩個來比 (一步)
大的再和另一個比 (一步)
最大的即出現了~~

然後小的分十七組來比 (每組兩個)
大的放一邊，小的放一邊，如下
大的小的17個     小的小的17個    (需比17次)
然後小的分八組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的小的小的8個+多1個     小的小的小的8個    (需比8次)
然後小的分四組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的小的小的小的4個+多1個     小的小的小的小的4個    (需比4次)
然後小的分兩組來比 (每組兩個，多一個)
大的放一邊，小的放一邊，如下
大的小的小的小的小的2個+多1個     小的小的小的小的小的2個    (需比2次)
最後挑其中兩個來比 (一步)
小的再和另一個比 (一步)
最小的即出現了~~

共34+(17+8+4+2+1+1)*2=100

YA!累死了

嗯我看的懂但我懶的驗算耶=.=

恩，根據資訊大神的想法
這題呢，如果只求最大或最小值，時間複雜度是O(n)
而兩個同時求的話，時間複雜度還是O(n)
(用O表示的話兩個一樣ㄟ，真糟糕，不過他們的係數不一樣喔)

囧
複製的好累!
下次乾脆寫原始碼
用迴圈印 "大的大的..." "小的小的..."
然後用%2之類的迴圈 不就輕鬆秒殺?

話說如果這題題目改大一點  (十萬之類的啊~
囧 不寫了~
囧 逃離數學組 跳槽資訊

公布正確答案吧

簡單來說
先分34組兩兩相比，需34次
各組較重的有34個，之中要選出最重的需33次
各組較輕的有34個，之中要選出最輕的需33次
所以要100次

喔喔這樣說變的好簡單阿~~

定義
在一次的天平側重時
重的一方得到一個B
輕的一方得到一個S

證明
要證明自己是清白的(不是最重也不是最輕)
必須得到一個B一個S
因為題目皆需考慮最差的情況
所以就考慮中間人士(XD)皆得到了BS各一個
而根據最差考慮
最重的至少有一個B(很粗糙的估計，絕對不止一個)
最輕的至少有一個S
中間人士有66個
故判別至少所需資訊量為66*2+1+1=134
一次秤量可得2資訊量(此為考慮一個一個秤，如果一堆一堆秤的話就不一樣的，只是如果這樣秤，就不知道要怎麼秤XDDD)
故秤量數>=134/2=67

重點就是說不定會有少於100的方法喔！
那就找找看吧XDDDD
找到方法則視情況加>=1的名聲

恩
林碩彥將程式碼po上來!!!

其實上面那個估計蠻廢的
但可以經過討論
將中間人士和頭尾的估計加強
就可以得到更好的下界了

恩，愷愷的意思是這題的算法是Ω(n - 1)

不過這題是不是和寒假「找晶片」的問題很像阿...

[ 本帖最後由 esrever 於 2010-2-26 23:34 編輯 ]