用信息论构造出称球问题的解.pdf

《用信息论构造出称球问题的解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用信息论构造出称球问题的解赵明达提要：本文用信息论推导出称球问题的解，并构造了的递推操作的称量办法，彻底解决了任意个球的称球问题。关键词：称量信息量概率递推经典的称球题目是这样的：“十二个外表相同的球中有一个坏球，它的重量和其它十一个好球不同，现在有一台没有砝码的天平，问需要称几次就能确保找出那个坏球”（一）十二个球称几次做过这道题目的人知道，答案是3次。不是太难，我们用图论中的策略树将称法记录如下：称3次，从12个球里找到坏球，并知道坏球的轻重：

2、--右--(1轻)

3、--右--(1;2)

4、--平--(8

5、重)

6、

7、--左--(2轻)

8、

9、

10、--右--(6重)

11、--右--(1,2,7;

12、--平--(5;6)

13、--平--(4轻)

14、3,8,9)

15、

16、--左--(5重)

17、

18、

19、

20、

21、--右--(3轻)

22、

23、--左--(3;9)

24、--平--(7重)

25、

26、--左--(×)

27、

28、

29、--右--(9轻)

30、

31、--右--(9;10)

32、--平--(11重)

33、

34、

35、--左--(10轻)

36、

37、

38、

39、

40、--右--(12重)(1-4;5-8)

41、--平--(9-10;

42、--平--(1;12)

43、--平--(13轻,13重)*

44、11，1)

45、

46、--左--(12轻)

47、

48、

49、

50、

51、

52、--右--(10重)

53、

54、--左--(9;10)

55、--平--(11轻)

56、

57、--左--(9重)

58、

59、

60、--右--(×)

61、

62、--右--(3;9)

63、--平--(7轻)

64、

65、

66、--左--(3重)

67、

68、

69、

70、

71、--右--(5轻)

72、--左--(1,2,7;

73、--平--(5;6)

74、--平--(4重)3,8,9)

75、

76、--左--(6轻)

77、

78、

79、--右--(2重)

80、--左--(1;2)

81、--平--(8轻)

82、--左--(1重)说明：1、*号所在的一行对应十三个球的情形，留待后面分析13个球的时候使用，现在可以不管。2、树的每一处分

83、叉就是一次称量，它有三个分支，分别标注了“右”、“平”和“左”，表示称量的结果为“右重”、“平衡”和“左重”。3、(1,2,3,4;5,6,7,8)或者(1-4;5-8)表示“将1-4号放在左边，5-8号放在右边”这样的一次“称量”。无疑，天平两端球数不等时的称量没有意义。4、(1重)和(2轻)表示“1号是坏球，且较重，其他球都正常”和“2号是坏球，且较轻，其他球都正常”的最终结果；可以看出，在到达最终结果前经过了几个分叉，便是称量的次数。这个结果是反复尝试得到的，虽然直觉上三次应该是最低了，但我们终究不

84、能百分之百的确定，我们还是会问，两次能搞定吗？或者我们想，十三个球里面找一个坏球，三次可以吗？十四个呢？……，或者问，十个球里面找一个坏球要几次呢？二十个、四十个呢？N个呢？……还有，称三次最多可以从几个球里找到唯一的那个坏球？四次呢？五次、六次呢？M次呢？解这样的题目有规律可循吗？一般的，我们要解决以下问题：给定任一自然数N，⑴找出N个球称球问题所需的最小称量次数；⑵给出最小次数称球的具体方法。这道题的解决无非是要获得“十二个球中哪一个球是坏球的”的信息，是要确定一个事件集合里最终哪一个事件发生的过程。

85、下面，我们用信息论的几个基本原理，试着分析一下。（随便找一本介绍有关香农信息论的书，都会有下面的内容，对信息论有所了解的，可以跳过下面一段）香农在他创立的信息论中，将信息定义为对“事物不确定性的消除”，消除了多少不确定性，用信息量来衡量。一个事件集合中究竟发生哪一件事情就是不确定的，每个事件的发生都有一定的概率，比如明天天气可以由“晴、多云、阴、雨”几个事件组合而成，最终哪种天气会出现，今天是不确定的，今天只是知道明天各种天气的发生概率，并且知道所有各种天气出现的概率总和为1。我们来看看事件集合中发生某事

86、件的信息大小和该事件发生的概率之间的关系。某事件发生的概率越小，该事件发生后给我们的“震撼”越大。比如“明天发生、不发生地震”这一事件集合中，明天不发生地震的概率远大于发生地震的概率，所以真的明天发生了地震，那我们所获得的信息量就比没有发生地震要大的多。此外，信息具有可加性，“今天地震了又下雨”给我们的信息应该是今天发生了地震和今天下雨两个事件的信息的和，而两个事件同时发生的概率又是这两个事件各自发生概率的乘积，基于此，香农将某一“发生概率为P”的事件的出现带来的信息量定义为1/P的对数，即log1/P。

87、基数r的不同，使得信息r量可以有不同的单位，基数r=2，单位就是比特。比如抛一枚硬币结果是“国徽向上”的信息量是log1(12)=1比特。2好，我们仅用这一点信息理论，就可以解决上面提出来的那个称球问题了。我们的想法是，如果确定12个球当中的坏球需要的信息量是A，而从每次天平的称量结果可以至少获得的信息量是B，那不小于A/B的整数就应该是所需的最小的称量次数了。在称以前，十二只球的任何一个都可能是坏球，而且概率一样，都是1/1