实验一 关于硬币称重问题的探讨
一、问题描述：
假设有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= < 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(\
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(\ else if(a[8]>a[11])
printf(\ else
printf(\ }
else if(a[0]+a[1]+a[2]>a[8]+a[9]+a[10]) {
if(a[8]==a[9])
printf(\
else if(a[8]>a[9])
printf(\ else
printf(\ } else {
if(a[8]==a[9])
printf(\ else if(a[8]>a[9])
printf(\ else
printf(\ } }
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(\ else if(a[6]>a[7])
printf(\ else
printf(\ }
else if(a[0]+a[2]+a[5]>a[1]+a[4]+a[8]) {
if(a[0]==a[2])
printf(\ else if(a[0]>a[2])
printf(\ else
printf(\ } else {
if(a[1]>a[8])
printf(\ if(a[5] printf(\ } } else { if(a[0]+a[2]+a[5]==a[1]+a[4]+a[8]) { if(a[6]==a[7]) printf(\ else if(a[6]>a[7]) printf(\ else printf(\ } else if(a[0]+a[2]+a[5] if(a[0]==a[2]) printf(\ else if(a[0]>a[2]) printf(\ else printf(\ } else { if(a[1] printf(\ if(a[5]>a[8]) printf(\ } } } 运行结果如图： 即输入12个数表示这12枚硬币的重量，最后输出哪一枚为假币，并判断其轻重。 四、实验总结 本次实验首先用信息熵的角度对实验进行了理论分析，即理论上要将假币找出，即消除事件的不确定度，只需要3次即可。然后又通过实际的称重情况对如何使用3次来称出硬币进行了分类讨论。最后附上的C语言程序则是对实际称重过程的描述。 通过本次实验，我对信息熵的理解更深入了，即要要想得到一个事件最终结果，即消除其不确定度便可以实现。通过这样的理解，对于信息熵在实际生活中的应用也得到了拓展。 实验二 信道容量的迭代算 一、实验目的 （1）进一步熟悉信道容量的迭代算法。 （2）学习如何将复杂的公式转化为程序。 （3）掌握C语言数值计算程序的设计和调试技术。 二、实验原理 1.算法如下 记p(yj|xi)?pij ，p(xi)?pi，p(xi|yi)??ji i=1,2...r;j=1,2...s
相关推荐：
loading