称假币问题实验报告

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

2、，平衡，而且这三种可能是概率相 等的，所以每一次使用天平的结果都携带iog3的信息量。(2) 要从n个硬币屮找到那个不一样，可以有2n种概率相同的可能，每个硬币都可能偏 轻或者偏重，这个事件所携带的信息量是log2n0所以可以得到最少可以使用log2n/log3次天平就可以凑够信息量，指出哪一个是不一样 的。三、问题解决【问题一】n =1 2设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

3、, 2, 3, 435, 6, 10, 29, 7, 11, 31, 8, 12, 4设3种称重结果分别表示为：0：平衡，1：左重,-1：右重。得到如下鉴别结果:号 称123z £: rnqq 轻称重结果ono-19q10019z1o21q10 o111q11o110q1a oro12zo o110z11 o11z1 oo4zloo12z11013z11o-称重结杲1o1zo11j-1-5a11o8q101-117q11 !16q 称兎结果1-oqo1013q1101-2qljo8z101-1z17z11-1-eo1q1015z1-参见上面表格,可用矩阵表示3次称重的安排，矩阵上面标

4、明12次硬币的序号,矩阵 的3行分别表示3次连续称重时硬币的放置状态，1表示放到左盘，表示放到右盘，0表 示放到旁边(不参与称重)。1234 5 6 7 8910111211111 -11-100001000 1 1 110-1-1-101-10 11-1011-10比较上面的表格和矩阵，发现：如果检测结果与上而矩阵的某列符合，则对应序号的硬币为 假币，且重量较重；如果检杏结果与不包含在上述矩阵的列屮，则1、一 1互换，得到假币 对应序号，但重量较轻。【问题二】n = 3 9查阅资料得到，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,

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

7、编号(2 )称重正序码第一位为0的硬币放在天秤的左侧，笫一位为2的放在右侧，笫一位为1的放在旁边结果与事先挑选的硬币-致五、编写代码#inelude <iostream>#incl ude<algorithm>#in clude<cstri ng>#in clude<cstdio>#in clude<cstdlib>#include<set>using namespace std;set<int > sett;int k,num,n,m;int vsi10005,weight10005,fflag,s2i100

8、05zheavy_or_light;char s100051005,rcd10005;int p=l,integjeicheng二 1;void ten2three(int a,char *s)num=0;for(int i=0;i<k;i+)si=,0,;while(l)snum+=a%3+,0,; a/=3； if(a<=l) snum=a+,o,; break;int judgel(int a)char sss310005;int integ3;ten2three(a,ssso);integ0=atoi(sss0);for(int i=o;i<k;i+)if (ssso

9、i='o,)sssii='r；else jf(sssoi='l,) sssli=,2,;else if(sssoi=,2,) sss i二 o;integl=atoi(sssl);for(int i=0;i<k;i+)if(sssli='o*) sss2i=t;else if(sssli='l')sss2i='2'else if(sssli=,2,) sss2i=o;integ2=atoi(sss 2);int ok=l;for(int i=0;i<=2;i+)if(vsiintegi)ok=0; break;retu

10、rn ok;int judge2(int a)char stst10005;ten 2three(a,stst);int ok=0;for(int i=0;i<k;i+)if(ststi!=ststi+l)if (ststi-'o'=o&&ststi+l-'o'=l) ok=l;else if(ststi-'o'=l&&ststi+l-'0'=2) ok=l;else if(ststi-'o'=2&&ststi+l-'o'=o)ok=l;brea

11、k;return ok;int judge3(int a)char cc10005;ten 2three(a,cc);if(cc0='l')return 1;return 0;int judge4(int a)charcc10005;ten 2three(a,cc);if(cc0='2'&&strlen(cc)=4)return 1;return 0;void bianma()for(int i=l;i<=leicheng;i+) if(judgel(i)&&judge2(i) ten 2three(i,sp); in te

12、g=atoi(sp); sett.insert(i nteg); vsii nteg=l;for(in t j=o;j<k;j+)if(spj=o*) sp+lj=r； else if(spj=*r) sp+lu=,2,;else if(spj='2')sp+lj=,o,; integ=atoi(sp+l); sett.insert(integ);vsii nteg=l;for(int j=o;j<k;j+)if(sp+lj=,o,) sp+2j=,r； else if(sp+lj='l*) sp+2j=2;else if(sp+lj=,2,)sp+2j=,

13、o,;integ=atoi(sp+2); sett.insert(i nteg);vsii nteg=l;p 二 p+3;if(n%3=0&&p>=n)break;else if(n%3=l&&p>=n)for(i nt j=i+l;j<=leiche ng;j+) if(judgel(j)&&judge2(j)&&judge3(j) ten 2three(j,sp); break;else 讦(n%3=2&&p>=n-l)for(i nt j=i+l;j<=leiche ng ;j+

14、)if (judgel(j)&&judge2(j)&&judge4(j) ten 2three(j,sp);for(int jj=o;jj<k;jj+)if(spjj=,o1) sp+luj=，l，；else if(spjj=-r)sp+luj='2,；else if(spjj='2')sp+ljj=o;p+=2;if(p> =n)break;void chengf)int lft10005,rght10005;forfint d=o;d<k;d+)int lnum=0,rnum=0,lsum=0,rsum=0;for(

15、int i=l;i<二n;i+)if(sid=,o,)lftlnu m+二 i; lsum+=weighti;if(sid='2')rghtr nu m+=i; rsum+=weighti;if(lnu m>r num)inum-;isum 二 a/eightlnum;if(lnu m<r num)rn um-;rsum-=weightrsum;printff'h%d 次称量:n“,d+l); printff"左盘放:“)；for(int i=o;i<lnum;i+) cout«lfti«""co

16、ut«endl;printff'右盘放:“)；forfint i=0;i<rnum;i+) cout«rghti«""cout«endl;if(lsum>rsum)rcdd=,0,;else if(lsum=rsum)rcdd='l,;else 讦(lsum<rsum)rcdd='2,;int bidui()for(int i=l;i<=n;i+)s2ii=atoi(si);int rcd2i,ans=o;rcd2i=atoi(rcd);for(int i=l;i<=n;i+)if

17、(rcd2i=s2ii) if(an s=o)heavy_or_light=0; for(int i=o;i<k;i+) if(rcdi=,o,) rcdi=,2,;else if(rcdi='2') rcdi='o'rcd2i=atoi(rcd); for(int i=l;i<二n;i+)if(rcd2i=s2ii)return i;elseheavy_or_light=l; return ans;int main()cout«"输入硬币数量，假币编号，假币重量"«endl; cin»n>> m»fflag;memse