称假币问题实验报告

《称假币问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、称假币问题实验报告信息论第一次作业学校：西安电子科技大学班别：1307011班姓名：黄丹丹学号：13070110009一、问题重述盒中有n个外形相同的硬币，知道其中有一个重量不同的硬币，但不知是比真币轻，还是比真币重。现用一无磁码天杆对现有硕币进行称重来鉴别假币，无舷码天桦的称重有3种结果,平衡，向左倾，向右倾。当n=12;n=39;n=n时，如何称重使实验次数最少，鉴别出假币并判断出轻或重？二、问题分析根据爛的可加性，一个复合事件的平均不确定性可以通过多次试验逐步解除。如果我们使实验所获得的信息量最大，那么所需要的总试验次数就最少。(1)每一次使用天平，可以得到三种可

2、能,左偏，右偏，平衡，而且这三种可能是概率相等的，所以每一次使用天平的结果都携带Iog3的信息量。(2)要从N个硬币屮找到那个不一样，可以有2N种概率相同的可能，每个硬币都可能偏轻或者偏重，这个事件所携带的信息量是log2N0所以可以得到最少可以使用log2N/log3次天平就可以凑够信息量，指出哪一个是不一样的。三、问题解决【问题一】n=12设12个硬币的编号分别为:1,2,3,4,5,6,7,8,9,10,11,12.三次称重安排如下表：称重序号左盘右盘其他11,2,3,45,6,7,89,10,11,1226,7,85,10,11,129,2,3,435,6,10

3、,29,7,11,31,8,12,4设3种称重结果分别表示为：0：平衡，1：左重,-1：右重。得到如下鉴别结果:□号称123z£:rnqQ••轻称重结果Ono-19Q10019z1□o21Q10o111Q11o110Q1Aoro12zo■o110z11■o11z1■■o□□o4zloo12z1101■3z11O-称重结杲1o1zo11J--1-5a1■1□o8Q101-117Q11■!•16Q■■称兎结果1-oQo10■13Q110■1-2QLJo8z101-1z1■7z1■1-1-Eo1Q10■■15z1---参见上面表格,可用矩阵表示3次称重的安排，矩阵上面标明12

4、次硬币的序号,矩阵的3行分别表示3次连续称重时硬币的放置状态，1表示放到左盘，表示放到右盘，0表示放到旁边(不参与称重)。1234567891011121111・1-1・1-100001000・11110-1-1-101-1011-10■11-10比较上面的表格和矩阵，发现：如果检测结果与上而矩阵的某列符合，则对应序号的硬币为假币，且重量较重；如果检杏结果与不包含在上述矩阵的列屮，则1、一1互换，得到假币对应序号，但重量较轻。【问题二】n=39查阅资料得到，n次称量最多可以在2个球中找到不同的球，并判断它的轻重。(1)编码：知道了球数，就能算出需要称量几次；以这个次数作

5、为长度，使用0、1、2排列组合进行编码，如001021、212022等等，再去掉全0、全1和全2,可知一共有3・一3个编码；如果在一个编码屮，第一处相邻数字不同的情况是01、12或20,则我们称它为正序码，如1120021；否则为逆序码,如2221012；在长度为n的编码中，正序码和逆序码的数量相等，均为2个。(2)赋值：如果把一个正序码中的0换成1,1换成2,2换成0,则它仍然是正序码；根据这个原理，我们把所有正序码按3个3个进行分组，如12001、20112、01220这3个就是一组；把正序码一组一组地分配给小球，每球一个，直到分完；然示把每个正序码的0换成2,2换

6、成0,它就变成了一个逆序码，如12001变成10221；这样，每个小球就冇了两个编码，一个正序，一个逆序，而且所有球都不重复。(3)称重：笫一轮，我们把所有正序码笫一位为0的小球放在天平左侧，为2的小球放在右侧，其它的放在旁边；如果天平左倾，记为0；右倾，记为2；平衡，记为1；然后是第二轮，把第二位为0的小球放在左侧，为2的放在右侧，同样记下称虽结果；每一轮都按这个顺序进行，一共耍称n次，最终结果是个n位的编码；如果编码等于某个小球的正序码，则这个小球比其它球重；如果编码等于某个小球的逆序码，则这个小球比具它球轻。【问题三】n=n方法少问题二同四、算法演示以n=12为例

7、(1)编号(2)称重正序码第一位为0的硬币放在天秤的左侧，笫一位为2的放在右侧，笫一位为1的放在旁边结果与事先挑选的硬币-•致五、编写代码#inelude#include#include#include#include#includeusingnamespacestd;setsett;intk,num,n,m;intvsi[10005],weight[10005],fflag,s2i[10005]zheavy_or_light