IQrace 版 (精华区)

发信人: ciel (二分之根号五减一℃·冬天来啦), 信区: IQrace
标  题: 称小球问题终结----称球问题的几种常见类型
发信站: 哈工大紫丁香 (2003年10月25日14:33:31 星期六), 站内信件

0. N 个球，其中有一个坏球比别的球重，
   问用无砝码天平最多称几次可将坏球找出来
   (典型例子：27个球最多称3次)

1. N 个球，其中有一个坏球与别的球重量不同，
   问用无砝码天平最多称几次可将坏球找出来
   (典型例子：13个球最多称3次)

2. N 个球，其中有一个坏球与别的球重量不同，
   问用无砝码天平最多称几次可将坏球找出来，并知其偏轻还是偏重
   (典型例子：12个球最多称3次)

3. N 个球，其中有一个坏球与别的球重量不同，另有一个标准球，
   问用无砝码天平最多称几次可将坏球找出来
   (典型例子：14个球最多称3次)

4. N 个球，其中有一个坏球与别的球重量不同，另有一个标准球，
   问用无砝码天平最多称几次可将坏球找出来，并知其偏轻还是偏重
   (典型例子：13个球最多称3次)

[答案]

各题至多所需称球次数依次为：

0. ceiling(log3(N))

1. ceiling(log3(2*N+1))

2. ceiling(log3(2*N+3))

3. ceiling(log3(2*N-1))

4. ceiling(log3(2*N+1))

其中 ceiling 表示上取整，log3表示取以3为底的对数

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.228.216]