推 ACGfans:嗯..金幣太少的話那個解法就不適用了 01/19 23:09
※ 引述《ACGfans (菜心)》之銘言：
: ※ 引述《chikuo ()》之銘言：
: : 看到這題出個進階
: : 如同上面假設
: : 但有n個袋子裡面裝的是假金幣
: : 要如何找出哪幾個袋子裝假金幣
: : (n = 未知數,有可能只有1個袋子 也有可能全部都是)
: 你是說現在可能不只一袋假金幣嗎?
: 假設總共有m個袋子
: 那這樣就改成
: 1號袋拿1枚，2號袋拿2枚，3號袋拿4枚，4號袋拿8枚，5號袋拿16枚....
: 第m袋2^(m-1)枚
: 這麼一來總共會有2^m-1枚金幣
: 原本應該是(2^m-1)*10克
: 但因為混雜了假金幣 所以實際重量會比較重
: 假設測出來的重為X
: 那就可以得出多的重量為 X-(2^m-1)*10
: 再把這個數改成2進位
: 則從右邊數過來為1的即為假的金幣袋
: EX: 有5個袋子，照上面的拿法共拿31枚金幣
: 原本應為310g 若實際測出來為323g
: 將323-310=13 這是多出來的重
: 轉換成2進位 01101
: 從右邊數過來 54321
: 則編號 1、3、4 即為假金幣袋
是這樣沒錯，簡單的說，就是避免出現某幾袋(相加)和另幾袋一樣的情形
用二進位是最容易的
但在原題目裡，一袋只有十枚，所以... 這樣的問題就沒有辦法解吧??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.246.107