搜索
NUDT 关于称硬币问题的简要分析 ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 曹务绅（200604015014） 刘晓明（200604015015） 2009‐3‐2 关于硬币称重问题的探讨一、问题描述： 假设有N个硬币，这N个硬币中或许存在一个特殊的硬币，这个硬币或轻或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问： 1）至少要称多少次才能达到目的； 2）如果N=12，是否能在3次之内将特殊的硬币找到；如果可以，要怎么称？ 二、问题分析： 对于这个命题，有几处需要注意的地方： 1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知； 2）在目的上，不光要找到这只硬币，还要确定它是重还是轻； 3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡； 4）最多只能称3次； 三、解决方案： i、关于可行性的分析： 在这里，我们把称量的过程看成一种信息的获取过程。对于N个硬币，他们可能的情况为2N+1种，即重（N 种），轻（N种）或者无假币（1种）。由于这2N+1种情况是等概率的，这个事件的不确定度为： ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐(1) 对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。每一次称量只有3种情况：左边重，右边重，平衡。这3种情况也是等概率的，所以他所提供的信息量为： ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐(2) 在K次测量中，要将事件的不确定度完全消除，所以 ‐‐‐‐‐‐‐‐‐‐‐‐‐‐(3) 根据（3）式，当N=12时，K= 2.92 3 所以13只硬币是可以在3次称量中达到目的的。通过此式，我们还可以计算得到：通过3次测量而找出异常硬币，N的最大值为13. Ii、方案的提出 1、一种基于每次测量结果的实际测量方法： 这种方法是大多数人都可以想出来的，即通过利用第一次称重的结果来帮助设计接下来的称重（方案）。在阐明这种方法之前，我们可以从简单问题入手，准备一下5种子情况：通过上一步的计算，我们得知如果只限于3次称重的话，我们最多可以从13个硬币中找到可能存在的那枚异常硬币。为了描述方便，我们给13只硬币分别编号A~L。对于已经确定的真币，我们用0表示，作为一种标准。真币可以通过天平的等重情况获得。1）情况1：3个硬币重于3个硬币，即（A+B+C）（D+E+F），两次称重完成。第一次称重（A+B+D）---（0+0+0）假如左边右边，那么D为异常硬币。假如左边右边，第二次称重为A---B，重者为异常硬币。假如左边=右边，第二次称重为E---F，轻者为异常硬币；如等重，则C为异常硬币。2)情况2：4个硬币重于4个硬币，即（A+B+C+D）（E+F+G+H），两次称重完成。第一次称重（A+B+C+E）---（0+0+0+D）假如左边右边，第二次称重为E---0，不等重，异常硬币为E；否则为D。假如左边右边，第二次称重为A---B，重者为异常硬币；如等重，则C为异常硬币。假如左边=右边，第二次称重为F---G，轻者为异常硬币；如等重，则H为异常硬币。3）情况3：3个硬币（A，B，C），不知道重量，两次称重完成。第一次称重A---0，如不等重，A为异常硬币。第二次称重B---0，如不等重，B为异常硬币；等重，C为异常硬币。4）情况4：4个硬币（A，B，C，D），不知道重量，两次称重完成。第一次称重（A+B）---（0+0），如不等重，第二次称重A---0，如不等重，A为异常硬币；否则B为异常硬币。如等重，第二次称重C---0，如不等重，C为异常硬币；否则D为异常硬币。5）情况5：5个硬币（A，B，C，D，E），不知道重量，两次称重完成。第一次称重（A+B）---（C+0）如左边右边，第二次称重A---B，如不等重，轻者为异常硬币；否则C为异常硬币。如左边右边，第二次称重A---B，如不等重，重者为异常硬币；否则C为异常硬币。如等重，第二次称重D---0，如不等重，D为异常硬币；否则E为异常硬币。了解了以上5种子情况，当硬币总数9-13时，分析如下：1、1.当硬币总数为9枚时。第一次称重（A+B+C）---（D+E+F）剩G、H、I如不等重，套入公式1如等重，套入公式31、2.当硬币总数为10枚时。第一次称重（A+B+C）---（D+E+F）剩G、H、I、J如不等重，套入公式1如等重，套入公式41、3.当硬币总数为11枚时。第一次称重（A+B+C）---（D+E+F）剩G、H、I、J、K如不等重，套入公式1如等重，套入公式51、4.当硬币总数为12枚时。第一次称重（A+B+C+D）---（E+F+G+H）剩I、J、K、L如不等重，套入公式2如等重，套入公式41、5.当硬币总数为13枚时。第一次称重（A+B+C+D）---（E+F+G+H）剩I、J、K、L、M如不等重，套入公式2如等重，套入公式52、基于信息论和通信理论的方法（Information-TheoryandCommunication-Theory）对于这个问题，我们想知道一个相对应的算法。那就是说，在任何的称重结果出来之前，必须预先决定在3次称重中哪些硬币要称。让我们把这个天平当成是一种通信信道。那就是，假设它试着传输给你一组编码告诉你这个谜题的结果。这个信道只有3种符号（L，B和R）来分别表示左盘重，平衡，和右盘重。信道可以提供一组包含3个这样符号的编码。所以整个任务简化成这样：运用这27（）中可能的子集，我们想映射每个编码和硬币。编码和硬币必须是一一对应的。对于这27个编码，我们很容易就可以制定出这样的一个表格：RRRRRBRRLRBRRBBRBLRLRRLB131211109876RLLBRRBRBBRLBBRBBBBBLBLR543210-1-2BLBBLLLRRLRBLRLLBRLBBLBL-3-4-5-6-7-8-9-10LLRLLBLLL-11-12-13现在，假如你得到一个这样的编码，比如方说是RRB，然后贴在其中一个硬币上。你可以从2个方面思考这个编码：•这个编码告诉了你怎样称重的规则：那个RRB硬币是在第一次称重的右边，第二次称重也是在右边，然后第三次它在边上，没有参与称重。•这个编码告诉你怎样解释天平的语言：如果第一次称重是右盘重了，第二次还是右盘重了，第三次平衡，那么标记了RRB的假币比其他硬币要重。现在再看如果标记了RRB的硬币比真币轻会是什么情况。那样天平会告诉你LLB，那就是左边，左边，平衡。从这个结果我们可以得出结论如果我们标记一个硬币RRB，我们不能标记其他的硬币LLB。更一般的情况，我们每次用到表中的编码时，我们必须毁掉它的镜像编码。此外，这里有另一个限制：天平只能处理两个盘子放相同数量的硬币的情况。所以我们必须选择一组具有每一列的R的数目等于L的性质的编码集合。我们直接忽略掉BBB的编码，因为这个编码不适合标记在任何硬币上。在这些称重中你永远也找不到这样的硬币。现在取表1的上半部编码（编号1-13）作为一个试探性的编码集合。我们需要忽略一个，因为我们只需要12个。很明显的选择是忽略RRR，因为这样做我们可以在剩下的集合中创造出偶数个R和L。最后我们把4个编码和他们的镜像编码交换。我们需要做一些镜像的工作，因为表 1 这个实验性的集合以太多的R（在第一列）为初始状态了，我们需要把他们中的4个换成L。改变12，11，9和7满足要求。结果是：LLBLLRRBRLBBRLBLRLRLBRLLBRRBRB-12-1110-98-76543BRLBBR21仔细观看上表，我们会发现如下几个性质：•有12行3列•每一列只有4个R，4个L，和4个B•每个表中的编码，他们的镜像编码并没有出现如果编码BBB的产生表示目前没有假币。当确定存在假币的时候，利用以上编码的表格，就可以很好的找到到底是那个硬币是假币，可以根据编码的前两个状态来判断到底是轻还是重。四、方案分析：对于方案一，思路清晰，原理简单，是比较大众的一种方法，基于的理论基础很有限，每次的测量都必须利用上一步的结果。而且在实际操作过程中很麻烦。对于方案二，它综合利用了信息论和通信系统的分析方法，将成硬币的过程看成一种通信模型，利用信道编码的原理进行分析，思考的过程较复杂，但是论证严密，实际称量也变的简单，这就是理论知识的魅力，就是理论用于实际而产生的便捷。五、参考文献：【1】JohnR.Pierce,“Symbols,Signals,andNoise“【2】JohnDenker“Forageneraldiscussionofwhatentropyis,thermo-laws.entropy”老师点评：这是讨论最深入的一组，得出了两种方案，并进行了比较与分析，反映学生们对此项目兴趣浓厚。表 2