芯片测试(分治)- 例题

转载自知乎

分治算法的基本思想是将一个规模为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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

poj,zoj题目分类

ZOJ题目分类 初学者题: 1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241...

22690
来自专栏数据结构与算法

博弈论进阶之Every-SG

Every-SG 给定一张无向图,上面有一些棋子,两个顶尖聪明的人在做游戏,每人每次必须将可以移动的棋子进行移动,不能移动的人输 博弈分析 题目中的要求实...

35590
来自专栏xingoo, 一个梦想做发明家的程序员

【UML】——为什么要使用UML

以前一提到UML,就想到了复杂的流程图。很敬佩哪些想想就能画出整个系统的UML图的人,因为他们头脑中有整个软件架构的蓝图,这样在编写实现的时候,就会知道哪个...

27580
来自专栏CDA数据分析师

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

18960
来自专栏落影的专栏

程序员进阶之算法练习(十二)

前言 题目地址在HDU,输入对应的题号即可看到题目,在百度搜索hdu+对应的题号可以看到题解。 我简单的对题目难度进行了划分: 简单题:想法题,实现简单...

35470
来自专栏闰土大叔

太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考察...

12230
来自专栏数据结构与算法

P2066 机器分配

题目背景 无 题目描述 总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到...

29370
来自专栏PPV课数据科学社区

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有多重要,有人知道吗?我们...

30930
来自专栏Java架构师历程

从一道简单的面试题考查应聘者的技术能力

导读:在日常的招聘中,一个比较头疼的问题是,如何考察应聘者的技术能力,本文从一个简单的笔试题的角度,谈谈自己不成熟的经验。

12820
来自专栏各种机器学习基础算法

NLTK学习笔记(二)

词意消歧 在词意消歧中,我们要算出特定上下文中的词被赋予的是哪个意思。 思考存在歧义的词 serve 和 dish: (1) a. serve: help wi...

29970

扫码关注云+社区

领取腾讯云代金券