称假币问答实验报告

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

2、平衡，而且这三种可能是概率相 等的，所以每一次使用天平的结果都携带 log3 的信息量。（2 ）要从 N 个硬币中找到那个不一样，可以有 2N 种概率相同的可能，每个硬币都可能偏 轻或者偏重，这个事件所携带的信息量是 log2N 。所以可以得到 最少可以使用 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，1221，6，7，85，10，11，

3、129，2，3，435，6，10，29，7，11，31，8，12，4设3种称重结果分别表示为：0 :平衡，1:左重，-1 :右重。得到如下鉴别结果:称重序号称重鉴别结果匸号 编 正 修123号 编 币 假JZZ-r二Q称重结一OOO-19Q1-9Z1 OO1O2Q111Q1-O O LJ1-O1QC CU U果1-O2Z1O1Z1-11Z-1OO4Z1-1 O12Z1 O-3 1z ZO 41 d-o n称重结果1d -n1_1-u 211101-Oo V15Q311-8 -Q -2-1I 1称重结果1-O/ 4(Q Q-o oU 3QQo-12Q- o18Zo-I C-6ZTTT-u d7Z

4、1-1Qo-1-50-1_-_1参见上面表格，可用矩阵表示 3次称重的安排，矩阵上面标明 12次硬币的序号，矩阵 的3行分别表示3次连续称重时硬币的放置状态， 1表示放到左盘，-1表示放到右盘，0 表示放到旁边(不参与称重)。1234 5 67 891011121111 -1-1 -1-100001000 -11 110-1-1-101-10 11 -10-11-10比较上面的表格和矩阵,发现:如果检测结果与上面矩阵的某列符合，则对应序号的硬币为假币，且重量较重；如果检查结果与不包含在上述矩阵的列中，则1、-1互换，得到假币 对应序号，但重量较轻。【问题二】n = 39查阅资料得到，n次称量最

5、多可以在 -个球中找到不同的球，并判断它的轻重。(1) 编码:知道了球数，就能算出需要称量几次;以这个次数作为长度，使用0、1、2排列组合进行编码，如 001021、212022等等，再去掉全0、全1和全2，可知一共有，个编码；如果在一个编码中，第一处相邻数字不同的情况是01、12或20 ,则我们称它为正序码，如 1120021 ；否则为逆序码，如 2221012 ；3" - 3在长度为n的编码中，正序码和逆序码的数量相等，均为J 个。（2）赋值：如果把一个正序码中的 0换成1，1换成2，2换成0,则它仍然是正序码；根据这个原理，我们把所有正序码按3个3个进行分组，如 12001、2

6、0112、01220这3个就是一组；把正序码一组一组地分配给小球，每球一个，直到分完；然后把每个正序码的 0换成2，2换成0,它就变成了一个逆序码，如12001变成10221 ；这样，每个小球就有了两个编码，一个正序，一个逆序，而且所有球都不重复。（3）称重：第一轮，我们把所有正序码第一位为0的小球放在天平左侧，为2的小球放在右侧，其它的放在旁边；如果天平左倾，记为 0 ;右倾，记为2;平衡，记为1 ；然后是第二轮，把第二位为0的小球放在左侧，为 2的放在右侧，同样记下称量结果；每一轮都按这个顺序进行，一共要称n次，最终结果是个n位的编码；如果编码等于某个小球的正序码，则这个小球比其它球重；

7、如果编码等于某个小球的逆序码，则这个小球比其它球轻。【问题三】n = n方法与问题二同四、算法演示以n=12为例(1)编号(2)称重正序码第一位为0的硬币放在天枰的左侧，第一位为2的放在右侧， 第一位为1的放在旁边结果与事先挑选的硬币一致五、编写代码#in elude <iostream>#include<algorithm> #include<cstring>#include<cstdio>#include<cstdlib>#include<set>using namespace std;set<int >

8、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='0'while(1)snum+=a%3+'0'a/=3;if(a<=1)snum=a+'0'break;int judge1(int a)char sss310005;int

9、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')sss1i='0'integ1=atoi(sss1);for(int i=0;i<k;i+)if(sss1i='0')sss2i='1'else if(sss1i='1')sss2i

10、='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(int 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;els

11、e if(ststi-'0'=1&&ststi+1-'0'=2)ok=1;else if(ststi-'0'=2&&ststi+1-'0'=0)ok=1;break;return ok;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'&&st

12、rlen(cc)=4)return 1;return 0;void bianma()for(int i=1;i<=leicheng;i+)if(judge1(i)&&judge2(i)ten2three(i,sp);integ=atoi(sp);sett.insert(integ);vsiinteg=1;for(int j=0;j<k;j+)if(sp j='0')sp+1 j='1'else if(spj='1')sp+1 j='2'else if(spj='2')sp+1 j=

13、9;0'integ=atoi(sp+1);sett.insert(integ);vsiinteg=1;for(int j=0;j<k;j+)if(sp+1 j='0')sp+2 j='1'else if(sp+1j='1')sp+2 j='2'else if(sp+1 j='2')sp+2 j='0'integ=atoi(sp+2);sett.insert(integ);vsiinteg=1;p=p+3;if(n%3=0&&p>=n)break;else if(n

14、%3=1&&p>=n)for(int j=i+1;j<=leicheng;j+)if(judge1(j)&&judge2(j)&&judge3(j) 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&

15、#39;)sp+1jj='1'else if(spjj='1')sp+1jj='2'else if(spjj='2')sp+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

16、')rghtrnum+=i;rsum+=weighti;if(lnum>rnum)lnum-;lsum-=weightlnum;if(lnum<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<

17、;rnum;i+)cout<<rghti<<" " cout<<endl;if(lsum>rsum)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(

18、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;elseheavy_or_light=1;return ans;int main()"<<endl;cout<<" 输入硬币数量，假币编号，假币重量cin>>n>>m>>fflag;memset(vsi,0