※ 引述《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)