此贴为求beyondyf大哥的算法！当然也欢迎其他高手

呵呵，这个公式如何推导出来，等待中。
若能给出配合公式的推导方法，更妙。
偶根据自己的方法，也给出一个公式，抛砖引玉。
ln(3N - 9)/ln3

N=3

哦，又开了一贴。看到原贴结了我还以为你不想知道这个问题了呢

敝姓杨，以后叫杨大哥就好了。

关于这个问题的解决策略也不是我发现的。先简单做点科普介绍。

解决这个问题的货叫米切尔.费根鲍姆（M.J.Feigenbaum），此人是美国物理学家，因在混沌学领域发现普适常数而著名，此常数后被命名为费根鲍姆常数。

之所以这里我写他的全名是为了防止和另一个叫爱德华.费根鲍姆的货搞混了。他俩是兄弟，后者是人工智能领域大师级人物。唉，这一家子全是天才。

一聊这两个家伙我就兴奋。言归正传，说说这称球的事。

球的状态是通过天平的状态来表达的。只有当天平的状态数达到或超过球的状态数才能区分开每一个球。

天平每次称量的状态有三种，平衡、左倾、右倾。

对于第一次称量，由于不知道坏球是比好球轻还是重，所以它的左倾和右倾只能传达一个意义（球在天平上）。

在之后的称量中，左倾和右倾可以与第一次的倾斜方向作参照，这时它们就有意义了。

如果倾斜方向没变说明坏球还在原来的盘子里，如果倾斜方向改变说明坏球被换到了另一个盘子里。

所以称1次我们可以得到2种状态（平衡，不平衡）

称2次。当第1次称量为平衡时得到2种状态（平衡，不平衡），当称1次衡量为不平衡时得到3种状态（平衡，左倾，右倾）。共可得到2 + 3 = 5种状态。

以此类推，称量n次，可以得到2 + 3 + 3^2 + 3^3 + ... + 3^(n - 1) = (3^n + 1) / 2 种状态。

这里需要说明一个细节，上面状态数的计算前提是已知了好球的重量，或者说我们有一枚额外的好球作参照。

这样，我们才能在第一次称量中获得两种状态。这意味着我们可以在两个球中找出那个坏球。

找法是将参考球与那两个球中的任意一个放在天平上。如果天平平衡，则没放上去的那个是坏球；如果不平衡，则放上去的那个是坏球。

但现在的情况是我们不知道好球的重量，或说我们没有那枚参考球。

而为了获得好球的重量，或者说明确地知道某个或某些球是好球，这需要消耗一次称量。

所以实际称量n次能获得的状态数是 (3^n + 1) / 2 - 1 = (3^n - 1) / 2

一个例子就是，只进行一次称量能从几个球里找出那个坏球。答案：1个。

把上面的公式看成一个函数，其反函数就是m个球可以用多少次称量找出来了。


以上就是找球这一问题的理论分析，最后说说在以上理论的支持下具体怎么找吧。

第一次，在天平左右盘各放(3^(n - 1) - 1) / 2 个球。

如果平衡，说明天平上的都是好球。其余的球继续。

如果不平衡，说明坏球在天平上，天平外的都是好球。

下一次称量，将天平上的球任取1/3下来，剩下的任取一半交换位置。

如果平衡，说明坏球在取下来的1/3里。（注意要记住这些球每个原先放在天平的哪一边了）。

如果不平衡，如果倾斜方向没变，说明坏球在天平上没交换位置的那一半里。

如果倾斜方向改变，说明坏球在天平上交换了位置的那一半里。

如此重复，任意N个球都可在ln(2N + 1)/ ln3次内一定找到那个坏球。

收到的鲜花

• g270615179 于 2012-04-01 09:15 送鲜花  5朵   附言：好文章
• q332010372 于 2012-04-01 17:58 送鲜花  5朵   附言：好文章

一个字——强。
beyondyf此道高手啊
能否留下联系方式（QQ||MSN||Email），一起聊聊？

楼上过奖了。不敢称高手。只是知道而已。
据说当朋友问费根鲍姆这个问题时，那家伙几乎连想都没想就给出了答案。呵呵，天才就是天才。
我第一次见到这个问题时也是在上大学，当时花了好几天才搞定，还挺为自己的智商自豪的。
但后来看了那家伙的故事后，不管是真是假，太受打击了。

我来这里的一个愿望也是能在芸芸中发现几个费根鲍姆这样的天才或者高手，并努力结交之，以提高自己的能力。

QQ已经几乎不用了。留个邮箱吧，欢迎交流。beyond.yfang@

用分冶法思想解决的吗

强大！！！！！！！！！！！！！

亲，杨大哥（一直以为laoyang这id是杨大哥）
感谢杨大哥的回答，这里先说声抱歉，补了两天课，时间不是很多！上次那个贴已有坛友解决了，不得不结贴啊，所以另开一贴。
看过杨大哥最近的发帖和回帖，不得不佩服杨大哥的姿势渊博，就这问题而言，我想论坛里面知道此公式及其证明的也不多吧！
小弟现在大一，学了c，正在学c++，平时课余时间也不少，想自学又没有方向，冒昧请杨大哥说说你的学习经历，借小弟参考参考，我想很多坛友也想知道吧

我的学习经历还真不知道该怎么说。就是喜欢什么学什么，需要什么学什么。

最初学的是BASIC语言，准确地说是GW-BASIC。原因——当时我只有台学习机，游戏卡带太少玩腻了。学习机的说明书里讲了点BASIC语言入门知识，觉得很好玩，就学了，天天在电视机上画星星玩。当时我13岁，在上初中。

之后用BASIC编了些小游戏在学校机房给同学们炫耀。但每次都得带着源代码。我有一个很要好的朋友。他很聪明，每次看完我的代码他就学会了，然后添上自己的功能拿给我看。当时这让我很不爽。决定学一门编译型语言，于是开始学习C语言。这时我15岁，上高一了。

现在常看见很多人说谭浩强的书多么多么烂。我对这种看法表示遗憾。我就是用谭爷爷的一本薄薄的《C语言简明教程》学的C语言。没人指导，但也没遇到现在论坛里刚入门的朋友们反复问的问题。因为从来没觉得那是问题。因为家里没电脑，所以为了上机经常需要去和学校管理机房的老师软磨硬泡。而大部分时间我只能在作业本的背面用笔写代码，在脑子里调试。

随着C学习的深入，我觉得有必要好好了解一下计算机的结构。于是买了本《8086汇编语言》。16开，蓝色封面，有些竖条纹，已经丢了。
在书店发现一本《数据结构》。没错，就是严蔚敏的那本绿书。太喜欢了，买下来开始学习。
不过受当时的知识所限，高中时期，我只看懂了前面几章的内容，大概学到队列部分。

进入大学给我的感觉就是，自由。我可以做我想做的任何事情了，这里提供了我想要的硬件条件。学校图书管有大量的书可以看，有老师可以问（从没问过计算机系的老师），我也有了属于自己的第一台计算机。这时我的编程水平也突飞猛进，并在个人兴趣的引导下，逐渐倾向于算法的学习。

我学编程的目的就是为了让计算机服从我的指挥实现我的想法。语言是我编织梦想的工具。想过以此为业，但原因不是为糊口。是为了能全身心的投入我的梦想。

现在毕业许久了，命运的车轮并没有按我设想的方向前行。有段时间我很失望、空虚，觉得正在离自己的理想越来越远。后来逐渐调整了自己的看法。人生不如意事十之八九，哪能事事都按自己的想法来。稍有困难就放弃，枉世为人。换个角度考虑，现在衣食无忧，妻子贤惠、父母健康、工作也不是很累，正是有时间和精力来为理想而努力的时候。

尽人事、听天命。现在我已经不再考虑能不能完成我的理想，只想着为了我的理想现在能做点什么。并且现在我也很享受这个过程

人活着，是要有点追求的。不要太在意结果能得到多少，其实这个过程本就是一份丰厚的收获。现在比较遗憾的就是年轻时用功还是不够，不过现在努力还不算晚。

再过一个月就该庆祝我的三十岁生日了。谨以此文献给年轻的朋友。

祝你们二的开心、二的痛快。但玩够之后还是要尽量多学习、多积淀你的能力。

这样当你二过多后，到三时，会少一些遗憾