当前位置:文档之家› 信息论与编码实验报告

信息论与编码实验报告

信息论与编码实验报告-标准化文件发布号:(9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII实验一关于硬币称重问题的探讨一、问题描述:假设有N 个硬币,这N 个硬币中或许存在一个特殊的硬币,这个硬币或轻或重,而且在外观上和其他的硬币没什么区别。

现在有一个标准天平,但是无刻度。

现在要找出这个硬币,并且知道它到底是比真的硬币重还是轻,或者所有硬币都是真的。

请问:1)至少要称多少次才能达到目的;2)如果N=12,是否能在3 次之内将特殊的硬币找到;如果可以,要怎么称?二、问题分析:对于这个命题,有几处需要注意的地方:1)特殊的硬币可能存在,但也可能不存在,即使存在,其或轻或重未知;2)在目的上,不光要找到这只硬币,还要确定它是重还是轻;3)天平没有刻度,不能记录每次的读数,只能判断是左边重还是右边重,亦或者是两边平衡;4)最多只能称3 次。

三、解决方案:1.关于可行性的分析在这里,我们把称量的过程看成一种信息的获取过程。

对于N 个硬币,他们可能的情况为2N+1 种,即重(N 种),轻(N 种)或者无假币(1 种)。

由于这2N+1 种情况是等概率的,这个事件的不确定度为:Y=Log(2N+1)对于称量的过程,其实也是信息的获取过程,一是不确定度逐步消除的过程。

每一次称量只有3 种情况:左边重,右边重,平衡。

这3 种情况也是等概率的,所以他所提供的信息量为:y=Log3在K 次测量中,要将事件的不确定度完全消除,所以K= Log(2N+1)/ Log3根据上式,当N=12 时,K= 2.92< 3 所以13 只硬币是可以在3 次称量中达到目的的。

通过此式,我们还可以计算得到:通过3 次测量而找出异常硬币,N 的最大值为13.2.方案的提出为了描述方便,我们给这12枚硬币分别编号(1)-(12)。

首先,任选8个比较,如选:⑴⑵⑶⑷比⑸⑹⑺⑻1.若一样重,则假币在⑼~⑿中,第二步:⑼⑽比⑾⑴(1)若一样重,则可能的假币为⑿。

则第三步:⑴比⑿a.若一样重,则没有假币;b.不一样重,则假币为⑿:如果(1)>(12),则假币轻,反之,假币重;(2)若⑼⑽重,则第三步:⑼比⑽a.若一样重,则假币为⑾(较轻)b.不一样重,则假币为⑼、⑽中较重者(3)若⑼⑽轻,则第三步:⑼比⑽a.若一样重,则假币为⑾(较重)b.不一样重,则假币为⑼、⑽中较轻者2.若⑴⑵⑶⑷重,则第二步:⑴⑵⑸比⑶⑷⑹(1)若一样重,则假币在⑺⑻中,第三步:⑺比⑻假币为⑺、⑻中较轻者(2)若⑴⑵⑸端较重,则假币在⑴⑵⑹中,第三步:⑴比⑵a.若一样重,则假币为⑹(较轻)b.不一样重,则假币为⑴⑵中较重者(3)若⑶⑷⑹端较重,则假币在⑶⑷⑸中,第三步:⑶比⑷a.若一样重,则假币为⑸(较轻)b.不一样重,则假币为⑶、⑷中较重者3.若⑴⑵⑶⑷轻,则与上面类似,第二步:⑴⑵⑸比⑶⑷⑹(1)若一样重,则假币在⑺⑻中,第三步:⑺比⑻假币为⑺、⑻中较重者(2)若⑴⑵⑸端较轻,则假币在⑴⑵⑹中,第三步:⑴比⑵a.若一样重,则假币为⑹(较重)b.不一样重,则假币为⑴⑵中较轻者(3)若⑶⑷⑹端较轻,则假币在⑶⑷⑸中,第三步:⑶比⑷a.若一样重,则假币为⑸(较重)b.不一样重,则假币为⑶、⑷中较轻者3.用C语言编程实现上述方案为:#include <stdio.h>void main(){int i;float a[12];for(i=0;i<12;i++)scanf("%f",&a[i]);if(a[0]+a[1]+a[2]+a[3]==a[4]+a[5]+a[6]+a[7]){if(a[0]+a[1]+a[2]==a[8]+a[9]+a[10]){if(a[8]==a[11])printf("There is no special coin!\n");else if(a[8]>a[11])printf("There is a special coin:%f(12) and it's ligh ter than others.\n",a[11]);elseprintf("There is a special coin:%f(12) and it's heav ier than others.\n",a[11]);}else if(a[0]+a[1]+a[2]>a[8]+a[9]+a[10]){if(a[8]==a[9])printf("There is a special coin:%f(11) and it's ligh ter than others.\n",a[10]);else if(a[8]>a[9])printf("There is a special coin:%f(10) and it's ligh ter than others.\n",a[9]);elseprintf("There is a special coin:%f(9) and it's light er than others.\n",a[8]);}else{if(a[8]==a[9])printf("There is a special coin:%f(11) and it's heav ier than others.\n",a[10]);else if(a[8]>a[9])printf("There is a special coin:%f(9) and it's heavi er than others.\n",a[8]);elseprintf("There is a special coin:%f(10) and it's heav ier than others.\n",a[9]);}}else if(a[0]+a[1]+a[2]+a[3]>a[4]+a[5]+a[6]+a[7]){if(a[0]+a[2]+a[5]==a[1]+a[4]+a[8]){if(a[6]==a[7])printf("There is a special coin:%f(4) and it's heavi er than others.\n",a[3]);else if(a[6]>a[7])printf("There is a special coin:%f(8) and it's light er than others.\n",a[7]);elseprintf("There is a special coin:%f(7) and it's light er than others.\n",a[6]);}else if(a[0]+a[2]+a[5]>a[1]+a[4]+a[8]){if(a[0]==a[2])printf("There is a special coin:%f(5) and it's light er than others.\n",a[4]);else if(a[0]>a[2])printf("There is a special coin:%f(1) and it's heavi er than others.\n",a[0]);elseprintf("There is a special coin:%f(3) and it's heavi er than others.\n",a[2]);}else{if(a[1]>a[8])printf("There is a special coin:%f(2) and it's heavi er than others.\n",a[1]);if(a[5]<a[8])printf("There is a special coin:%f(6) and it's light er than others.\n",a[5]);}}else{if(a[0]+a[2]+a[5]==a[1]+a[4]+a[8]){if(a[6]==a[7])printf("There is a special coin:%f(4) and it's light er than others.\n",a[3]);else if(a[6]>a[7])printf("There is a special coin:%f(7) and it's heavi er than others.\n",a[6]);elseprintf("There is a special coin:%f(8) and it's heavier th an others.\n",a[7]);}else if(a[0]+a[2]+a[5]<a[1]+a[4]+a[8]){if(a[0]==a[2])printf("There is a special coin:%f(5) and it's heavi er than others.\n",a[4]);else if(a[0]>a[2])printf("There is a special coin:%f(3) and it's light er than others.\n",a[2]);elseprintf("There is a special coin:%f(1) and it's light er than others.\n",a[0]);}else{if(a[1]<a[8])printf("There is a special coin:%f(2) and it's light er than others.\n",a[1]);if(a[5]>a[8])printf("There is a special coin:%f(6) and it's heavi er than others.\n",a[5]);}}}运行结果如图:即输入12个数表示这12枚硬币的重量,最后输出哪一枚为假币,并判断其轻重。

相关主题