称假币问题实验报告

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

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

3、4设3种称重结果分别表示为：0：平衡，1：左重，-1：右重。得到如下鉴别结果：称重鉴别结果称重序号0231轻：Q重：Z假币编号修正编号称重结果0-1-1-1-1-1111110000010Z1ZZZZZZZQQQQ3249912121111101000100-101001101-10-1011010-11010-1-10-11100称重结果11-1-10-111_QQQQ67851-1-11-111-1011-1称重结果00-1111-1-1-100-11QQQQZZZZ_51768234-1-11-1-10-11-1-111-110-100-101-10-1参见上面表格，可用矩阵表示3次称重

4、的安排，矩阵上面标明12次硬币的序号，矩阵的3行分别表示3次连续称重时硬币的放置状态，1表示放到左盘，-1表示放到右盘，0表示放到旁边（不参与称重）。比较上面的表格和矩阵，发现：如果检测结果与上面矩阵的某列符合，则对应序号的硬币为假币，且重量较重；如果检查结果与不包含在上述矩阵的列中，则、互换，得到假币对应序号，但重量较轻。【问题二】查阅资料得到，n次称量最多可以在个球中找到不同的球，并判断它的轻重。 （1）编码：知道了球数，就能算出需要称量几次；以这个次数作为长度，使用0、1、2排列组合进行编码，如、等等，再去掉全0、全1和全2，可知一共有个编码；如果在一个编码中，第一处相邻数字不

5、同的情况是01、12或20，则我们称它为正序码，如；否则为逆序码，如；在长度为n的编码中，正序码和逆序码的数量相等，均为个。（2）赋值：如果把一个正序码中的0换成1，1换成2，2换成0，则它仍然是正序码；根据这个原理，我们把所有正序码按3个3个进行分组，如12001、20112、01220这3个就是一组；把正序码一组一组地分配给小球，每球一个，直到分完；然后把每个正序码的0换成2，2换成0，它就变成了一个逆序码，如12001变成10221；这样，每个小球就有了两个编码，一个正序，一个逆序，而且所有球都不重复。（3）称重：第一轮，我们把所有正序码第一位为0的小球放在天平左侧，为2的小球放在右侧，

6、其它的放在旁边；如果天平左倾，记为0；右倾，记为2；平衡，记为1；然后是第二轮，把第二位为0的小球放在左侧，为2的放在右侧，同样记下称量结果；每一轮都按这个顺序进行，一共要称n次，最终结果是个n位的编码；如果编码等于某个小球的正序码，则这个小球比其它球重；如果编码等于某个小球的逆序码，则这个小球比其它球轻。【问题三】方法与问题二同4、 算法演示以为例（）编号（） 称重正序码第一位为的硬币放在天枰的左侧，第一位为的放在右侧，第一位为的放在旁边结果与事先挑选的硬币一致五、编写代码#include <iostream>#include<algorithm>#include&l

7、t;cstring>#include<cstdio>#include<cstdlib>#include<set>using namespace std;set<int > sett;int k,num,n,m;int vsi10005,weight10005,fflag,s2i10005,heavy_or_light;char s100051005,rcd10005;int p=1,integ,leicheng=1;void ten2three(int a,char *s) num=0; for(int i=0;i<k;i+) si=

8、'0' while(1) snum+=a%3+'0' a/=3; if(a<=1) snum=a+'0' break; int judge1(int a) char sss310005; int integ3; ten2three(a,sss0); integ0=atoi(sss0); for(int i=0;i<k;i+) if(sss0i='0') sss1i='1' else if(sss0i='1') sss1i='2' else if(sss0i='2&

9、#39;) sss1i='0' integ1=atoi(sss1); for(int i=0;i<k;i+) if(sss1i='0') sss2i='1' else if(sss1i='1') sss2i='2' else if(sss1i='2') sss2i='0' integ2=atoi(sss2); int ok=1; for(int i=0;i<=2;i+) if(vsiintegi) ok=0; break; return ok; int judge2(in

10、t a) char stst10005; ten2three(a,stst); int ok=0; for(int i=0;i<k;i+) if(ststi!=ststi+1) if(ststi-'0'=0&&ststi+1-'0'=1) ok=1; else if(ststi-'0'=1&&ststi+1-'0'=2) ok=1; else if(ststi-'0'=2&&ststi+1-'0'=0) ok=1; break; return o

11、k; int judge3(int a) char cc10005; ten2three(a,cc); if(cc0='1') return 1; return 0; int judge4(int a) char cc10005; ten2three(a,cc); if(cc0='2'&&strlen(cc)=4) return 1; return 0;void bianma() for(int i=1;i<=leicheng;i+) if(judge1(i)&&judge2(i) ten2three(i,sp); inte

12、g=atoi(sp); sett.insert(integ); vsiinteg=1; for(int j=0;j<k;j+) if(spj='0') sp+1j='1' else if(spj='1') sp+1j='2' else if(spj='2') sp+1j='0' integ=atoi(sp+1); sett.insert(integ); vsiinteg=1; for(int j=0;j<k;j+) if(sp+1j='0') sp+2j='1&#

13、39; else if(sp+1j='1') sp+2j='2' else if(sp+1j='2') sp+2j='0' integ=atoi(sp+2); sett.insert(integ); vsiinteg=1; p=p+3; if(n%3=0&&p>=n) break; else if(n%3=1&&p>=n) for(int j=i+1;j<=leicheng;j+) if(judge1(j)&&judge2(j)&&judge3(j)

14、 ten2three(j,sp); break; else if(n%3=2&&p>=n-1) for(int j=i+1;j<=leicheng;j+) if(judge1(j)&&judge2(j)&&judge4(j) ten2three(j,sp); for(int jj=0;jj<k;jj+) if(spjj='0') sp+1jj='1' else if(spjj='1') sp+1jj='2' else if(spjj='2') sp+

15、1jj='0' p+=2; if(p>=n) break; void cheng() int lft10005,rght10005; for(int d=0;d<k;d+) int lnum=0,rnum=0,lsum=0,rsum=0; for(int i=1;i<=n;i+) if(sid='0') lftlnum+=i; lsum+=weighti; if(sid='2') rghtrnum+=i; rsum+=weighti; if(lnum>rnum) lnum-; lsum-=weightlnum; if(ln

16、um<rnum) rnum-; rsum-=weightrsum; printf("第%d次称量：n",d+1); printf("左盘放:"); for(int i=0;i<lnum;i+) cout<<lfti<<" " cout<<endl; printf("右盘放:"); for(int i=0;i<rnum;i+) cout<<rghti<<" " cout<<endl; if(lsum>r

17、sum) rcdd='0' else if(lsum=rsum) rcdd='1' else if(lsum<rsum) rcdd='2' int bidui() for(int i=1;i<=n;i+) s2ii=atoi(si); int rcd2i,ans=0; rcd2i=atoi(rcd); for(int i=1;i<=n;i+) if(rcd2i=s2ii) ans=i; break; if(ans=0) heavy_or_light=0; for(int i=0;i<k;i+) if(rcdi='0') rcdi='2' else if(rcdi='2') rcdi='0' rcd2i=atoi(rcd); for(int i=1;i<=n;i+) if(rcd2i=s2ii) return i; else heavy_or_light=1; return ans; int main() cout<<"输入硬币数量，假币编号，假币重量"<<endl; cin>>n>>m>>fflag; memset(vsi,0,sizeof(vsi); f