PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Counterfeit Coin

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間15年前 (2009/06/08 01:56)推噓0(0推 0噓 0→)

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

※ 引述《meteor1211 (小希)》之銘言： : 想請問有人找的到Counterfeit Coin ... : 推 yauhh:這一題是ACM問題集608:Counterfeit Dollar 06/07 14:48 這個問題,基本上有模擬解題動作的程式. 我的方法是每個硬幣都定一個重量. 但是,如果知道重量了,如果問題的輸入是一堆硬幣的重量,重量都知道了, 程式就要變成一個迴圈,找到惟一重量不同的硬幣即可. 這樣就沒意義了. ACM問題集608則說,是輸入一組稱重的情況,從其中找到偽幣. 例如: ABCD EFGH 是平的, ABCI EFJK 使秤右邊上揚, ABIJ EFGH 是平的. 要從以上六串硬幣代號中,找出惟一不同的那一枚. 很抱歉在它板給的程式,算是沒意義的,除了將硬幣分為三堆的方法之外. ---------------------- 說說 ACM 608號問題的題意: 有一位手上有 12 枚銀幣,其中一枚是假的. 而偽幣的重量比較輕一點. 主角分不出是哪一枚,不過她朋友弄到一座精密秤,只要隨便拿兩枚稱一下,就知道若有上揚的一邊,那一邊就是偽幣. 主角會試著整理稱重順序,稱 3 次把偽幣找出來. (而本程式目的,是模擬人腦判斷稱重結果,找出偽幣的過程. 請問你的偽幣題目題意一樣嗎?) 程式的輸入資料: 先輸入第 1 行是一個數字,代表接下來要給多少組稱重情況. 每組稱重情況分三行輸入,每一行都是先給二組硬幣組成,再給一個描述稱重結果的文字,例如: ABCD EFGH even ABCI EFJK up ABIJ EFGH even 程式的輸出結果: 根據輸入的資訊,找出其中哪一個硬幣是假的. 例如,前例的答案是 K. ------------------------------------------- 接下來是我的解題想法: 這個題目的題意是說,主角如何安排硬幣秤重次序,不干你的事. 你的責任只有接受任何一種秤重次序,從其中做判斷. 所以解決這問題要先想清楚普通的秤重策略,會有規則的決策樹. 硬幣用 A 到 L 12 個字母代表. 決策樹如下: 1. ABCD EFGH 平等 (則將第三組分解代入其他組) 1.1. ABCI EFJK 平等 (則決定答案) -> L 1.2. ABCI EFJK 上揚 (則將 JK 分解代入其他組) 1.2.1. ABIJ EFGH 平等 ... 1.2.2. ABIJ EFGH 上揚 ... 1.2.3. ABIJ EFGH 下降 ... 1.3. ABCI EFJK 下降 ... 2. ABCD EFGH 上楊 (則將第二組分解代入其他組) 2.1. ABCE IJFG 平等 ... 2.2. ABCE IJFG 上揚 ... 2.3. ABCE IJFG 下降 ... 3. ABCD EFGH 下降 (則將第一組分解代入其他組) 3.1. EFGA IJBC 平等 ... 3.2. EFGA IJBC 上揚 ... 3.3. EFGA IJBC 下降 ... 決策樹深度不一. 但慢慢看會找到一些穩定的規則. 解題就是要寫寫那些規則,來做判斷. ------------------------------------- 不過,最簡單的方式是用交集處理. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.71.199 ※ 編輯: yauhh 來自: 61.231.71.199 (06/08 03:24)