最新消息:发现真没时间折腾VPS,最近又换了个空间。呵呵

智力题:称石头(已知轻重)

题目: 给你8颗小石头和一架托盘天平。有7颗石头的重量是一样的,另外一颗比其他石头略重;除此之外,这些石头完全没有分别。你不得假设那颗重头到底比其他的石头重了多少。请问:最少要称量几次,你才能把那颗较重的石头找出来?

分析:
最开始我想的是用二分法,即先4颗一组,找到其重的一组,然后两颗一组,再找其重的一组,再一颗一组,找到重的一颗,用三次。

因为之前做过12颗珠子的题,想想如果3分怎么样?分析结果如下。

第一次,随便拿6颗分成两组放天平上称。
情况一:两边相等,则重的在剩下的两个里,再把剩下的两个放天平里称,找出重的一个即可(两次)
情况二:有一边重,则在重的一边的两个里再随便拿两个放天平上称。如果两边平衡,则重的是没没称的那个,否则是重的那个。

结论:
用三分法两次就能称出来了。

扩展:
对于已经轻重的称石头问题,一般都可以用三分法,其次数为 Math.ceil(log3(n)),即颗数小于或等于3的1次方(3),则需1次;颗数小于或等于3的2次方(9),则需2次;颗数小于或等于3的3次方(27),则需3次;……

转载请注明:宇托的狗窝 » 智力题:称石头(已知轻重)

发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址