Tag Archives: 比较

天平比较找出轻球

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

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

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

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

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

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