lemene

         12球问题表述如下：有12个球，有一个球的重量与其它球的重量不一致。用一台没有刻度的天平称3次把这个球找出。当然12球问题可以推广至N个球。
    首先考虑这道题目的模式，它属于输入反馈的问题。每一次输入（即称一次）便会有一个反馈信息，分析反馈信息再次输入，直到把问题解决。通过一次次输入反馈、这类问题解法思路较简单，由于是有穷状态，状态数目不大，可以用穷举法解答。比较所有的输入，找出最佳输入（某个标准意义下）。问题是如何衡量输入的好坏。直观上，输入越好，反馈的信息就越大。问题变成了对信息的量化。山农给出了信息量的定义是解决问题的关键。信息量是不确定性的大小。如果某个事件的概率为P，则它含有的信息量为log(1/p)。具体理论请参考关于信息论方面的书籍。（这个问题和猜数字很像，大家参考此文《猜数字的一种解法》）。

     具体到这个12球问题。12个球从0-11编号。0号球为较轻的球可能性为1/24。这个事件的信息量log(24)。同理0号球为重球这个事件的信息量为log(24)。这样的事件有24个，每个事件出现的概率1/24，所以整个系统的信息量24*(1/24*log(24))，即log(24)。
下面我们考虑一次具体的输入：
第一次输入，天平左端放0号球，右端放1号球。反馈信息可能为平衡，左倾，右倾。
平衡：这时0，1号球是标准球。根据上面的计算过程，同样可以计算出此时系统含有的信息量20*(1/20*log(20))，即log(20)。这次输入获得的信息log(24)-log(20)。
左倾：可能的情况，1号球为轻球，2号球为重球。此时系统的信息量log(2)。获得的信息log(24)-log(2)。
右倾：同左倾，此时系统的信息量log(2)。获得的信息log(24)-log(2)。
这次输入，出现平衡的概率20/24，出现左倾的概率2/24，出现右倾的概率2/24。这可以计算这次输入能够获得的平均信息量为20/24*(log(24)-log(20))+2/24*(log(24)-log(2))+2/24*(log(24)-log(2))，即20/24*log(24/20)+2/24*log(24/2)+2/24*log(24/2)。

   下面就要枚举所有可能的输入，找出平均信息量最大的输入。枚举需要些技巧，需要把球分类，例如第一次输入时每个球可以看成相同，左右天平放的球数为1，2，3，4，5，6，一共六情况。如果把每个球区别看待枚举的次数将会很多。下面介绍分类方法。
根据球的状态，分成4类，一类：标准球即排出不标准的可能性，二类：只可能为轻球，三类：只可能为重球，四类：可能为轻球也可能为重球。

// 把球分类
// 输出参数：type 表示对应球的类型，0为标准球，1可能为轻球，2可能为重球，3都有可能
void CGuessBall::SortBalls(VectorInt& type)
{
    for (int i=0; i<m_iNumOfBalls; i++)
    {
        if (m_vPsbAns[i*2] == 0)
            type[i]++;
        if (m_vPsbAns[i*2+1] == 0)
            type[i] += 2;
    }
}

// 返回四个数组，分别表示四类球
void CGuessBall::SortBalls(VectorInt& type0, VectorInt& type1, VectorInt& type2, VectorInt& type3)
{
    for (int i=0; i<m_iNumOfBalls; i++)
    {
        if (m_vPsbAns[i*2] == 0 && m_vPsbAns[i*2+1] == 0)
            type3.push_back(i);
        else if (m_vPsbAns[i*2+1] == 0)
            type2.push_back(i);
        else if (m_vPsbAns[i*2] == 0)    
            type1.push_back(i);
        else
            type0.push_back(i);
    }
}

下面函数说明如何枚举，首先找出2*i个球，然后从中找出i个球。计算这次输入的信息量，需要我以前写的一篇文章《从集合中枚举子集 》。

// 使用分类法得到最佳输入
// 输出参数：left，right左右天平球的标号
void CGuessBall::GetBestInputSort(VectorInt& left, VectorInt& right )
{
    double max_entropy = 0.0;
    
    // 把球分类
    VectorInt types(m_iNumOfBalls, 0);
    SortBalls(types);
    VectorInt t[4];
    SortBalls(t[0], t[1], t[2], t[3]);
    
    // 枚举所有可能的输入组合
    // 首先找出i个球，左右天平各方i/2个球。
    CSetIterAgent<int> iter(types);
    for (int i=2; i<=m_iNumOfBalls; i+=2)
    {
        iter.Init(i, CSetIter::MULT_DISORDER_IN);
        VectorInt subset(i, 0);
        while (iter.GetNextSubset(subset, types))
        {            
            // 再从i个球中找出i/2个球
            CSetIterAgent<int> iter_i(subset);
            iter_i.Init(i/2, CSetIter::MULT_DISORDER_IN);
            VectorInt subset_l(i/2, 0);
            VectorInt subset_r(i/2, 0);
            while (iter_i.GetNextSubset(subset_l, subset))
            {
                // subset - subset_l得到subset_r
                int idx_r=0, idx_l=0, idx=0;
                while (idx < subset.size())
                {
                    if (idx_l >= subset_l.size() ||
                        subset_l[idx_l] != subset[idx])
                    {
                        subset_r[idx_r++] = subset[idx++];
                    }
                    else
                    {
                        idx_l++, idx++;
                    }
                }
                
                // 把球的类型转化成具体的球号
                int idxs[4] = {0, 0, 0, 0};
                left.assign(i/2, -1);
                for (int j=0; j<subset_l.size(); j++)
                {
                    left[j] = t[subset_l[j]][idxs[subset_l[j]]++];
                }
                right.assign(i/2, -1);
                for (int j=0; j<subset_r.size(); j++)
                {
                    right[j] = t[subset_r[j]][idxs[subset_r[j]]++];
                }
                
                // 得到所有可能的反馈
                VectorInt outputs(3, 0);
                for (int j=0; j<m_vPsbAns.size(); j++)
                {
                    if (m_vPsbAns[j] == 1)
                        continue;
                    outputs[CheckFeedback(right, left, j)+1]++;        
                }
                
                // 检查是否是理论最优，提前返回
                 if (IsTheoryBestInput(outputs))
                {
                    m_vLeft = left;
                    m_vRight = right;
                    return;
                }
                
                // 比较
                double entropy = CalcEntropy(outputs);
                // 求最大的信息量
                if (max_entropy < entropy)
                {
                    max_entropy = entropy;
                    m_vLeft = left;
                    m_vRight = right;
                }
            }
        }
    }
    left = m_vLeft;
    right = m_vRight;
}

    要使得到的信息量最大，就要使天平左倾，右倾，平衡的出现的概率尽可能相等。四类球，只有三类影响平衡，如果它们的个数能被3整除，左右天平各放三分之一份球。当然也有不能被3整除的情况。三类球，每一类均可能有余数0，1，2。组合起来一共有27种情况。考虑这27种情况配合标准球如何分配。得到以下的算法，先将三类球三等分，然后再考虑27种余数情况，得到第二种算法。

// 直接法得到最佳输入
void CGuessBall::GetBestInputDirect(VectorInt& left, VectorInt& right)
{
    // 第一次输入，没有标准球。
    if (m_iTimes == 0)
    {
        int num = (m_iNumOfBalls+1) / 3;
        left.assign(num, -1);
        right.assign(num, -1);
        for (int i=0; i<num; i++)
        {
            left[i] = i;
            right[i] = i + num;
        }
    }
    else
    { // 有标准球
        VectorInt t0, t1, t2, t3;
        SortBalls(t0, t1, t2, t3);
        int tmp1 = t1.size() / 3;
        for (int i=0; i<tmp1; i++)
        {
            left.push_back(t1[i]);
            right.push_back(t1[i+tmp1]);
        }
        int tmp2 = t2.size() / 3;
        for (int i=0; i<tmp2; i++)
        {
            left.push_back(t2[i]);
            right.push_back(t2[i+tmp2]);
        }
        int tmp3 = t3.size() / 3;
        for (int i=0; i<tmp3; i++)
        {
            left.push_back(t3[i]);
            right.push_back(t3[i+tmp3]);
        }
        
        switch ((t3.size()%3)*9+(t2.size()%3)*3+(t1.size()%3))
        {
        case 0*3*3 + 0*3 + 0:
        case 0*3*3 + 0*3 + 1:
        case 0*3*3 + 1*3 + 0:
            break;
        case 0*3*3 + 0*3 + 2:
        case 0*3*3 + 1*3 + 2:
        case 0*3*3 + 2*3 + 2:
//        case 1*3*3 + 0*3 + 2:
            left.push_back(t1[tmp1*2]);
            right.push_back(t1[tmp1*2+1]);
            break;
        case 0*3*3 + 1*3 + 1:
            left.push_back(t1[tmp1*2]);
            right.push_back(t0[0]);
            break;
        case 0*3*3 + 2*3 + 0:
        case 0*3*3 + 2*3 + 1:
//        case 1*3*3 + 2*3 + 0:
            left.push_back(t2[tmp2*2]);
            right.push_back(t2[tmp2*2+1]);
            break;
        case 1*3*3 + 0*3 + 0:
//        case 1*3*3 + 0*3 + 1:
//        case 1*3*3 + 1*3 + 0:
        case 2*3*3 + 0*3 + 0:
            left.push_back(t3[tmp3*2]);
            right.push_back(t0[0]);
            break;
//        case 1*3*3 + 1*3 + 1:
//        case 1*3*3 + 1*3 + 2:
//        case 1*3*3 + 2*3 + 1:
//            left.push_back(t1[tmp1*2]);
//            right.push_back(t3[tmp3*2]);
//            break;
//        case 1*3*3 + 2*3 + 2:
//            left.push_back(t1[tmp1*2]);
//            right.push_back(t1[tmp1*2+1]);
//            left.push_back(t2[tmp2*2]);
//            right.push_back(t2[tmp2*2+1]);
//            break;
//        case 2*3*3 + 0*3 + 1:
//        case 2*3*3 + 0*3 + 2:
//        case 2*3*3 + 1*3 + 0:
//        case 2*3*3 + 1*3 + 1:
//        case 2*3*3 + 2*3 + 0:
//        case 2*3*3 + 1*3 + 2:
//        case 2*3*3 + 2*3 + 1:
//            left.push_back(t3[tmp3*2]);
//            right.push_back(t3[tmp3*2+1]);
//            break;
//        case 2*3*3 + 2*3 + 2:
//            left.push_back(t1[tmp1*2]);
//            right.push_back(t1[tmp1*2+1]);
//            left.push_back(t3[tmp3*2]);
//            right.push_back(t3[tmp3*2+1]);
//            break;
        default:;
        }
    }
    m_vLeft = left;
    m_vRight = right;
}

这里要注意，如果有标准球则能达到最佳的输入。所以第一次没有标准球要区别对待。此外其实没有27种情况，因为第二，三类不可能和第四类同时出现。

这是一个测试程序 ，解答12球的问题，它输出左右天平放的球的编号，等待用户判断左倾，右倾还是平衡，直到输出结果。

    从程序运行情况看，很多球也很少几次就可以找出不规则球。下面讨论N个球要多少次才能确定不规则球。最佳输入能够使天平的三种情况出现的次数均匀。如果是最佳输入，系统的信息量只剩下原来的三分之一。由于对N个球，如果N不能被3整除，第一次就找不到最佳输入。对N个球可以在[log3(2*N)]+1次内找出不规则球。

第二个程序是测试上面两种算法的性能

#ifdef _TEST_TIME_
#include <windows.h>
int main()
{
    const int inc = 20;
    DWORD time;
    CGuessBall guess;
    for (int i=0; i<2; i++)
    {
        for (int j=12; j< 12+inc; j++)
        {
            time = 0;
            for (int t=0; t<j*2; t++)
            {
                guess.Init(j, i);
                DWORD start = GetTickCount();
                while (1)
                {
                    VectorInt left, right;
                    guess.GetBestInput(left, right);
                    int fd = guess.CheckFeedback(left, right, t);
                    int rz = guess.RemoveImpsAns(fd);
                    if (rz == 1)
                        break;
                }
                time += GetTickCount()-start;
            }
            time /= j*2;
            printf("方法：%d\t球数：%d\t平均时间：%d\n", i, j, time);
        }
    }
    
    return 0;
}
#endif

这是测试结果：
方法：0 球数：12        平均时间：0
方法：0 球数：13        平均时间：0
方法：0 球数：14        平均时间：0
方法：0 球数：15        平均时间：0
方法：0 球数：16        平均时间：0
方法：0 球数：17        平均时间：1
方法：0 球数：18        平均时间：1
方法：0 球数：19        平均时间：1
方法：0 球数：20        平均时间：5
方法：0 球数：21        平均时间：5
方法：0 球数：22        平均时间：5
方法：0 球数：23        平均时间：6
方法：0 球数：24        平均时间：6
方法：0 球数：25        平均时间：6
方法：0 球数：26        平均时间：27
方法：0 球数：27        平均时间：26
方法：0 球数：28        平均时间：25
方法：0 球数：29        平均时间：167
方法：0 球数：30        平均时间：162
方法：0 球数：31        平均时间：157
方法：0 球数：32        平均时间：171
方法：0 球数：33        平均时间：165
方法：0 球数：34        平均时间：163
方法：1 球数：12        平均时间：0
方法：1 球数：13        平均时间：0
方法：1 球数：14        平均时间：0
方法：1 球数：15        平均时间：0
方法：1 球数：16        平均时间：0
方法：1 球数：17        平均时间：0
方法：1 球数：18        平均时间：0
方法：1 球数：19        平均时间：0
方法：1 球数：20        平均时间：0
方法：1 球数：21        平均时间：0
方法：1 球数：22        平均时间：0
方法：1 球数：23        平均时间：0
方法：1 球数：24        平均时间：0
方法：1 球数：25        平均时间：0
方法：1 球数：26        平均时间：0
方法：1 球数：27        平均时间：0
方法：1 球数：28        平均时间：0
方法：1 球数：29        平均时间：0
方法：1 球数：30        平均时间：0
方法：1 球数：31        平均时间：0
方法：1 球数：32        平均时间：0
方法：1 球数：33        平均时间：0
方法：1 球数：34        平均时间：0


这里是全部代码