主题：[讨论][无聊][数学]纯属无聊的帖子
windy0will
[专家分：2300] 发布于 2010-07-20 12:07:00
无聊的时候想到的一个数学题目。
原题： 有12个球，其中有1个求的质量不同与其他11个，或轻或重，无法通过外表和手感感觉得出来，现有一天平。允许称量3次，考虑最坏情况，找出那个质量问题球。说出称量方法（有2中方法）。
可能原题比较简单，现把题目该为：
1. 如果有n个球，其他条件同上，问称量几次一定能找出那个质量问题球。
2. 如果有允许称量m次，其他条件同上，问最多可以从多少个球中找出问题球。
最后更新于：2010-08-01 13:36:00
回复列表 （共33个回复）
11 楼
windy0will [专家分：2300] 发布于 2010-07-21 11:13:00
那你怎么找这个最小数呢？
我觉的如果那样做的话，就是那个比较大小的函数怎么写，总不能直接象比较整数大小那样吧？更何况问题不是要找出那个质量不同的球，要求的是f(n)和g(n)
12 楼
elst5523183 [专家分：210] 发布于 2010-07-21 11:20:00
貌似这样模拟不了天平...
又试试这样...
一个数组中 只有一个元素是1(表示不正常的球),其余为0...
然后折半..算数组左边元素的和...右边元素的和...
假如左>右,
找左边.递归...
否则
右边,递归...
13 楼
elst5523183 [专家分：210] 发布于 2010-07-21 11:22:00
这个f(n)就是递归的深度...
14 楼
elst5523183 [专家分：210] 发布于 2010-07-21 11:25:00
...为了更好模拟天平....还要处理一下左右两边元素数量不相等的情况...
15 楼
windy0will [专家分：2300] 发布于 2010-07-21 11:31:00
感觉思路好像有点可以。
不过还是那句话，有很多情况要考虑，如下面称14个球：
第一次： 1 2 3 4 > a b c d（给球编号,这次结果说明问题球在这里面,剩下6个标准）
第二次: 1 b √ > a 2 3 （拿出4 c d这3个球，加入一个标准球,然后交换b和2,3）
如果称量结果如上面，那么问题球在 1和a 中
像上面的例子我们应该可以知道，直接来模拟天平在实现起来还是有点麻烦的
16 楼
elst5523183 [专家分：210] 发布于 2010-07-21 11:36:00
厄...原来我一直都理解错题目....
17 楼
windy0will [专家分：2300] 发布于 2010-07-21 11:41:00
不要花过多的时间来思考这个问题，我觉的这个问题还是比较难的。
不过平常可以用它来锻炼自己考虑问题的全面性，在穷举的时候要特别仔细。多思考 数学里面一些关于穷举法 也不错，即使不能解决问题。
18 楼
elst5523183 [专家分：210] 发布于 2010-07-21 11:46:00
我明天再想想..休息去了.:)
19 楼
bruceteen [专家分：42660] 发布于 2010-07-21 14:01:00
我没仔细想，先说说我的猜想吧
n个球，至多需要 n的开立方 次称重 // （比如12的开立方是2.289，所以需要3次）
n次称重，最多可以确定 n的三次方 个球
20 楼
windy0will [专家分：2300] 发布于 2010-07-21 15:23:00
那n=13，14呢？前者要3次，后者要4次。
我来回复
您所在位置：