您当前的位置: 首页 >  算法

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【算法分析与设计】寻找假币问题

星拱北辰 发布时间:2019-10-06 20:15:56 ,浏览量:0

问题描述:给出27枚硬币,它们的各种外观完全相同,但有一枚硬币稍重一点,是假币,我们只有一杆秤,试找到一种便捷的方法找出假币。

简单直接的思路是:直接从头到尾扫描遍历一趟,找出最大的即可。算法复杂度是 O ( N ) O(N) O(N),不符合我们这一问题“尽可能少比较次数”的宗旨。

可以优化上述思路。 容易想到二分查找,进而用将硬币分为2堆+1个,“折半”比较,找出那个特殊的假硬币。

还可以继续优化。 我们可以随机等分成三份,拿出两组比较,划分的对称性更强,查找也更快。 比如9枚硬币,二分最坏的情况是3次查找;三分

关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0601s