Re: [閒聊] 八卦板的「超怪面試問題」

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者SansWord (是妳)時間15年前 (2011/01/07 22:47)推噓1(1推 0噓 1→)

留言2則, 1人參與討論串15/16 (看更多)

: 唔...這個結論似乎有待檢討 : 例如這樣好了: : case 1: case 2: : 正常一個 1g 正常一個 1.2g : 輕的一個 0.8g 輕的一個 0.4g : 四正常 4g 三正常一輕 4g : 二正常一輕 2.8g 兩正常一輕 2.8g : 結果你第一次拿四個硬幣秤得 4g 第二次拿三個硬幣秤得 2.8g : 你不會知道是上面二種 case 的哪一個... : 這個結論只有一種時候是對的那就是兩次上去秤的硬幣沒有重覆 : 我這樣證明試試看: : 第三次秤的結果只會有兩種情形：要嘛有輕幣要嘛沒有輕幣 : 這代表我們必須在前兩次秤時把可能性減少到剩下兩個 : 於是前兩次秤必須要至少有四種可分辨的結果 : 但是無論如何三一律告訴我們 : 前兩次的兩個結果的比值和某數比較只會有三個情形 : (許多類似的運算其實都可以化歸為兩個結果的比值) : 這個比較的基準值只能是在測量前的已知值 : 而這問題中只有這兩次放上去測的硬幣的個數比是這樣的已知值 : 所以不可能有四種可分辨的結果出來因此無解這題其實就是一個 8選1 的選擇題，所以分堆上必須要在3次分堆後展現出8種可能案例。我做到的方法是把硬幣編號1~8後依編號分成三堆 (這樣的分堆是設計後的結果，我的意圖是為了讓 8 個Case在分堆中能區辨) 123 5 12 4 6 1 34 7 這個分法是刻意設計的，若假設一般硬幣重r, 特殊硬幣比一般硬幣輕s 那麼如果4堆都是一般硬幣，那會量到4r 如果其中有一個特殊硬幣，那會量到4r-s 每一次量測都有可能是4r 或 4r-s, 三次量測總共就是8種可能性現在做案例窮舉，若特殊硬幣為1 則會量測到 Case1: 4r-s 4r-s 4r-s 依序列出每個Case: Case1: Case5: 4r-s 4r-s 4r-s 4r 4r-s 4r Case2: Case6: 4r-s 4r 4r-s 4r-s 4r 4r Case3: Case7: 4r-s 4r 4r 4r 4r-s 4r-s Case4: Case8: 4r 4r 4r-s 4r 4r-s 4r 假設無法得知r與s的正確數值，那我只能觀察三次量測彼此的大小關係看似有8個案例，但是Case1 與Case8 其實無法區分所以會導致最後無法肯定答案為1或8, 其他都能肯定。 =============開始想像別種解法==================== 也因此，我知道一口氣量測三次是不智的，如果前兩次重量相等，那麼第三次仍舊量測1 3 4 7 這四個銅板，必定會導致最後無法區辨是1 或8的結果所以我想先按照分堆量測第一、第二次，最後一次若重量相等，就用不同抓法。按照這個案例表，當第一次第二次重量相等時，案例剩下1 2 7 8 四種硬幣而實際推廣上， 1 2 代表的是第一次與第二次的共通硬幣 7 8 代表的是前兩次都沒有抓起的硬幣第三次分堆時，若要取有代表性的硬幣，那只要抓1 2 其中之一，與7 8其中之一即可。然後就回到了我回答的第一篇的狀況，仍舊無法區辨四種狀況。簡單的來說，當第一次第二次的重量相等時以線性代數的角度來說，便是我們喪失了一個限制式本來若有三個限制式，就能推廣出 2^3 的8種狀況。但是喪失了一個限制式(或著說兩個限制式合併)，導致無法推導出最後的狀況。也就很像前一篇您說的，前兩次由於重量相等，導致最後一次量測的三一律只有可能比第一二次大或著等於或小於，也就是只會區辨出3種狀況。導致一定有一個狀況是模糊的。 ================最後的解法========== 若我能上網得知r的正確值，那我量測三次後，若三個都相等那我自然能知道重量為4r或著小於4r 那就能判斷硬幣是1 或 8了。問題是誰說比較重的硬幣一定要所謂的 "法定重量" 呢？若法定重量是10克，那出題者可以給7個9.9克和一個9.8克那不管是1或8我都會誤判成8 不過這樣量測三次後，等於猜錯機率只剩下1/8....也算夠準了吧....(這句話是耍賴) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.193.67.182