稱假幣問題實(shí)驗(yàn)報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上稱假幣問題實(shí)驗(yàn)報告信息論第一次作業(yè)學(xué)校：西安電子科技大學(xué)班別：班姓名：黃丹丹學(xué)號：專心-專注-專業(yè)1、 問題重述盒中有n個外形相同的硬幣，知道其中有一個重量不同的硬幣，但不知是比真幣輕，還是比真幣重?，F(xiàn)用一無砝碼天枰對現(xiàn)有硬幣進(jìn)行稱重來鑒別假幣，無砝碼天枰的稱重有3種結(jié)果，平衡，向左傾，向右傾。當(dāng)n=12;n=39;n=n時，如何稱重使實(shí)驗(yàn)次數(shù)最少，鑒別出假幣并判斷出輕或重？二、問題分析根據(jù)熵的可加性，一個復(fù)合事件的平均不確定性可以通過多次試驗(yàn)逐步解除。如果我們使實(shí)驗(yàn)所獲得的信息量最大，那么所需要的總試驗(yàn)次數(shù)就最少。（1）每一次使用天平，可以得到三種可能，左偏，右偏，

2、平衡，而且這三種可能是概率相等的，所以每一次使用天平的結(jié)果都攜帶log3的信息量。（2）要從N個硬幣中找到那個不一樣，可以有2N種概率相同的可能，每個硬幣都可能偏輕或者偏重，這個事件所攜帶的信息量是 log2N。所以可以得到 最少可以使用 log2N/log3次天平 就可以湊夠信息量，指出哪一個是不一樣的。3、 問題解決【問題一】設(shè)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設(shè)3種稱重結(jié)果分別表示為：0：平衡，1：左重，-1：右重。得到如下鑒別結(jié)果：稱重鑒別結(jié)果稱重序號0231輕：Q重：Z假幣編號修正編號稱重結(jié)果0-1-1-1-1-1111110000010Z1ZZZZZZZQQQQ3249912121111101000100-101001101-10-1011010-11010-1-10-11100稱重結(jié)果11-1-10-111_QQQQ67851-1-11-111-1011-1稱重結(jié)果00-1111-1-1-100-11QQQQZZZZ_51768234-1-11-1-10-11-1-111-110-100-101-10-1參見上面表格，可用矩陣表示3次稱重

4、的安排，矩陣上面標(biāo)明12次硬幣的序號，矩陣的3行分別表示3次連續(xù)稱重時硬幣的放置狀態(tài)，1表示放到左盤，-1表示放到右盤，0表示放到旁邊（不參與稱重）。比較上面的表格和矩陣，發(fā)現(xiàn)：如果檢測結(jié)果與上面矩陣的某列符合，則對應(yīng)序號的硬幣為假幣，且重量較重；如果檢查結(jié)果與不包含在上述矩陣的列中，則、互換，得到假幣對應(yīng)序號，但重量較輕?！締栴}二】查閱資料得到，n次稱量最多可以在個球中找到不同的球，并判斷它的輕重。 （1）編碼：知道了球數(shù)，就能算出需要稱量幾次；以這個次數(shù)作為長度，使用0、1、2排列組合進(jìn)行編碼，如、等等，再去掉全0、全1和全2，可知一共有個編碼；如果在一個編碼中，第一處相鄰數(shù)字不

5、同的情況是01、12或20，則我們稱它為正序碼，如；否則為逆序碼，如；在長度為n的編碼中，正序碼和逆序碼的數(shù)量相等，均為個。（2）賦值：如果把一個正序碼中的0換成1，1換成2，2換成0，則它仍然是正序碼；根據(jù)這個原理，我們把所有正序碼按3個3個進(jìn)行分組，如12001、20112、01220這3個就是一組；把正序碼一組一組地分配給小球，每球一個，直到分完；然后把每個正序碼的0換成2，2換成0，它就變成了一個逆序碼，如12001變成10221；這樣，每個小球就有了兩個編碼，一個正序，一個逆序，而且所有球都不重復(fù)。（3）稱重：第一輪，我們把所有正序碼第一位為0的小球放在天平左側(cè)，為2的小球放在右側(cè)，

6、其它的放在旁邊；如果天平左傾，記為0；右傾，記為2；平衡，記為1；然后是第二輪，把第二位為0的小球放在左側(cè)，為2的放在右側(cè)，同樣記下稱量結(jié)果；每一輪都按這個順序進(jìn)行，一共要稱n次，最終結(jié)果是個n位的編碼；如果編碼等于某個小球的正序碼，則這個小球比其它球重；如果編碼等于某個小球的逆序碼，則這個小球比其它球輕?！締栴}三】方法與問題二同4、 算法演示以為例（）編號（） 稱重正序碼第一位為的硬幣放在天枰的左側(cè)，第一位為的放在右側(cè)，第一位為的放在旁邊結(jié)果與事先挑選的硬幣一致五、編寫代碼#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<<"輸入硬幣數(shù)量，假幣編號，假幣重量"<<endl; cin>>n>>m>>fflag; memset(vsi,0,sizeof(vsi); f