称假币问题实验报告

称假币问题实验报告——信息论第一次作业学校：西安电子科技大学班别：1307011班姓名：黄丹丹学号：13070110009１３０７０１１０００９黄丹丹信息论第一次作业1一、问题重述盒中有n个外形相同的硬币，知道其中有一个重量不同的硬币，但不知是比真币轻，还是比真币重。现用一无砝码天枰对现有硬币进行称重来鉴别假币，无砝码天枰的称重有3种结果，平衡，向左倾，向右倾。当n=12;n=39;n=n时，如何称重使实验次数最少，鉴别出假币并判断出轻或重？二、问题分析根据熵的可加性，一个复合事件的平均不确定性可以通过多次试验逐步解除。如果我们使实验所获得的信息量最大，那么所需要的总试验次数就最少。（1）每一次使用天平，可以得到三种可能，左偏，右偏，平衡，而且这三种可能是概率相等的，所以每一次使用天平的结果都携带log3的信息量。（2）要从N个硬币中找到那个不一样，可以有2N种概率相同的可能，每个硬币都可能偏轻或者偏重，这个事件所携带的信息量是log2N。所以可以得到最少可以使用log2N/log3次天平就可以凑够信息量，指出哪一个是不一样的。三、问题解决【问题一】ｎ＝１２设12个硬币的编号分别为：1，2，3，4，5，6，7，8，9，10，11，12.三次称重安排如下表：称重序号左盘右盘其他11，2，3，45，6，7，89，10，11，1221，6，7，85，10，11，129，2，3，435，6，10，29，7，11，31，8，12，4１３０７０１１０００９黄丹丹信息论第一次作业2设3种称重结果分别表示为：0：平衡，1：左重，-1：右重。得到如下鉴别结果：参见上面表格，可用矩阵表示3次称重的安排，矩阵上面标明12次硬币的序号，矩阵00-1Q321-1011-10000-11ZZQ49—1212111100101101-10-1011010-11010-1-10-1110011011____Q678501-1-1-1QZ____51768234-11-1称重序号123称重鉴别结果假币编号轻：Q重：Z修正编号称重结果01000-10-11—9-1-1-11111101-1-11-11-100-101-1-10Q0ZZZZZZQQ1010010称重结果-1-1QQQ称重结果-111-1QQZZZ-1-11-111-110-10-1１３０７０１１０００９黄丹丹信息论第一次作业3的3行分别表示3次连续称重时硬币的放置状态，1表示放到左盘，-1表示放到右盘，0表示放到旁边（不参与称重）。1234567891011121111-1-1-1-100001000-11110-1-1-101-1011-10-11-10比较上面的表格和矩阵，发现：如果检测结果与上面矩阵的某列符合，则对应序号的硬币为假币，且重量较重；如果检查结果与不包含在上述矩阵的列中，则１、－１互换，得到假币对应序号，但重量较轻。【问题二】ｎ＝３９查阅资料得到，n次称量最多可以在个球中找到不同的球，并判断它的轻重。（1）编码：知道了球数，就能算出需要称量几次；以这个次数作为长度，使用0、1、2排列组合进行编码，如001021、212022等等，再去掉全0、全1和全2，可知一共有个编码；如果在一个编码中，第一处相邻数字不同的情况是01、12或20，则我们称它为正序码，如1120021；否则为逆序码，如2221012；在长度为n的编码中，正序码和逆序码的数量相等，均为个。（2）赋值：如果把一个正序码中的0换成1，1换成2，2换成0，则它仍然是正序码；根据这个原理，我们把所有正序码按3个3个进行分组，如12001、20112、01220这3个就是一组；把正序码一组一组地分配给小球，每球一个，直到分完；然后把每个正序码的0换成2，2换成0，它就变成了一个逆序码，如12001变成10221；这样，每个小球就有了两个编码，一个正序，一个逆序，而且所有球都不重复。（3）称重：第一轮，我们把所有正序码第一位为0的小球放在天平左侧，为2的小球放在右侧，其它的放在旁边；如果天平左倾，记为0；右倾，记为2；平衡，记为1；然后是第二轮，把第二位为0的小球放在左侧，为2的放在右侧，同样记下称量结果；每一轮都按这个顺序进行，一共要称n次，最终结果是个n位的编码；如果编码等于某个小球的正序码，则这个小球比其它球重；如果编码等于某个小球的逆序码，则这个小球比其它球轻。【问题三】ｎ＝ｎ方法与问题二同１３０７０１１０００９黄丹丹信息论第一次作业4四、算法演示以ｎ＝１２为例（１）编号（２）称重正序码第一位为０的硬币放在天枰的左侧，第一位为２的放在右侧，第一位为１的放在旁边１３０７０１１０００９黄丹丹信息论第一次作业5１３０７０１１０００９黄丹丹信息论第一次作业6结果与事先挑选的硬币一致五、编写代码#includeiostream#includealgorithm#includecstring#includecstdio#includecstdlib#includesetusingnamespacestd;setintsett;intk,num,n,m;intvsi[10005],weight[10005],fflag,s2i[10005],heavy_or_light;chars[10005][1005],rcd[10005];intp=1,integ,leicheng=1;voidten2three(inta,char*s){num=0;for(inti=0;ik;i++)s[i]='0';while(1){s[num++]=a%3+'0';a/=3;if(a=1)１３０７０１１０００９黄丹丹信息论第一次作业7{s[num]=a+'0';break;}}}intjudge1(inta){charsss[3][10005];intinteg[3];ten2three(a,sss[0]);integ[0]=atoi(sss[0]);for(inti=0;ik;i++){if(sss[0][i]=='0')sss[1][i]='1';elseif(sss[0][i]=='1')sss[1][i]='2';elseif(sss[0][i]=='2')sss[1][i]='0';}integ[1]=atoi(sss[1]);for(inti=0;ik;i++){if(sss[1][i]=='0')sss[2][i]='1';elseif(sss[1][i]=='1')sss[2][i]='2';elseif(sss[1][i]=='2')sss[2][i]='0';}integ[2]=atoi(sss[2]);intok=1;for(inti=0;i=2;i++)if(vsi[integ[i]]){ok=0;break;}１３０７０１１０００９黄丹丹信息论第一次作业8returnok;}intjudge2(inta){charstst[10005];ten2three(a,stst);intok=0;for(inti=0;ik;i++){if(stst[i]!=stst[i+1]){if(stst[i]-'0'==0&&stst[i+1]-'0'==1)ok=1;elseif(stst[i]-'0'==1&&stst[i+1]-'0'==2)ok=1;elseif(stst[i]-'0'==2&&stst[i+1]-'0'==0)ok=1;break;}}returnok;}intjudge3(inta){charcc[10005];ten2three(a,cc);if(cc[0]=='1')return1;return0;}intjudge4(inta){charcc[10005];ten2three(a,cc);if(cc[0]=='2'&&strlen(cc)==4)return1;return0;}voidbianma(){for(inti=1;i=leicheng;i++)１３０７０１１０００９黄丹丹信息论第一次作业9{if(judge1(i)&&judge2(i)){ten2three(i,s[p]);integ=atoi(s[p]);sett.insert(integ);vsi[integ]=1;for(intj=0;jk;j++){if(s[p][j]=='0')s[p+1][j]='1';elseif(s[p][j]=='1')s[p+1][j]='2';elseif(s[p][j]=='2')s[p+1][j]='0';}integ=atoi(s[p+1]);sett.insert(integ);vsi[integ]=1;for(intj=0;jk;j++){if(s[p+1][j]=='0')s[p+2][j]='1';elseif(s[p+1][j]=='1')s[p+2][j]='2';elseif(s[p+1][j]=='2')s[p+2][j]='0';}integ=atoi(s[p+2]);sett.insert(integ);vsi[integ]=1;p=p+3;}if(n%3==0&&p=n)break;elseif(n%3==1&&p=n){for(intj=i+1;j=leicheng;j++){１３０７０１１０００９黄丹丹信息论第一次作业10if(judge1(j)&&judge2(j)&&judge3(j)){ten2three(j,s[p]);break;}}}elseif(n%3==2&&p=n-1){for(intj=i+1;j=leicheng;j++){if(judge1(j)&&judge2(j)&&judge4(j)){ten2three(j,s[p]);for(intjj=0;jjk;jj++){if(s[p][jj]=='0')s[p+1][jj]='1';elseif(s[p][jj]=='1')s[p+1][jj]='2';elseif(s[p][jj]=='2')s[p+1][jj]='0';}}}p+=2;}if(p=n)break;}}voidcheng(){intlft[10005],rght[10005];for(intd=0;dk;d++){intlnum=0,rnum=0,lsum=0,rsum=0;for(inti=1;i=n;i++){１３０７０１１０００９黄丹丹信息论第一次作业11if(s[i][d]=='0'){lft[lnum++]=i;lsum+=weight[i];}if(s[i][d]=='2'){rght[rnum++]=i;rsum+=weight[i];}}if(lnumrnum){lnum--;lsum-=weight[lnum];}if(lnumrnum){rnum--;rsum-=weight[rsum];}printf(第%d次称量：\n,d+1);printf(左盘放:);for(inti=0;ilnum;i++)coutlft[i];coutendl;printf(右盘放:);for(inti=0;irnum;i++)coutrght[i];coutendl;if(lsumrsum)rcd[d]='0';elseif(lsum==rsum)rcd[d]='1';elseif(lsumrsum)rcd[d]='2';}１３０７０１１０００９黄丹丹信息论第一次作业12}intbidui(){for(inti=1;i=n;i++){s2i[i]=atoi(s[i]);}intrcd2i,ans=0;rcd2i=atoi(rcd);for(inti=1;i=n;i++)if(rcd2i==s2i[i]){ans=i;break;}if(ans==0){heavy_or_light=0;for(inti=0;ik;i++){if(rcd[i]=='0')rcd[i]='2';elseif(rcd