一架天平，只能稱重三次，如何從12枚金幣中找到1枚假的？
01-22
1. 取8枚幣 （a b c d e f g h )，一邊4個 (a b c d e f g h )。稱一下。如果平，那麼有問題的在剩下的4枚 (1 2 3 4)。如果不平，問題在這8枚。
已知a b c d e f g h 沒問題，2次區分1 2 3 4，比較容易了。
ab 和12稱。如果平，有問題的是34，不平，有問題的是12。假設有問題的是34（1，2完全一樣），3和a稱，平，有問題的是4，不平，有問題的是3。
2. 以下假設 a b c d 低 e f g h 高 （換過來是對稱的，不複述）。
3. 第二次：稱 a 1 2 3 和 b c d h
3.1 如果平，則a 1 2 3 b c d h沒問題，4也沒問題。有問題的是 e f g，並確定有問題的高（比較輕）。 剩下一次很容易了。e和f稱，看誰輕，輕的有問題，平則g有問題。
3.2 如果 a 1 2 3低， b c d h 高，則有問題的一定是a 或者 h。因為如果b c d 有問題，則 b c d h 一定低。 剩下一次區分a 和h也很容易了，不複述。
3.3 如果a 1 2 3高， b c d h 低，則有問題的，一定是 b c d。 並確認有問題的會低（比較重）。剩下一次也很容易了。不複述。這不就是資訊理論這門課上的作業嗎。。。天平一次能稱出3種可能，左沉、右沉、平衡，因此，稱一次獲得的信息量是以2為底3的對數，稱3次的信息量就是3倍的（以2為底3的對數）=以2為底27的對數再說金幣，知道哪個金幣是假的，獲得信息量為以2為底12的對數；考慮假金幣是偏輕還是偏重，兩種可能，乘2，信息量為以2為底24的對數.綜上，從天平獲得的信息量大於找假金幣所需的信息量，所以一定是有辦法找出來的。至於是什麼辦法，還沒想到。。。-------------------------------------------------------------------------------------------------------------------------------------百度到了一些方法，大家看看吧。。。
12球稱重問題, 演算法及其他
數學分析: 經典的12球稱重！13球也可以滴！
代碼實現: 12個小球稱重量問題(C代碼)
第一：有12個外觀完全一樣的球；
第二：11個是好球，重量相同； 第三：有一個球是「壞球」，重量與其他11個球異常，但不知偏輕偏重！ 第四：有一架天平，無砝碼； 問：怎樣用該天平稱量3次，找出重量異常的球！============================================================================
先論證可行性:
再來看看牛人的解答吧，從另一個角度看東東，特別牛！！！
從資訊理論來看，12個球一個重量異常，出現概率1/12；該球質量可能輕也可能重，那麼出現概率為1/2。 那麼要得到結果所需信息量為log2+log12。 稱一次可能有輕、重、相等三種結果，信息量為log3。log24/log3&<3，三次應該能稱出來。 資訊理論運用到這種地步，實在是精闢啊。（說實話，本人只看得懂一部分，資訊理論好強。）
（參見 David J.C. MacKay 的「Information Theory, Inference, and Learning Algorithms」） 首先考察一個這個題目的性質。 要求從12個球中找出一個次品球來可以歸結為一種態空間的搜索。 12個球可以具有很多狀態，例如第一個球是重球，而其它球是正常球，
或者第三球是輕球，而其它球是正常球。 12個球，每個球都可能是重球或者輕球，所以共有24個可能的狀態。 標記為1+, 1-, 2+, ..., 12+, 12-。 注意這裡我們已經省略了對正常球的描述，而認為它們是一種背景情況。 我們的任務是確定12個球到底處在這24種狀態的哪一個。 再來看看我們所具有的搜索手段。 我們只有一架天平，可以將其看作一種指標函數， 其輸出有三種：左重右輕，左輕右重，平衡。所以一次稱量我們可以在態空間中進行一次三分操作，
而將搜索空間縮小到態空間中的某一部分。 考慮到最壞的情況，每次我們都可能落入較大的搜索空間， 所以應該盡量進行三等分。 舉個例子, □□□□□□X□□□□□□□□□□Y□□□□□□□□□□Z □□□□1+ 2+ 3+ 4+□□□□5+ 6+ 7+ 8+ □□□□9+ 10+ 11+ 12+ □□□□1- 2- 3- 4-□□□□5- 6- 7- 8- □□□□9- 10- 11- 12- 如果我們稱量X和Y, 如果平衡，則次品球必在Z中。如果 X &> Y，則我們可以排除X中的1-,2-,3-,4-以及Y中的5+,6+,7+,8+等狀態。
無論如何，最終只會剩下8個待選狀態。 最後明確一下我們在繼續稱量的過程中需要注意的問題：如何才能最大限度的獲取信息。 假設 X &> Y, 則剩下1+ 2+ 3+ 4+ 5- 6- 7- 8-這8個狀態。 繼續稱量必須將這8個狀態打亂放置到天平兩側，而且要注意到盡量均衡。 比如說我們現在選擇稱量1+和5-。 顯然，現在的結果只能是左重右輕或者平衡，因為根據我們的知識可以排除左輕右重的情況。 而如果比較1+和2+，我們仍然可以得到三種情況。 只有在先驗上我們認為兩者絕對無法區分的情況下，比較才具有最大的意義。 具體如何稱量下去，這裡不講了。只是強調一點，信息是我們意料之外的事情，這是資訊理論的要點。最後，說一下如何稱13個球吧。不過，只能找出來，不能保證知道壞球是輕是重。
還是分三組，A、B、C，C組5個球（C1,C2,C3,C4,C5） 第一次，還是稱量 A :::: B；如果不相等，嘿嘿，和稱12個球完全一樣了！ 如果 A == B，都是好球，C中有「壞球」； 很簡單， 第二次，（A1,A2,A3）::::（C1,C2,C3）稱量； 如果，==，（C4,C5）有「壞球」，隨便哪一個與A1稱即可； 如果，&>，（C1,C2,C3）中有「壞球」，且壞球輕，再C1和C2稱，即可； 如果，&<，（C1,C2,C3）中有「壞球」，且壞球重，再C1和C2稱，即可；最後，對資訊理論的一點兒補充，權當給各位參考：
1）13球問題, 一共有26種可能的情況；
2）天平一次稱量結果有3種情況(左偏,平衡,右偏), 3次稱量最多有3^3=27種情況。 這說明3次確定出這26種情況是「有可能」的！=============================================================================
答案很多種，也都很精彩！
正確的都是分成三組：A(A1,A2,A3,A4)、B(B1,B2,B3,B4)、C(C1,C2,C3,C4) 如果不分三組，嘿嘿，那肯定不對！第一種方法：（分三組，A、B、C，各四個球）
(1)第一次：A :::: B，兩組稱量；如果，A == B，A、B 組是好球，C 組（C1,C2,C3,C4）中有「壞球」；
(2)----第二次：（A1,A2）::::（C1,C2），稱量； (這裡只用了兩個球稱量!!!! ) ----如果，（A1,A2）==（C1,C2），說明（C3,C4）中有「壞球」； --------第三次：A1 :::: C3，稱量； --------如果，A1 == C3，說明 C3 是好球，結論是：C4 是「壞球」； --------如果，A1 != C3，說明 C4 是好球，結論是：C3 是「壞球」； ----如果，（A1,A2）!=（C1,C2），說明（C1,C2）中有「壞球」； --------第三次：A1 :::: C1，稱量； --------如果，A1 == C1，說明 C1 是好球，結論是：C2 是「壞球」； --------如果，A1 != C1，說明 C2 是好球，結論是：C1 是「壞球」； (3)如果，A != B，肯定 C 組是好球， ----有兩種情況：（左）A &> B（右）（A重），或 A &< B（A輕）； ----以「A &> B（A重，左 &> 右）」為例，進行操作； ----第二次：天平左側，A 組留1個球，與 B 組3個球配成一組； ---- 天平右側，B 組還剩1個球，與 C 組3個球配成一組； ---- 即：（A1,B1,B2,B3）::::（B4,C1,C2,C3），稱量； ----此時，將出現三種情況，左 == 右，左 &> 右，左 &< 右； ----如果，左 == 右，那麼，問題球肯定在（A2,A3,A4）中， ---------------- 且因為（A重）為例，說明「壞球」是重的； --------第三次：A2 :::: A3，稱量； --------如果，A2 = A3，都是好球，結論是：A4 是「壞球」； --------如果，A2 &> A3，結論是：A2 是「壞球」，且重； --------如果，A2 &< A3，結論是：A3 是「壞球」，且重； ----如果，左 &> 右，（B1,B2,B3）移動後，未引起變化，是好球， ---------------- 問題球就是（A1,B4），要麼A1重，要麼B4輕； --------第三次：C1 :::: A1，稱量； --------如果，C1 = A1，都是好球，結論是：B4 是「壞球」，且輕； --------如果，C1 &< A1，結論是：A1 是「壞球」，且重； ----如果，左 &< 右，說明（B1,B2,B3）移位後，引起變化，有壞球， ---------------- 問題球在（B1,B2,B3）中，且「壞球」較輕； --------第三次：B1 :::: B2，稱量； --------如果，B1 = B2，都是好球，結論是：B3 是「壞球」，且輕； --------如果，C1 &< A1，結論是：A1 是「壞球」，且重；==========================================================================
其實，這道題的解法還有多種，
分別是對「第一種方法」中的(2)、(3)進行變化。 先說簡單的：(2)的變化 前提是：第一次稱量，A == B； 變化一 第二次稱量：（A1,A2,A3）::::（C1,C2,C3）； 如果，==，那麼，C4是「壞球」，想知輕重，與 A1 稱一下即可； 如果，&>，那麼，（C1,C2,C3）中有壞球，壞球為輕； --------第三次稱量，C1 :::: C2， --------如平衡，C3是「壞球」，不平衡，輕的是「壞球」； 如果，&<，那麼，（C1,C2,C3）中有壞球，壞球為重； --------第三次稱量，C1 :::: C2， --------如平衡，C3是「壞球」，不平衡，重的是「壞球」； 變化二 第二次稱量：（A1,C1）::::（C2,C3）； 如果，==，那麼，C4是「壞球」，想知輕重，與 A1 稱一下即可； 如果，&>，那麼，（C1,C2,C3）中有壞球，要麼C1重，要麼C2或C3輕； --------第三次稱量，C2 :::: C3， --------如平衡，C1是「壞球」，且重；不平衡，輕的是「壞球」； 如果，&<，那麼，（C1,C2,C3）中有壞球，要麼C1輕，要麼C2或C3重； --------第三次稱量，C2 :::: C3， --------如平衡，C1是「壞球」，不平衡，重的是「壞球」； 補充說明：這兩種變化，比之前的要好，可以知道「壞球」的輕重！ 第一種方法中的(2)， 有可能三次稱量後，只能判斷哪個是「壞球」，卻不知是輕是重！
幾年前閑的蛋疼的時候曾經畫過流程圖
就把我在百度文庫上寫的答案再搬過來吧。ps:題主要求的是12枚金幣，這裡用12個球代替。其實都一樣，外觀上無法分辨就好。pps:這是我在知乎上回答的第一個問題（好緊張）題目：有12個外觀一樣的球，有且僅有一個是壞球，但是不知道壞球是比好球輕還是重，利用天平最多稱重三次找出這個壞球，並指出是比好球輕還是重。 推理：將12球分成ABC三組，每組4個，隨機選兩組進行稱重 A and B，此時有三種情況 1. A=B，則壞球在C組中。此時C1C2 and C3A1，有三種情況 1.1 C1C2&> C3A1 則C1C2重或C3輕，此時C1 and C2，有三種情況 1.1.1 C1&>C2，則C1是壞球，且壞球重於好球 1.1.2 C1&
鏈接: https://pan.baidu.com/s/1pLa9VQF 密碼: t8bm 一個安卓的模擬稱硬幣的APP，直接下載安裝就可以用。歡迎試用，不足之處，請多指正。
第一次，取六個三三稱假設平衡那麼這六個是真的。 第二步步要用不平衡的六個。關鍵是第二步，再用原本的左右三三稱重。左右的硬幣不能動。肯定會有不平衡所以三三不需要稱，在這次還沒稱重時兩邊個去掉一個，同時左右各互換一枚硬幣。如果剩下的這四個ab+cd保持平衡，則說明去掉的兩枚中有一枚是假的。如果天平保持原本的高低，也就是說明天平中沒有互換的那兩枚硬幣有一枚是假的。如果天平的高低改變，那麼互換的兩枚硬幣中有一枚是假的。將判定為假的兩枚硬幣任取一枚，拿其它真的真的和他稱重，如果平衡則剩餘的一枚為假，如果保持不平衡，則稱的那枚為假。
假設假的輕。分成3份（4個一份），第一次取其中兩份稱，如果平衡則假的在沒稱的那份，如果不平衡，取出輕的那份，這次已判斷出假幣所在的位置。第二次把已知假的那份在分成2份（2個一份）稱一下，可判斷假幣所在位置第三次只剩2個幣了，稱了就知道了。
推薦閱讀：
※面試問題，是選擇在女友生日時陪女友看電影還是先完成領導交代的任務？
※假如你是面試官，面試時，你希望面試者問你哪些問題？
※UI設計師如何準備面試作品？
※有誰知道武漢鼎業環保工程技術有限公司怎麼樣？
※面試完了你是怎麼和人事砍價？
TAG:面試問題 |