称球问题——经典智力题推而广之三（五）

《称球问题——经典智力题推而广之三（五）》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、称球问题——经典智力题推而广之三（五）五、四十个球的例子　　　　　　　　最后我们来解决一下40个球，没有标准球的问题。我们知道　　40=(34-1)/2　　所以我们可以称4次找出坏球，但是因为没有标准球，就不一定能知道坏球的轻重。　　　　顺便先考虑13个球，另有一标准球的问题。　　13=称球问题——经典智力题推而广之三（五）五、四十个球的例子　　　　　　　　最后我们来解决一下40个球，没有标准球的问题。我们知道　　40=(34-1)/2　　所以我们可以称4次找出坏球，但是因为没有标准球，就不一定能知道坏球的轻重。　　　　顺便先考虑13个球，另有一标准球的问

2、题。　　13=(33-1)/2　　所以称3次可以找出坏球，因为有标准球，我们还可以同时知道坏球的轻重。　　　　根据上一节的证明过程，这时我们要把这13个球分为3堆：　　第一堆：1-5　　第二堆：6-9，再加上标准球s　　第三堆：10-13　　我们把第一和第二堆小球放在天平左右端进行第一次称量。　　　　如果是左边重，那么要么是第一堆1-5号球中有一个是坏球，而且它比标准球重，要么是第二堆6-9号球中有一个是坏球，那么它比标准球轻。用结论1来解决的问题，第三节末尾我们处理过27个球的问题，9个球的问题就是小菜了：　　　　　　

3、--右--(4重)　　　　

4、--右

5、--(3;4)

6、--平--(6轻)　　

7、

8、--左--(3重)　　

9、　　

10、

11、--右--(8轻)　　(1-2,6;3-4,7)

12、--平--(8;9)

13、--平--(5重)　　

14、

15、--左--(9轻)　　

16、　　

17、

18、--右--(2重)　　

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

20、--平--(7轻)　　

21、--左--(1重)　　　　　　　　如果是右边重，那么和上面的情况对称，只要把策略树中的“左”和“右”互换，“轻”和“重”互换即可。　　　　　　如果平衡，那么就化为4个球有一个标准球2次称出的问题。虽然还可以往下照葫芦画瓢地递归一次，不过4个球的情况就太简单了，所以直接写出策略树：　　　　

22、　　

23、--右--(10轻)　　　　

24、--右--(10;11)

25、--平--(12重)　　

26、

27、--左--(11轻)　　

28、　　

29、

30、--右--(13轻)　　(10,11;12,s)

31、--平--(13;s)

32、--平--()　　

33、

34、--左--(13重)　　

35、　　

36、

37、--右--(11重)　　

38、--左--(10;11)

39、--平--(12轻)　　

40、--左--(10重)　　　　　　　　把左中右三个分支拼起来我们就得到13个球有一标准球称3次的策略树：　　　　　　　　

41、--右--(1轻)　　　　

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

43、--平--(7重)　　

44、

45、--左--(2轻)　　

46、　　

47、

48、-

49、-右--(9重)　　

50、--右--(1-2,6;

51、--平--(8;9)

52、--平--(5轻)　　

53、3-4,7)

54、

55、--左--(8重)　　

56、

57、　　

58、

59、

60、--右--(3轻)　　

61、

62、--左--(3;4)

63、--平--(6重)　　

64、

65、--左--(4轻)　　

66、　　

67、

68、--右--(10轻)　　

69、

70、--右--(10;11)

71、--平--(12重)　　

72、

73、

74、--左--(11轻)　　

75、

76、　　

77、

78、

79、--右--(13轻)　　(1-5;

80、--平--(10,11;

81、--平--(13;s)

82、--平--()　　6-9,s)

83、12,s)

84、

85、--左--(13重)　　

86、

87、　　

88、

89、

90、--右--(11重

91、)　　

92、

93、--左--(10;11)

94、--平--(12轻)　　

95、

96、--左--(10重)　　

97、　　

98、

99、--右--(4重)　　

100、

101、--右--(3;4)

102、--平--(6轻)　　

103、

104、

105、--左--(3重)　　

106、

107、　　

108、

109、

110、--右--(8轻)　　

111、--左--(1-2,6;

112、--平--(8;9)

113、--平--(5重)　　3-4,7)

114、

115、--左--(9轻)　　

116、　　

117、

118、--右--(2重)　　

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

120、--平--(7轻)　　

121、--左--(1重)　　　　　　现在可以考虑40个球，无标准球的问题了。根据上一节的证明过程，我们首先拿掉第40号球，使之变为39个球的问题。

122、然后我们把这39个球分为3堆：　　第一堆：1-13　　第二堆：14-26　　第三堆：27-39　　把第一和第二堆小球放在天平左右端进行第一次称量。　　　　如果是右边重，那么要么是第一堆1-14号球中有一个是坏球，而且它比标准球重，要么是第二堆15-27号球中有一个是坏球，那么它比标准球轻。这恰好是第三节末尾我们解决过的例子！这个策略树分支我们可以完全拷贝过来。　　　　如果是左边重，那么和上面的情况对称，只要把策略树中的“左”和“右”互换，“轻”和“重”互换即可。　　　　如果平衡，那么问题转化为本节开始的13个球，有一标准球的问题，上面的策略树也可拷贝过来，

123、只是要把原来的1-13号球和这里的27-39号球一一对应。