作者oodh (oodh)
看板Inference
标题Re: [问题] 金币秤重..
时间Thu Jan 19 21:49:17 2006
※ 引述《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
1F：推 ACGfans:嗯..金币太少的话那个解法就不适用了 01/19 23:09