实验一关于硬币称重问题的探讨
一、问题描述：
假设有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
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 lighter than others.\n",a[11]);
else
printf("There is a special coin:%f(12) and it's heavier 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 lighter than others.\n",a[10]);
else if(a[8]>a[9])
printf("There is a special coin:%f(10) and it's lighter than others.\n",a[9]);
else
printf("There is a special coin:%f(9) and it's lighter than others.\n",a[8]);
}
else
{
if(a[8]==a[9])
printf("There is a special coin:%f(11) and it's heavier than others.\n",a[10]);
else if(a[8]>a[9])
printf("There is a special coin:%f(9) and it's heavier than others.\n",a[8]);
else
printf("There is a special coin:%f(10) and it's heavier 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 heavier than others.\n",a[3]);
else if(a[6]>a[7])
printf("There is a special coin:%f(8) and it's lighter than others.\n",a[7]);
else
printf("There is a special coin:%f(7) and it's lighter 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 lighter than others.\n",a[4]);
else if(a[0]>a[2])
printf("There is a special coin:%f(1) and it's heavier than
others.\n",a[0]);
else
printf("There is a special coin:%f(3) and it's heavier than others.\n",a[2]);
}
else
{
if(a[1]>a[8])
printf("There is a special coin:%f(2) and it's heavier than others.\n",a[1]);
if(a[5] printf("There is a special coin:%f(6) and it's lighter 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 lighter than others.\n",a[3]); else if(a[6]>a[7]) printf("There is a special coin:%f(7) and it's heavier than others.\n",a[6]); else printf("There is a special coin:%f(8) and it's heavier than others .\n",a[7]); } else if(a[0]+a[2]+a[5] { if(a[0]==a[2]) printf("There is a special coin:%f(5) and it's heavier than others.\n",a[4]); else if(a[0]>a[2]) printf("There is a special coin:%f(3) and it's lighter than others.\n",a[2]); else printf("There is a special coin:%f(1) and it's lighter than others.\n",a[0]); } else { if(a[1] printf("There is a special coin:%f(2) and it's lighter than others.\n",a[1]); if(a[5]>a[8]) printf("There is a special coin:%f(6) and it's heavier than others.\n",a[5]); } } } 运行结果如图： 即输入12个数表示这12枚硬币的重量，最后输出哪一枚为假币，并判断其轻重。 四、实验总结 本次实验首先用信息熵的角度对实验进行了理论分析，即理论上要将假币找出，即消除事件的不确定度，只需要3次即可。然后又通过实际的称重情况对如何使用3次来称出硬币进行了分类讨论。最后附上的C语言程序则是对实际称重过程的描述。 通过本次实验，我对信息熵的理解更深入了，即要要想得到一个事件最终结果，即消除其不确定度便可以实现。通过这样的理解，对于信息熵在实际生活中的应用也得到了拓展。 实验二信道容量的迭代算 一、实验目的 （1）进一步熟悉信道容量的迭代算法。 （2）学习如何将复杂的公式转化为程序。 （3）掌握C 语言数值计算程序的设计和调试技术。 二、实验原理 1.算法如下 记ij i j p x y p =)|( ，i i p x p =)(，ji i i y x p ?=)|( i=1,2...r;j=1,2...s 初始化信源分布)......,(21)0(r i p p p p p =，置迭代计数器k=0，设信道容量相对误差门限为δ，δ>0; ②∑= i k i ij k i ij k ji p p p p ) () () (? ∑∑∑= +i j k ji ij j k ji ij k i p p p ]} ln {exp[] ln exp[)()()1(?? ④}]ln exp[ln{)()1(∑∑=+i j k ji ij k p C ? ⑤如果δ≤-=?+++) 1()()1(1k k k k C C C C ） （，转向⑦ ⑥置迭代序号k+1 k,转向 ⑦输出)1()(+k i x p 的结果和)1(+k C 的结果 ⑧停止 2.算法流程图如下
相关主题
文本预览