专栏首页ACM算法日常芯片测试(分治)- 例题

芯片测试(分治)- 例题

转载自知乎

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

问题描述:

给定n个芯片,(1)好芯片比坏芯片至少多一片;(2)两个芯片可以互相测出对方的好坏,好芯片可以测准,坏芯片不一定测准。从中选出一片好芯片。

思路分析:

角度一:随机选一片芯片,与其他芯片比较:

当芯片总数是偶数:好芯片数目大于等于 n/2+1 , 如果选中的芯片是好芯片,剩下的超过一半( n/2) 报好(结果一) ,如果选中的芯片是坏芯片,超过一半的报坏(结果二);结果不是一半(及以上)报好就是一半(及以上)报坏,因此可以检测出选中的单芯片的好坏;

如果选中的芯片是奇数:好芯片数目大于等于 (n+1)/2 ,如果选中的是好芯片,剩下的至少芯片一半报好;如果选中的是坏芯片,超过一半报坏;结果不是一半(及以上)报好就是一半(及以上)报坏,因此可以检测出选中的单芯片的好坏;

仔细想一想,由于好芯片比坏芯片多,抽出一片好芯片,剩下的至少还有一半好芯片,根据他们测定的结果,可以得出判断;抽出一片坏芯片,那剩下的好芯片就更多了,也可以得出判断。

因此,采取蛮力算法:随机选一片,判断其好坏,如果是坏的,重复进行;最坏的情况是每一片都与其他片比较一遍,需要 O(n^2) 。

角度二:随机的两片比较有四种可能:

A片     B片
B好     A好   要么都好,要么都坏     
B好     A坏   至少坏一片
B坏     A好   至少坏一片 
B坏     A坏   至少坏一片

每种情况考虑四种情形:AB都好、 AB都坏 、一片好一片坏

第一种情况:设AB都好吻合,设AB都坏吻合,一片好一片坏矛盾,所以要么都好,要么都坏;

第二种情况:AB都好矛盾,AB都坏吻合,A坏B好吻合,A好B坏矛盾,所以至少坏一片;

其他两种情况同理,也是至少坏一片;

如果我们给芯片随便两两配对测量(先假设芯片数是偶数),都报好的任选一片,其他情况的全不选,从而选出新子集,如果新子集还满足原来集合的性质,就可以逐步缩小筛选的范围,不用一片一片去比。这时满足表达式 W(n) = W(n/2) + O(n) ,可以看出这个就是典型的分治算法——寻找相同的子问题,将原来的大问题分解后递归求解,复杂度为W(n) = O(n)。

新子集还满足原来集合的性质?

原来集合的性质:好芯片比坏芯片多;由于选取的芯片组有两种类型:都是好的,都是坏的,可以知道好的芯片组的数目多于坏的芯片组的数目,因此子集中好芯片还是比坏芯片多,因此满足条件。

那如果芯片数目是奇数怎么办?

当遇到芯片数目是奇数时,将轮空的(未分到组的)芯片采取角度一方法判断,好的话,结束程序,坏的话就丢弃该芯片。

伪码算法:

n <- 芯片总数
while n > 3 then:
    将 n 分为 n/2(默认向下取整) 组
    if n是奇数 then:
         轮空的芯片检测其好坏,好的话结束程序,坏的话丢弃
    对每个分组进行元素抽取,测试结果都好的随机抽一个,其余的丢弃
    n <- n/2
    if n == 3 then:
        ‍随机选取一片芯片比较一次
        if 都好 then 选择一片
        els‍e 选择剩下的一片
    if n<3 then:随机选择一片
        return

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 四两拨千斤,GCC编译器(同余模) - HDU 3123

    同余这一属性看起来简单,然而却是数论中极为重要的概念。与之相关的公式和定理更是纷繁芜杂,如果不是数学背景的童鞋,恐怕很难深入去钻研所有的知识。

    ACM算法日常
  • 浅谈ACM算法学习与有效训练

    一、什么是有效地训练?   很多ACMer入门的时候,都被告知:要多做题,做500多道就变牛了。其实,这既不是充分条件、也不会是必要条件。   我觉得一般情...

    ACM算法日常
  • 编程天才楼天城的科幻时代:我为什么来广州创业无人车

    进入CB Insights发布的全球100家最有前景的AI创业公司,小马智行(Pony.ai)的联合创始人、首席技术官楼天城看上去也很淡然。毕竟,对于这个曾经的...

    ACM算法日常
  • 中国芯突围战,是科技史上最悲壮的长征

    “我们害怕华为站起来后,举起世界的旗帜反垄断。” 多年前,时任微软总裁史蒂夫・鲍尔默、思科 CEO 约翰・钱伯斯在和华为创始人任正非聊天时都不无担忧。

    新智元
  • AI芯片发展的前世今生

    现代电子产品和设备在诸如通信 、娱乐 、安全和 医疗保健等许多方面改善了我们的生活质量 ,这主要是因为现代微电子技术的发展极大地改变了人们的日常工作和互动方式。...

    AI科技大本营
  • 为什么俄罗斯没有高端芯片,却能造出一流武器?

    自从美国封锁对中国出口芯片这一消息传出,芯片成为大家经常谈论的话题,今天小编看到一篇文章是谈论俄罗斯没有高端芯片,却能造出一流武器,发来与大家分享。

    钱塘数据
  • 自动驾驶寒冬与否,关键看“芯”

    前不久,谷歌Waymo公司的CEO John Krafcik在一次大会上承认自动驾驶普及还需要很久的时间,因为要在任何天气和情况条件下都能实现自动驾驶,这种技术...

    镁客网
  • Python|python芯片检测

    有n(2≤n≤20)块芯片,有好有坏,已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时,能正确给出被测试芯片是好还是坏。而用坏芯片测试...

    算法与编程之美
  • 明日之争:中国会成为下一个芯片帝国吗?

    《经济学人》最新的封面文章,题为《芯片大战》(Chip wars),认为21世纪对技术的争夺,包括从人工智能到网络设备等,主战场在半导体工业。

    新智元
  • 国产芯片失落的十年

    “现在一定是国产芯片最好的时候,”孙超这样强调,“会有很多人跟你说,国产芯片产业有各种各样的问题,但我要告诉你,国产芯片被低估了。”

    镁客网

扫码关注云+社区

领取腾讯云代金券