信息论与编码实验报告
实验⼀关于硬币称重问题的探讨
⼀、问题描述：
假设有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");
el if(a[8]>a[11])
printf("There is a special coin:%f(12) and it's lighter than others.\n",a[ 11]); el
printf("There is a special coin:%f(12) and it's heavier than others.\n",a[ 11]); }
el 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]); el if(a[8]>a[9])
printf("There is a special coin:%f(10) and it's lighter than others.\n",a[ 9]); el
printf("There is a special coin:%f(9) and it's lighter than others.\n",a[8 ]);
}
el
{
if(a[8]==a[9])
printf("There is a special coin:%f(11) and it's heavier than others.\n",a[ 10]); el if(a[8]>a[9])
printf("There is a special coin:%f(9) and it's heavier than others.\n",a[8 ]); el
printf("There is a special coin:%f(10) and it's heavier than others.\n",a[ 9]); }
}
el 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 ]); el if(a[6]>a[7])
printf("There is a special coin:%f(8) and it's lighter than others.\n",a[7 ]); el
printf("There is a special coin:%f(7) and it's lighter than others.\n",a[6 ]);
}
el 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 ]); el if(a[0]>a[2])
printf("There is a special coin:%f(1) and it's heavier than others.\n",a[0 ]);
el
printf("There is a special coin:%f(3) and it's heavier than others.\n",a[2 ]); }
el
{
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 ]); }
}
el
{
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 ]); el if(a[6]>a[7])
printf("There is a special coin:%f(7) and it's heavier than others.\n",a[6 ]); el
printf("There is a special coin:%f(8) and it's heavier than others.\n",a[7]); }
el 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 ]); el if(a[0]>a[2])
printf("There is a special coin:%f(3) and it's lighter than others.\n",a[2 ]);
el
printf("There is a special coin:%f(1) and it's lighter than others.\n",a[0 ]);
}
el
{
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=;j=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[)(
