注册 登录
编程论坛 数据结构与算法

真假硬币问题

上寒 发布于 2012-12-10 21:13, 645 次点击
各位朋友:
    最近我在研究算法,有一个经典问题——真假硬币问题,令我感兴趣;关于此问题的求解,我想咨询大家的意见。
    问题描述:
       有n枚硬币,其中有一个是假币,并且已知假币比真币轻,可以通过一架天平来任意比较两组硬币。请设计方案找出其中的假币,要求最坏情况下用天平的比较次数最少。
    谁能解决此题。希望通过动态规划解决
2 回复
#2
hymanxq2012-12-11 18:00
法一:二分法,每次都均分两份(如果多一个,也没事),再称;主要关注轻的一边。多次操作得解。
法二:三分法,和二分法道理一样,不过显然更加有效。
希望LZ采纳。
#3
fufengzhe2012-12-19 21:55
三分法比较好 效率要好点
1