Java开发网 - 考考你的智力和编程能力

Topic: 考考你的智力和编程能力

1.考考你的智力和编程能力

Posted by: wsj
Posted on: 2004-01-03 14:04

有12个从外表上看一样大小，一样色的小球。但其中有一只重量和其他的不同
请用天平称三次。找出这个重量不同的小球！

给出思路, 且正确者 60％
给出程序, 结果不正确者不得分，结果正确者视“执行效率” 和“算法可读性” 60~100%

[可惜不能散分，就看看谁先做出来吧]

2.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: nothing Posted on: 2004-01-03 14:07 floater总板,给出过答案,可惜在水区被删除了.

3.Re:考考你的智力和编程能力 [Re: nothing]	Copy to clipboard
Posted by: wsj Posted on: 2004-01-03 14:13 中午在csdn看到的，这几天年终评定忙想看看别人写出来是什么样子，有空了我也会写一写 -------------- 有空写写代码，是我的休闲

4.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: jfml Posted on: 2004-01-03 16:03 １２个小球称３次的程序不难写吧难写的是Ｎ个小球称Ｍ次

5.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: jfml
Posted on: 2004-01-03 17:05

12个小球，ID依次记为a,b,c,d,e,f,g,h,i,j,k,l，其中不等重的小球定为x球。
1.将所有球分成3堆："a,b,c,d"，"e,f,g,h"，"i,j,k,l"
2.进行第一次称重："a,b,c,d"和"e,f,g,h"
2.1.如果等重，那么x在"i,j,k,l"内，将"i,j,k,l"这堆球分成三部分："i,j"，"k"，"l"，并将"a,b,c,d,e,f,g,h"中任一小球比如a，加入"k"，得到"k,a",然后进行第二次称重："i,j"和"k,a"
2.1.1.如果等重，那么x就是l球
2.1.2.如果不等重，那么x球存在于"i,j,k"中
2.1.2.1.如果"i,j">"k,a"，那么不是i或者j偏重，就是k偏轻。于是进行第三次称重："i"和"j"
2.1.2.1.1.如果等重，那么x就是k球，且偏轻
2.1.2.1.2.如果不等重,那么"i,j"中重的那个球就是x
2.1.2.2.如果"i,j"<"k,a"，那么不是i或者j偏轻，就是k偏重。于是进行第三次称重："i"和"j"
2.1.2.2.1.如果等重，那么x就是k轻，且偏重
2.1.2.2.2.如果不等重，那么"i,j"中轻的那个球就是x
2.2.如果不等重，那么x在"a,b,c,d,e,f,g,h"内
2.2.1.如果"a,b,c,d">"e,f,g,h"，那么说明要么x在"a,b,c,d"中，且x偏重，要么x在"e,f,g,h"中，且x偏轻
2.2.1.1.进行第二次称重："a,e,f"和"b,g,h"
2.2.1.1.1.如果等重，那么x必定存在于"c,d"中，只要进行第三次称重："c"和"d"，其中偏重的就是x球
2.2.1.1.2.如果不等重
2.2.1.1.2.1.如果"a,e,f">"b,g,h"，则说明不是a球偏重就是g或h球偏轻，那么进行第三次称重："g"和"h"
2.2.1.1.2.1.1.如果等重，那么x就是a球，且偏重
2.2.1.1.2.1.2.如果不等重，那么x就是g和h球其中偏轻的那个
2.2.1.1.2.2.如果"a,e,f"<"b,g,h"，则说明不是b球偏重就是g或h球偏轻，那么进行第三次称重："g"和"h"
2.2.1.1.2.2.1.如果等重，那么x就是b球，且偏重
2.2.1.1.2.2.2.如果不等重，那么x就是g和h球其中偏轻的那个
2.2.2.如果"a,b,c,d"<"e,f,g,h"，那么说明要么x在"a,b,c,d"中，且x偏轻，要么x在"e,f,g,h"中，且x偏重
2.2.2.1.进行第二次称重："a,e,f"和"b,g,h"
2.2.2.1.1.如果等重，那么x必定存在于"c,d"中，只要进行第三次称重："c"和"d"，其中偏轻的就是x球
2.2.2.1.2.如果不等重
2.2.2.1.2.1.如果"a,e,f">"b,g,h"，则说明不是b球偏轻就是e或f球偏重，那么进行第三次称重："e"和"f"
2.2.2.1.2.1.1.如果等重，那么x就是b球，且偏轻
2.2.2.1.2.1.2.如果不等重，那么x就是e和f球其中偏重的那个
2.2.2.1.2.2.如果"a,e,f"<"b,g,h"，则说明不是a球偏轻就是g或h球偏重，那么进行第三次称重："g"和"h"
2.2.2.1.2.2.1.如果等重，那么x就是a球，且偏轻
2.2.2.1.2.2.2.如果不等重，那么x就是g和h球其中偏重的那个

------------------------------------------------------------------------------------------------------
吐血半斤...............

6.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: javadd Posted on: 2004-01-03 17:51 厉害.

7.Re:考考你的智力和编程能力 [Re: jfml]	Copy to clipboard
Posted by: floater Posted on: 2004-01-04 01:52 jfml wrote: １２个小球称３次的程序不难写吧难写的是Ｎ个小球称Ｍ次 It's really just a N-problem, M can be derived from N. The deduction should be used with recursion, my guts feeling.

8.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: floater
Posted on: 2004-01-05 14:36

Here is java file for the solution.

Before you run, in the main method, change N and start to smaller number(<20).
N=start=12 is the case of the top post.

If you want to run any particular case, say 1000 balls, set both N and start to 1000, otherwise it will run all the cases in between.

I checked start=4 and N=12(4 balls, 5 balls, ... , 12 balls).

It's kind of rough, so use it, read it, in your own risk.

BallsOnScale.java (29.95k)

9.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: jfml Posted on: 2004-01-05 14:56 多谢F老大，学习学习

10.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: dog72
Posted on: 2004-01-05 18:25

大学时候解过这个问题，但是当时考虑不清楚如何由N导出最小的M和解的步骤。现在看来应该可以归约为一个NP完全问题，即在无数的解当中找到一个最优的解（类似于货郎担问题，找到最佳路径）。
没有仔细看floater的程序，不知道floater是否可以给出思路说明，看程序实在是下下策。
这个问题也一直困扰着我，但一直没有时间静下来真正的把它解开。如果不能够归约成NP完全问题，应该怎么归约？

11.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: floater
Posted on: 2004-01-06 03:59

This is really a deduction probelm, i.e., we start with N balls, and reduce to roughly N/3 balls in the next step. 3 is natural because we have 2 sides on the scale, plus the off scale(so 3 groups).

Because we don't know which group we are going to end up(considering all cases), we have to divide N balls as evenly as possible, e.g., 8 = 2,3,3; 12=4,4,4; 13=4,4,5; but not 13 = 3, 3, 7.(Otherwise, once we hit 7, it's too much to be handled). Among 3 groups, at least 2 of them have the same number of balls, so we put these two groups on the scale.

Let's say, we put groups g1 and g2 on the scale:
if g1=g2, then both g1 and g2 are good, g3 is bad. g3 has roughly N/3(maybe off by one, but we can afford that).

if g1>g2, then g1, g2 are bad, and g3 is good. g1 + g2 is 2/3 of N, so we have to reduce this to 1/3 of N. Here is the logic to do this: if the bad ball is in g1, since g1>g2, then the bad ball must be heavier; similarly, if the bad ball is in g2, since g1>g2, then the bad ball must be lighter. This is the first important fact, let's call it rule #1
We need another rule for the logic, rule #2, shown with the following example. Say, {1, 2}>{1', 2'} is true. Now we switch balls from one side to another, {1, 1'} ? { 2, 2'}. We switched 1', 2. 1, 2' unchanged.(mark as switched and unswitched). if {1, 1'}>{2, 2'}(notice this has the same direction >), then 1', 2 can not be the bad ball(use contradiction to prove this), so the switched ones are good, the unswitched ones are bad.
similarly, if {1, 1'}<{2, 2'}, then the switched ones are bad.
So the rule #2 is: If the same direction follows after a switch, the switched ones are good, unswitched ones are bad; If the direction is reversed after a switch, the switched ones are bad, unswitched ones are good.

Have said these two rules, now we reduce g1+g2 to the size of N/3, we just somehow remove a half of g1+g2(because g1+g2 is just 2*N/3). Now divide g1 to 2 groups g11, g12 and weigh them on the scale.
if g11=g12, then g11, g12 are good(so g1 is good), g2 is bad(of size N/3)<br>
if g11<> g12, then g11, g12 are bad(so g1 is bad), g2 is good.
So in either case we reduce to N/3. BUT, we used one more trial to get here. This is fatal, if we want to get the smallest number of trials. So we need to squeeze more info from this extra trial.
if g11=g12, we can't squeeze more on g2. But we could reduce g2 number by add some of g2 to g11 and g12. We don't want to add too many balls to g11, g12 either because that will make them too big later on.
if g11>g12, by rule #2, g12 is good since we switched g12 from left to right(well, we shift it really). So g11 is bad(and the bad ball is heavier). g11 is roughly 1/3 of g1 + g2.
Similarly if g11<g12, by rule#2, g12 is bad.<br>
Now with this size, it works.

The base cases (3 balls, 4 balls) are trivial, but complicated by nontrivial cases where if a "normal" ball is available.

12.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: floater
Posted on: 2004-01-07 12:28

Here is the revised version.

I tested N=4-100, 115-125, 360-370. For each N, vary the bad ball from 0 to N-1. However, my machine hangs when I try to run 3279.

The reason why I test these numbers are in the main().

I try to make code as much readable as possible, but ...

The full explanation is in the reference(in the top of the java file).

BallsOnScale.java (31.14k)

13.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: Biubiu Posted on: 2004-01-07 17:21 我小学五年级就开始做这样的题目了。

14.Re:考考你的智力和编程能力 [Re: Biubiu]	Copy to clipboard
Posted by: jfml Posted on: 2004-01-08 09:40 Biubiu wrote: 我小学五年级就开始做这样的题目了。知道您老人家牛Ｘ行了不？别光说不练啊，也给大伙讲解讲解？

15.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: floater Posted on: 2004-01-08 09:43 Well, one extension would be, without pointing out whether the ball is heavier or lighter, what's the minimum timies required to point out which ball is the defect one.

16.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: dog72 Posted on: 2004-01-08 14:09 我知道要分成3组，但这是人来解，人可以凭借经验和直觉。如果要机器来解，他可不知道这些。而且，也无法证明分3组是最佳的。机器应该是遍历所有可能的解，除非我们能够证明一上来分3组是最优的。

17.Re:考考你的智力和编程能力 [Re: dog72]

Copy to clipboard

Posted by: floater
Posted on: 2004-01-09 00:07

dog72 wrote:
我知道要分成3组，但这是人来解，人可以凭借经验和直觉。如果要机器来解，他可不知道这些。
而且，也无法证明分3组是最佳的。机器应该是遍历所有可能的解，除非我们能够证明一上来分3组是最优的。

It's proven that 分3组 is one of the optimal solutions(in the reference), in the sense that it will lead to the optimal number n(which is proven too).
Not only we did this, we also know, we may 分3组 with a slightly off the average(N/3)(a range). That's why we see 4 or 5 different solutions when N=12.

So neither human nor computers act on intuition at all, the solution is based on a proven algorithm(it can be proven by deduction).

I tried to simplify it further, that was version 1. But it didn't work well. So I just stick with the algorithm(version 2).

The idea is that we reduce the size to 1/3 everytime we use a scale, if we can't then we reduce the size to 1/9 by using the scale twice.

18.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: harvey007 Posted on: 2004-01-09 13:53 先将12个球分两组，称出哪边重就留下哪边，再将留下的那组6个分成三个一组，留下重的一组，再将重的这组随便拿两个放在天平上称，如果一致，则剩下的是特殊的，如果不一致，答案已经出来

19.Re:考考你的智力和编程能力 [Re: harvey007]	Copy to clipboard
Posted by: jfml Posted on: 2004-01-09 14:00 harvey007 wrote: 先将12个球分两组，称出哪边重就留下哪边，再将留下的那组6个分成三个一组，留下重的一组，再将重的这组随便拿两个放在天平上称，如果一致，则剩下的是特殊的，如果不一致，答案已经出来谁跟你说那个球是偏重的？

20.Re:考考你的智力和编程能力 [Re: wsj]

Copy to clipboard

Posted by: xiongjy
Posted on: 2004-01-10 21:32

给个算法，比较通用的
divide(3);//divide into 3 group:A,B,C
if(A1234=B1234)//once
then compare(C1234);
else if (A1234>B1234)then
{
if (A1+C234=B1+A234)//twice
then compare(B234);//lighter in B234
else if (A1+C234>B1+A234)
then compare(A1B1C1);//A1 is heavier or B1 is lighter
else if (A1+C234<B1+A234)
then compare(A234);//heavier in A234
}

21.Re:考考你的智力和编程能力 [Re: wsj]	Copy to clipboard
Posted by: dianzi Posted on: 2004-02-05 16:36 厉害.