小球比较问题的通解 (100分)

  • 主题发起人 主题发起人 MrMengyi
  • 开始时间 开始时间
M

MrMengyi

Unregistered / Unconfirmed
GUEST, unregistred user!
很久前,大家讨论过 在13个小球或者12个小球里找出一个不同的小球 的问题
过年的时候我归纳了一下
昨天没事,就把程序也写了一下
基本是通过了
在这里报告一下
各位有兴趣的可以帮忙看看
我的解法的正确性
 
问题简单描述(具体的大家应该都很清楚了吧):
A (3^n-1)/2 和 B(3^n-3)/2
这两个式子是表示小球个数的
A式中的小球比B式中多一个
13个球是A的情况
12个球是B的情况
A的情况下,在n次可以找到不同的坏球,但可能不能发现这个小球是偏重还是偏轻
B的情况下,在n次可以找到不同的坏球,而且可以知道这个小球是偏重还是偏轻
 
小球的个数已经用公式表示出来了
下面再写几个简单的公式:
C、3^n个小球情况,在知道坏球偏重还是偏轻时,n次可以找到这个球,而且能确定这个坏球是偏重还是偏轻。
做法是平均分成三份,下面我想不需要详细写了,这个是小学智力题。
 
D、三组小球,数量分别是x (3^n-1)/2,y (3^n-1)/2,s (3^(n-1))
其中,最后一组(s)我称为辅助小球,数量要求大于(3^(n-1)),里面的小球必须确定是标准的。而且还要确定的是x组一定比y组重(实际上知道两者轻重关系即可,但是确定了轻重关系,下面好描述)。
在这样的情况下,n次可以找出那个坏球
方法是:
x中取(3^(n-1))个球给y,y取下(3^(n-1)),将s加到x上。再次比较。
1、如果x仍旧重,那么坏球在x和y中未移动位置的小球里,
(3^n-1)/2 - (3^(n-1)) = (3^(n-1)-1)/2
可见,这是一个递归的问题。
由于辅助球足够,x重于y,还是D类问题。
2、如果天平平衡了,说明目前天平上的小球都是好的,所以从y移出的(3^(n-1))个小球里有坏球,而且这个坏球是偏轻的。
问题转化成为:(3^(n-1))小球里有一个偏轻的球,按照C类问题,在n-1次里是可以解决的。
3、如果天平变成y重了,说明从x移动到y的(3^(n-1))小球里有一个偏重的球,按照C类问题,在n-1次里是可以解决的。
最后,D类问题的递归结束条件,当n=1时,(3^n-1)/2 = 1,用辅助小球与其中一个比较,如x,如果平衡,y里的就是坏球,且坏球轻。如果x重,那么x里的是坏球,且坏球重。
 
E、有(3^n+1)/2个小球,有辅助球(3^(n-1))个
在n次内可以解决
做法是:
把(3^n+1)/2个小球分为两组(3^(n-1))和(3^(n-1)+1)/2
(3^(n-1)) + (3^(n-1)+1)/2 = (3^n+1)/2
用(3^(n-1)) 与辅助的标准小球比较
1、平衡,转化为E类递归问题
2、不平衡,转化为C类问题
递归结束条件:
n=1时,(3^n+1)/2 = 2,如果碰巧那到的是坏球与辅助球比较,可以得到坏球是否偏重
,否则就只能找到这个坏球
 
现在来解决A类问题
(3^(n+1)-1)/2 = (3^n-1)/2 + (3^n-1)/2 + (3^n+1)/2
分成这样的三组
A (3^n-1)/2
B (3^n-1)/2
C (3^n+1)/2
比较A和B
一样重的话,转为E类问题,再化n次解决,一共需要n+1次
A和B不一样重的话,转化为D类问题一共也需要n+1次
这与式子里的(3^(n+1)-1)/2一致
于是,这个问题解决了
 
F、(3^n-1)/2个小球,有辅助球(3^(n-1)),可以在n次内解决
做法类似与E类问题
把(3^n-1)/2个小球分为两组(3^(n-1))和(3^(n-1)-1)/2
(3^(n-1)) + (3^(n-1)-1)/2 = (3^n-1)/2
用(3^(n-1)) 与辅助的标准小球比较
1、平衡,转化为F类递归问题
2、不平衡,转化为C类问题
递归结束条件:
n=1时,(3^n-1)/2 = 1,这个时候有一次比较机会,已经在次数限制前找到坏球了,可以再次比较得到坏球的重量情况。
 
现在来解决B类问题
(3^(n+1)-3)/2 = (3^n-1)/2 + (3^n-1)/2 + (3^n-1)/2
平均分成三组
A (3^n-1)/2
B (3^n-1)/2
C (3^n-1)/2
比较A和B
一样重的话,转为F类问题,再化n次解决,一共需要n+1次
A和B不一样重的话,转化为D类问题一共也需要n+1次
这与式子里的(3^(n+1)-3)/2一致
于是,这个问题也解决了
 
佩服,顺便接分
 
高手,看了你们,我都不想学了,
我们这些小菜哪有这么高深的功夫啊!
路漫漫,其修远兮……
 
佩服,我做12各小球 就费了半天得劲
 
多人接受答案了。
 
后退
顶部