http://blog.csdn.net/shoulinjun/article/details/14128635
对于分治（Divide and Conquer)的题目，最重要是
1.如何将原问题分解为若干个子问题，
2.子问题中是所有的都需要求解，还是选择一部分子问题即可。
还有一点其实非常关键，但是往往会被忽视：分解后的子问题除了规模较原问题小之外，必须和原问题具有相同的性质。
在子问题的划分时，只有这一点保证，才能递归求解子问题，从而得到solution。
算法导论 4-6 VLSI芯片测试 - Zerohuan的专栏 - 博客频道 - CSDN.NET
任意拿两片芯片互相测试，则有
1）结果都为真，则说明两片都为真，或者都为假。
2）其他结果，则最少有一为假。
在任意偶数多的芯片里，如果好芯片多于坏芯片，将所有芯片两两分组，根据抽屉原理，则有
1）必有两个好芯片分在一组。
2）同为好芯片的组数一定多于同为坏芯片的组数。
测试流程
1）将芯片两两分组，比如1和2，3和4。。。。2k-1和2k。互相测试，则必有结果同为真的组。
2）保留结果同为真的组，丢弃其他组。必有好芯片组多于坏芯片组。（所以当只有两组或者一组同为真时，则必为真，测试结束）
3）结果同为真的组芯片必定同好或者同坏，所以可以丢弃一半。从所有同真组中任意取出一个丢弃另一个，组成新的测试组，继续两两分组，直到同真组只有2个或者1个测试结束，坚持到最后的就是好芯片。
说 明：同真组可能会变成奇数个，当为奇数组时，任意选一组取其中一个（假设为A），在剩余组中各取一个来测试A，如果测试结果A为好芯片过半或者等于一半， 则A为好芯片，测试结束。否则A为坏芯片，判定A为好芯片的必为坏芯片，剔除后剩余部分形成新的测试组，继续两两分组。。。
总的原理和淘 金差不多，刚开始好的芯片多，在每次剔除芯片时一定要保证剔除的坏芯片数量一定要多于或者等于好芯片的数量，这样就能保证在剩余的芯片中好的一定多于坏 的。当组数为奇数时采用投票制，多于半数的投票有效（等于也有效，因为好的多于坏的，相等则被测试的一定为好的）。
因为每次最少剔除一半的芯片，所以最坏情况出现在每次只能剔除一半芯片的时候，按等比数列递减。当有N个芯片时，测试次数为n+(n/2)+(n/4)...=2n（实际上当为奇数组时，次数会更多，不过算不过来了，省略^_^ ）
http://vlsicad.ucsd.edu/courses/cse101/hw_solutions/hw1_5.pdf
Question 5. CLRS 4-6.
a. If more than n/2 chips are bad, then a subset of the bad chips can act like good chips.
The number of black chips that do this can be the same as the number of good chips
(which is less than n/2), making it impossible to discern between these black chips
and the good chips (both sets of the same size). This means that it is possible for a
subset of the bad chips (the number of black chips in this subset is equal to the
number of good chips) to report accurately whether the other chip is good or bad.
Assuming that these bad chips always do this, it would be impossible to tell the
difference between the good chips and these bad chips. That is, there does not exist a
method by which to determine which are the good chips. Here is an illustration
below that illustrates this point:
b. The answer to this question lies in the two questions that are asked by Professor
Kahng on the discussion board. The first question is 1) if you put two chips on the
tester, and the result says that one of them is bad, what happens if you “throw both of
the chips away”? In this case, if you throw both of the chips away, then since you
know that at least one of the chips is bad, then you are still left with a set of chips that
have a majority of good chips. The second question is 2) if you have K pairs of chips,
each of which is an “identical pair” (i.e., X-X, where X can be either Good or Bad –
you can’t tell) – and, the 2K chips together have a majority of Good chips – is there
any way that you can come up with a smaller set of chips which still have a majority
of Good chips? The answer to this question is yes. You can easily do this by
throwing away one of the chips from each pair. Then, you still have a majority of
good chips. Therefore, combine the two questions, so to speak. If you are given n
chips, begin a pairwise comparison. If one or more is labeled as bad, throw them
both out. If they are both labeled as good, store them in a pile, but at the end of the
pairwise comparisons of all the chips, throw out one chip from each pair which said
that the chips were both good. If you do this, then you are guaranteed to have a set of
chips with a majority of good chips, where the size of the set is half the size of the
original set. After finishing this algorithm you will be left with one chip, which will
be good.
c. The recurrence relation corresponding to this solution is T(n) = 2T(n/2) + n/2, which
according to the master method is equal to (n).
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap04.htm
Video: https://class.coursera.org/algorithms-001/lecture/51
Read full article from 算法导论 4-6 VLSI芯片测试 - Zerohuan的专栏 - 博客频道 - CSDN.NET
对于分治（Divide and Conquer)的题目，最重要是
1.如何将原问题分解为若干个子问题，
2.子问题中是所有的都需要求解，还是选择一部分子问题即可。
还有一点其实非常关键，但是往往会被忽视：分解后的子问题除了规模较原问题小之外，必须和原问题具有相同的性质。
在子问题的划分时，只有这一点保证，才能递归求解子问题，从而得到solution。
算法导论 4-6 VLSI芯片测试 - Zerohuan的专栏 - 博客频道 - CSDN.NET
4-6 VLSI芯片测试
Diogenes教授有n个被认为是完全相同的VLSI芯片，原则上它们是可以互相测试的。教授的测试装置一次可测二片，当该装置中放有两片芯片时，每一片就对另一片作测试并报告其好坏。一个好的芯片总是能够报告另一片的好坏，但一个坏的芯片的结果是不可靠的。这样，每次测试的四种可能结果如下：
A芯片报告 B芯片报告 结论
B是好的 A是好的 都是好的，或都是坏的
B是好的 A是坏的 至少一片是坏的
B是坏的 A是好的 至少一片是坏的
B是坏的 A是坏的 至少一片是坏的
a）证明若多于n/2的芯片是坏的，在这种成对测试方法下，使用任何策略都不能确定哪个芯片是好的。假设坏的芯片可以联合起来欺骗教授。
b）假设有多于n/2的芯片是好的，考虑从n片中找出一片好芯片的问题。证明[n/2]对（下界）测试就足以使问题的规模降至近原来的一半。
c）假设多于n/2片芯片是好的，证明好的芯片可用Θ(n)对测试找出。给出并解答表达式测试次数的递归式。
http://blog.csdn.net/shoulinjun/article/details/14128635
You have n mobile phones and a contraption that holds two phones at the
same time and allows them to test each other. Once you load the phones into
the contraption, they test each other and each outputs whether the other
one is good or bad. If a phone is actually good than it will always output a
correct result. Unfortunately, if it is bad, its reply is unrelated to the real
state of the other phone and hence cannot be trusted. In other words, the
badphone can each time output whatever it wants. [For all practical pur-
poses,you can assume that the bad phone always outputs something that
willbe as unhelpful to you as possible.] Loading two phones and letting
them test each other will be called a test. We have 4 cases that might result
from a single test:
Chip A says
|
Chip B says
|
Conclusion
|
B is good
|
A is good
|
Either good or bad
|
B is good
|
A is bad
|
At least one is bad
|
B is bad
|
A is good
|
At least one is bad
|
B is bad
|
A is bad
|
At least one is bad
|
We will assume that there are more than n /2 good phones. Final goal is
to identify all the good and all the bad phones. In the question we are
after a deterministic algorithm, i.e. you cannot make use of any type of
randomization.
1.Explain how to find a single good phone. [Hint: Start by explaining
how to use O(n) tests to reduce the problem size by a constant factor.]
2.Use the previous part to show how to identify all of the good phones
by performing Θ(n) tests.
这个题目其实就是算法导论的一题课后题： VLSI芯片测试
思路： 目标是从n个手机中找到一个good phone.
注意题目给出了一个条件，原问题中超过一半的手机是好的。如果用分治，子问题必须同样满足good phones超过半数这一个性质。
先利用超过半数手机是好的这一性质，构造一个O（n^2）的算法。
Consider a phone x, 拿它与所有的phones做tests：
if超过半数的手机说它是good, then it's good.
Else it's bad.
打个比喻，法院审判一个犯人，陪审团中超过半数的人是公正的（如果 x is good, 他们一定投反对票），其余的人随便瞎给判决。无论其余的人怎么投票，根据少数服从多数的原则，最终犯人是否无罪释放取决于那超半数的公正的陪审团成员的判决。
注意： 一个重要的细节问题
总共n部手机，拿出一个手机后，剩余n-1部手机， 这n-1个手机中还是超半数是好手机吗？？（如果不是，算法1不再work)
答案是肯定的!!! 题目要求n是偶数，n中good phones > bad phones，
因此， n个手机中 good phones 至少比 bad phones多 2个 （反证法，若只好手机比坏手机多1个，则n是奇数，矛盾）
所以n个手机任意去掉一个手机后，仍然满足超半数是好手机的性质。
首先，直观想法：对半开，假设n是偶数，两两结对，做test
测试结果有4个 cases: (好-好)，(好-坏)，(坏-好)，(坏-坏)
注意到后三种情况，至少有一个是坏的phone（用反证法非常容易证明)
但是同时还要满足 超半数是good：
选择留下少于一半的元素（超半数是good)的，
或者说，选择丢掉超过半数的元素(超半数是bad）的。
Bingo！:丢掉测试结果是（好-坏，坏-好，坏-坏）（超半数是bad的）的phones,剩下的元素就是超半数是好的。
但是不要高兴得太早，子问题还有一个性质：《规模》
（好-好）的规模还一定是少于半数的，还得从其中丢掉一部分元素！！！
但是（好-好）只能保证 both good or both bad.
遇到了个小问题，不用怕，要相信自己的思路是对的。
（好-好）的所有元素中去掉一半元素，规模不就满足<n/2了
但是如何剔除呢？？
第一种思路，选择一半的（好-好）对去掉，不对。不能保证超半数是good的性质了;
第二种思路， 每一组（好-好）对中选择一个元素。Bingo！由于要么bothgood, or both bad, 这样做一定能保证，剩余的元素中good> bad;
(还有一点需要证明，(好-好)对一定会出现吗？反证法：若不存在，其余三种情况都是至少有一个是坏的，因此超半数是bad，矛盾)
Complexity:每次两两结对做tests，耗时O（n）
故 T（n)<= T(n/2) +O(n)所以复杂度是线性。
总结：
分治的子问题必须和原问题具有相同的性质。
算法分析：
(a) 可以采用时间复杂性最高但最准确的方法进行穷举：对每一个芯片，都让其他所有芯片和其配对检测，由于坏芯片的数量大于n/2，所以没有办法从检测结果判断芯片的好坏，所以~。
(b) 根据问题叙述的四种情况，可以想到用分治法来二分的解决问题，首先说下思路：
总：通过每次的划分子问题，并且保持满足好芯片多于坏芯片这一条件的循环不变式，我们就可以通过不断减小问题规模最终得到好芯片。
(1) 首先将原来的n个芯片随机的两两配对，这样就得到了[n/2]（下界）个检测对，可以假设，在n中有x个好芯片，y个坏芯片，检测对中有g对检测结果两个都为好的检测对，其中有a对为两个都为好芯片，b对两个都为坏芯片：
(2) 根据n的奇偶性不同分别进行分析：
1. 如果n为偶数，在剩下的([n/2] - g)对中坏芯片的数量大于等于好芯片，又x > y（这说明x - y >= 2），则在g对中a > b；
2. 如果n为奇数，就有一个芯片剩下没有配对，那么在x - y = 1的情况下，根据剩下那个芯片的好坏不同就有可能出现不同的情况：
如果g为奇数，即使g对以外的检测中坏芯片好芯片各占一半的，也能保证在g对中a - b >= 2，这样舍弃剩下未检测的芯片也能使新取出来的检 测序列中好芯片多于坏芯片；
如果g为偶数：
如果这个剩下的芯片是好的话，就有a >= b，留下这个芯片没有问题；
如果这个芯片是坏的话，就有a - b >= 2（因为g为偶数，要大只能大2个），留下这个坏芯片也没有问题。
(3) 这样在就得到一个规模为[n/2]的新检测序列，并且这个新序列也满足好芯片多于怀芯片的条件，这时就可以重复1， 2步进行递归或迭代，直到规模为1是，一定可以得到好芯片。
(c) 根据(b)的叙述，显然可以得到：T(n) = T(n/2) + n/2。
http://www.cppblog.com/jinq0123/archive/2007/09/24/goodbadchiptest.html任意拿两片芯片互相测试，则有
1）结果都为真，则说明两片都为真，或者都为假。
2）其他结果，则最少有一为假。
在任意偶数多的芯片里，如果好芯片多于坏芯片，将所有芯片两两分组，根据抽屉原理，则有
1）必有两个好芯片分在一组。
2）同为好芯片的组数一定多于同为坏芯片的组数。
测试流程
1）将芯片两两分组，比如1和2，3和4。。。。2k-1和2k。互相测试，则必有结果同为真的组。
2）保留结果同为真的组，丢弃其他组。必有好芯片组多于坏芯片组。（所以当只有两组或者一组同为真时，则必为真，测试结束）
3）结果同为真的组芯片必定同好或者同坏，所以可以丢弃一半。从所有同真组中任意取出一个丢弃另一个，组成新的测试组，继续两两分组，直到同真组只有2个或者1个测试结束，坚持到最后的就是好芯片。
说 明：同真组可能会变成奇数个，当为奇数组时，任意选一组取其中一个（假设为A），在剩余组中各取一个来测试A，如果测试结果A为好芯片过半或者等于一半， 则A为好芯片，测试结束。否则A为坏芯片，判定A为好芯片的必为坏芯片，剔除后剩余部分形成新的测试组，继续两两分组。。。
总的原理和淘 金差不多，刚开始好的芯片多，在每次剔除芯片时一定要保证剔除的坏芯片数量一定要多于或者等于好芯片的数量，这样就能保证在剩余的芯片中好的一定多于坏 的。当组数为奇数时采用投票制，多于半数的投票有效（等于也有效，因为好的多于坏的，相等则被测试的一定为好的）。
因为每次最少剔除一半的芯片，所以最坏情况出现在每次只能剔除一半芯片的时候，按等比数列递减。当有N个芯片时，测试次数为n+(n/2)+(n/4)...=2n（实际上当为奇数组时，次数会更多，不过算不过来了，省略^_^ ）
http://vlsicad.ucsd.edu/courses/cse101/hw_solutions/hw1_5.pdf
Question 5. CLRS 4-6.
a. If more than n/2 chips are bad, then a subset of the bad chips can act like good chips.
The number of black chips that do this can be the same as the number of good chips
(which is less than n/2), making it impossible to discern between these black chips
and the good chips (both sets of the same size). This means that it is possible for a
subset of the bad chips (the number of black chips in this subset is equal to the
number of good chips) to report accurately whether the other chip is good or bad.
Assuming that these bad chips always do this, it would be impossible to tell the
difference between the good chips and these bad chips. That is, there does not exist a
method by which to determine which are the good chips. Here is an illustration
below that illustrates this point:
b. The answer to this question lies in the two questions that are asked by Professor
Kahng on the discussion board. The first question is 1) if you put two chips on the
tester, and the result says that one of them is bad, what happens if you “throw both of
the chips away”? In this case, if you throw both of the chips away, then since you
know that at least one of the chips is bad, then you are still left with a set of chips that
have a majority of good chips. The second question is 2) if you have K pairs of chips,
each of which is an “identical pair” (i.e., X-X, where X can be either Good or Bad –
you can’t tell) – and, the 2K chips together have a majority of Good chips – is there
any way that you can come up with a smaller set of chips which still have a majority
of Good chips? The answer to this question is yes. You can easily do this by
throwing away one of the chips from each pair. Then, you still have a majority of
good chips. Therefore, combine the two questions, so to speak. If you are given n
chips, begin a pairwise comparison. If one or more is labeled as bad, throw them
both out. If they are both labeled as good, store them in a pile, but at the end of the
pairwise comparisons of all the chips, throw out one chip from each pair which said
that the chips were both good. If you do this, then you are guaranteed to have a set of
chips with a majority of good chips, where the size of the set is half the size of the
original set. After finishing this algorithm you will be left with one chip, which will
be good.
c. The recurrence relation corresponding to this solution is T(n) = 2T(n/2) + n/2, which
according to the master method is equal to (n).
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap04.htm
Video: https://class.coursera.org/algorithms-001/lecture/51
Read full article from 算法导论 4-6 VLSI芯片测试 - Zerohuan的专栏 - 博客频道 - CSDN.NET
