天平比较找出轻球

用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的(条件是y个球中y-1个重量相等,其他一个轻),
使用x 次天平,最多可以从y 个小球中找出较轻的那个,求y 与x 的关系式。

其实,这是一个“三分查找问题”。

当y=3时,x=1(一次称重即可):

3个球中任选两个放到天平两端,若相等,则没称的那个是轻球。

若有一个轻,则轻的就是。

递归可以分析出来x = log3(y)。

 

2 thoughts on “天平比较找出轻球

  1. Sosi

    这个是决策树问题,你可以看http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/

    Reply

Leave a Reply to Sosi Cancel reply

Your email address will not be published. Required fields are marked *