问题：
12个外表一样的小球，有11个球重量相同，另1个球为“坏球”，可能比较重，也可能比较轻。 如何利用天平称重3次来找出这个“坏球”？
分析：
12个球中的某一个球为坏球，该事件的信息熵
H1
即为
∑12112−log(112)=log(12)
,
而该坏球是重球和轻球的信息熵
H2
为
∑2−12log(12)=log(2).
故问题的总信息量 H3=H1+H2=log(24) 。
天平称重，每次给出的结果有三种: 左重，平衡，右重。 此时对应的信息熵
H4=∑3−13log(13)=log(3)
;
天平称重3次给出的总信息熵即为
H5=3∗H4=log(27)
.
由于 H5>H4 , 天平3次称重能够提供足够的信息量来找到对应的坏球。不仅如此，其实还可以得出这个坏球是重还是轻。
答案：
代码中A==B情况的处理稍有差异。
思维导图
#include <iostream>
#include <random>
#include <assert.h>
#include <string>
using namespace std;
string str[4] = {"st","nd","rd","th"};
int compare_time = 0;
void initweight (int weight[],int n)
{
// 数组长度定义
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, n-1);
for (int i =0 ; i < n; i++)
{
weight[i] = 2;
}
int idx = dis(gen);
int type = dis(gen) > ((float)(n-1))/2 ? 1 : -1 ;
// calculate the probability of type value
// int count[2] = {0,0};
// for(int i = 0; i < 1000000; i++)
// {
// int idx = dis(gen) > (float)(n-1)/2 ? 1 : 0 ;
// count[idx]++;
// }
//
// cout<<count[0]<<" "<<count[1]<<endl;
weight[idx] += type; // type = 1， 重球； type = 0, 轻球
}
int compare_weight(int left_side[], int right_side[], int n)
{
//string name[3] = {"1st","2nd","3rd"};
if(compare_time < 3)
cout<< " the "<< compare_time<<str[compare_time++] << " compare : ";
else
return 0;
// left minus right , >: left heavy =: equal <: light
int sum_weight = 0;
for (int i =0 ; i < n ; i++)
{
sum_weight += (left_side[i] - right_side[i]);
}
if(sum_weight > 0 )
return 1;
if(sum_weight == 0)
return 0;
if(sum_weight < 0)
return -1;
}
int AheavythanB(int A[], int B[],int C[]) // A > B
{
int D[4] = {A[0],C[1],C[2],C[3]};
int E[4] = {B[0],A[1],A[2],A[3]};
int bad_ball = -1;
int info = compare_weight(D,E,4);
cout<<" "<< info<< endl;
switch(info)
{
case 1: // D has bad ball, and A[0] is the heavy ball or B[0] is the light ball
{
info = compare_weight(A,C,1);
cout<<" "<< info<< endl;
if(info == 1)
{
bad_ball = 0;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[0]<<endl;
}
else
{
bad_ball = 4; // B[0]
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[0]<<endl;
}
break;
}
case 0:
{
// B[1],B[2],B[3] has bad ball and is light ball
info = compare_weight(B+1,B+2,1);
cout<<" "<< info<< endl;
if(info == 0)
{
bad_ball = 7; // B[3]
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[3]<<endl;
break;
}
else if(info > 0)
{
bad_ball = 6; // B[2]
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[2]<<endl;
break;
}
else
{
bad_ball = 5; // B[1]
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[1]<<endl;
break;
}
break;
}
case -1: // D( A[0],C[1],C[2],C[3]) < E(B[0],A[1],A[2],A[3] )
{
// A[1],A[2],A[3] is the heavy ball
info = compare_weight(A+1,A+2,1);
cout<<" "<< info<< endl;
if(info > 0)
{
bad_ball = 1;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[1]<<endl;
break;
}
else if(info == 0)
{
bad_ball = 3;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[3]<<endl;
break;
}
else
{
bad_ball = 2;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[2]<<endl;
break;
}
}
}
return bad_ball;
}
int AlightthanB(int A[], int B[], int C[]) // A < B
{
int D[4] = { B[0],C[1],C[2],C[3]};
int E[4] = { A[0],B[1],B[2],B[3]};
int bad_ball = -1;
int info = compare_weight(D,E,4);
cout<<" "<< info<< endl;
switch(info)
{
case 1: // B[0] heavy ball or A[0] light ball
{
info = compare_weight(A,C,1);
cout<<" "<< info<< endl;
if(info < 0)
{
bad_ball = 0;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[0]<<endl;
}
else
{
bad_ball = 4;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[0]<<endl;
}
break;
}
case 0: // A[1],A[2],A[3] has light ball
{
info = compare_weight(A+1,A+2,1);
cout<<" "<< info<< endl;
if( info > 0 )
{
bad_ball = 2;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[2]<<endl;
}
else if(info == 0)
{
bad_ball = 3;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[3]<<endl;
}
else
{
bad_ball = 1;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<A[1]<<endl;
}
break;
}
case -1: // B[1],B[2],B[3] has heavy ball
{
info = compare_weight(B+1,B+2,1);
cout<<" "<< info<< endl;
if(info > 1)
{
bad_ball = 5;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[1]<<endl;
}
else if(info == 0)
{
bad_ball = 7;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[3]<<endl;
}
else
{
bad_ball = 6;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<B[2]<<endl;
}
break;
}
}
return bad_ball;
}
int Aequal2B(int C[],int A[]) // C has the bad ball
{
int bad_ball = -1;
int info = compare_weight(C,A,2); // 2rd compare
cout<<" "<< info<< endl;
switch(info)
{
case 1: // C(0,1) > A(0,1) , C[0],C[1] has the bad ball and is heavy ball
{
info = compare_weight(C,A,1);
cout<<" "<< info<< endl;
if(info > 0)
{
bad_ball = 8;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[0]<<endl;
}
else // info == 0 , because info < 0 not exist
{
bad_ball = 9;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[1]<<endl;
}
break;
}
case 0:
{
// (C(2,3)) has the bad all and
info = compare_weight(C+2,A,1);
cout<<" "<< info<< endl;
if(info > 0)
{
bad_ball = 10;
cout <<"the heavy ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[2]<<endl;
}
else if(info < 0)
{
bad_ball = 10;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[2]<<endl;
}
else
{
bad_ball = 11;
cout <<"the heavy/light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[3]<<endl;
}
break;
}
case -1:
{
// C(0,1) < A(0,1) , C has the bad ball and is light ball
info = compare_weight(C,A,1);
cout<<" "<< info<< endl;
if(info < 0)
{
bad_ball = 8;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[0]<<endl;
}
else
{
bad_ball = 9;
cout <<"the light ball is "<< bad_ball+1 << str[min(bad_ball,3)]<< " : "<<C[1]<<endl;
}
break;
}
} //2nd
return bad_ball;
}
int find_ball(int weight[], int n)
{
assert(n == 12); // this the 12 balls' method
int bad_ball = -1;
int A[4],B[4],C[4];
for(int i = 0; i < 4; i++)
{
A[i] = weight[i];
B[i] = weight[i+4];
C[i] = weight[i+8];
}
// first compare
int info = compare_weight(A,B,4);
cout<<" "<< info<< endl;
switch(info)
{
case 1: // A > B
{
bad_ball = AheavythanB(A,B,C);
break;
}
case 0: // A = B , C has the bad all
{
bad_ball = Aequal2B(C,A);
break;
}
case -1: // A < B
{
bad_ball = AlightthanB(A,B,C);
break;
}
}
return bad_ball;
}
int _tmain(int argc, _TCHAR* argv[])
{
int w[12];
int n = 12;
int err = 0;
for(int i = 0; i < n; i++)
{
compare_time = 0;
initweight(w,12);
// the input data
for (int i = 0; i < 12; i++)
{
cout<<i+1<<":"<<w[i]<<", ";
}
cout<<endl;
int bad = find_ball(w,12);
if(w[bad] == 2)
err++;
}
cout<<"find error count: "<< err<<endl;
return 0;
}