最近给我们学校的一个提高班的招新考试出了一道笔试题，是关于常见的称球问题，大部分人都知道这题，也会觉得不屑一顾，如果我已经知道方法了我也许同样会这么觉得，但我总习惯站在一个旁观者的角度审查问题，就像这次出的这题，我就重新思考了一下这个问题，发现还是大有文章可做的，如果你肯花费１０分钟看下我下面这段文字，相信会对你有所帮助的。废话不多说了，让我们开始吧！这是一个历史悠久的问题：有n（n≥3）个球，其中一个是次品，你有一架天平，但没有砝码，现在要用最少的称量次数判断出次品来。

这个问题初看上去很简单，但细想起来还真不是一眼能看出来的，我是个非常喜欢物理学的童鞋，这里的让我想起大学物理里讲到过的熵，这是我最喜欢的概念，信息熵也是一个非常棒的想法，信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到 1948 年，香农提出了“信息熵”(shāng) 的概念，才解决了对信息的量化度量问题。当然这个量化也是做了一个标准的，在此就不提多了，要不然没人往下看了，呵呵。

总之，我想用信息熵的办法解决这个问题，当然其他办法也有很多，我只是表达自己观点。

这里有n个球，其中一个是次品，我们可以认为每个球都有可能是次品，而且一个球是次品还是正品的概率是等值的，都是1/2，由独立事件的概率乘法可知，任何一种情况的概率为1/2的n次方。假设我们手上有一个检验器，可以瞬间检验出一个球是否是正品，那么我们只需要用它来检验每一个球，直到出现次品为止，我们考虑最坏的情况，即检验到最后一个球才是次品，于是说明在进行检验前信息熵为S2 = K*ln（2的n次方）= log2（2的n次方）= n（bit），于是我想到可以用一串01串来代表这些球，一个球对应一个数，为0即正品，为1即次品。

我们知道称量一次会出现两种情况，平衡和不平衡。于是我们可以设法分别求出每一次称量之后的熵变，当然这里需要信息论的知识，因为我信息论了解不多，自然无法得出答案。呵呵~~其实我是没有尝试成功的，但不代表我永不会成功。我上网找了很久，也看了很多大家的解法，最后我看到了长沙雅礼中学的何林同学的解法，相当的不错，这里推荐给大家他的思路，当然，我也希望你们能像我一样，尝试自己能想到的各种方法，即使最后不能成功，也是有助于开拓思路的。

先给出我根据何林同学的计算公式写的一段简单代码，大家可以自己运行一下，玩一下嘛~~



    

  1. #include <stdio.h>   
    2. 

  2. 
#include <math.h>   

    3. 

  3. 
void main()   

    4. 

  4. {   
    5. 

  5. 
    int choose = 0;   

    6. 

  6. 
    int    m = 3;   

    7. 

  7. 
    int    n = 6;   

    8. 

  8. 
    int i, j;   

    9. 

  9. 
    int X = 1;   

    10. 

  10. 
    double temp1, temp2, temp3;   

    11. 

  11. 
    const double eps = 1e-10;   

    12. 

  12. 
    while (65534 &gt; (i++))   

    13. 

  13.     {   
    14. 

  14. 
        printf("Please choose set the number of\nblancing times or balls(1 for times,2 for balls): ");   

    15. 

  15. 
        scanf("%d",&choose);   

    16. 

  16. 
        if (1 == choose)   

    17. 

  17.         {   
    18. 

  18. 
            printf("Input the number of blancing times(number &gt;= 3 & <= 10): \n");   

    19. 

  19. 
            while (1)   

    20. 

  20.             {   
    21. 

  21. 
                scanf("%d",&m);   

    22. 

  22. 
                if ((3 &lt;= m) && (10 >= m))   

    23. 

  23.                 {   
    24. 

  24. 
                    for (j = 0; j < m; j++)   

    25. 

  25.                     {   
    26. 

  26.                         X *= 3;   
    27. 

  27.                     }   
    28. 

  28.                     X -= 1;   
    29. 

  29.                     X /= 2;   
    30. 

  30. 
                    printf("You can most blancing %d balls!!\nPlease test again\n\n\n\n", X);   

    31. 

  31.                     X = 1;   
    32. 

  32. 
                    break;   

    33. 

  33.                 }   
    34. 

  34. 
                else   

    35. 

  35.                 {   
    36. 

  36. 
                    printf("Wrong Input number,please input again: \n");   

    37. 

  37. 
                    continue;   

    38. 

  38.                 }   
    39. 

  39.             }   
    40. 

  40.         }   
    41. 

  41. 
        else if (2 == choose)   

    42. 

  42.         {   
    43. 

  43. 
            printf("Input the number of balls(number >= 4 & <= 65535): \n");   

    44. 

  44. 
            while (1)   

    45. 

  45.             {   
    46. 

  46. 
                scanf("%d",&n);   

    47. 

  47. 
                if ((4 &lt;= n) && (65535 >= n))   

    48. 

  48.                 {   
    49. 

  49.                     n = 2 * n + 1;   
    50. 

  50.                     temp1 = log(n);   
    51. 

  51.                     temp2 = log(3);   
    52. 

  52.                     temp3 = temp1 / temp2;   
    53. 

  53. 
                    printf("You can least blancing %d times!!\nPlease test again\n\n\n\n", (((temp3-(double)((int)temp3)) &lt; eps) ? (int)temp3 : ((int)temp3 + 1)));   

    54. 

  54. 
                    break;   

    55. 

  55.                 }   
    56. 

  56. 
                else   

    57. 

  57.                 {   
    58. 

  58. 
                    printf("Wrong Input number,please input again: \n");   

    59. 

  59. 
                    continue;   

    60. 

  60.                 }   
    61. 

  61.             }   
    62. 

  62.         }   
    63. 

  63. 
        else   

    64. 

  64.         {   
    65. 

  65. 
            printf("Wrong Input,please reinput!!!\n\n");   

    66. 

  66. 
            continue;   

    67. 

  67.         }   
    68. 

  68.     }   
    69. 

  69. 
    printf("That's enough!!!\n");   

    70. 

  70. } 
    71. 



下面是何林同学的部分思路，最后我附上他的整份文档和PPT以及他自己写的一端pascal程序，因为暂时没有经过他本人的同意就放这里了，所以希望大家不要用作不良用途~~


 


一个有趣的问题-分球问题


一个有趣的问题-分球问题


一个有趣的问题-分球问题


一个有趣的问题-分球问题


一个有趣的问题-分球问题