algorithm - O(logn) で偽造コインを見つけるための分割統治アルゴリズム

Question

やあ ！！この問題を解決するための情報や例を見つけようとしましたが、見つかりませんでした。そして、このような関連する例を含むリソースはありますか? 乾杯！！

Answer 1

I'll give the solution in (log2(n) + 1) steps. +1 is to find whether heavy or light. If you know that part, it will take log2(n) steps.

Divide into 2 piles. Say, A and B. Weigh them against each other, and you find A<B (read, weight of pile A is lesser then that of B). Take a pile, say A, split and weigh the parts. If they weigh equal, you get 2 facts:

• Counterfeit coin is in B
• It is heavier than other coins.

And then you continue with pile B. (and there went your +1 weighing.)

otherwise:

• Counterfeit coin is in A
• It is lighter than other coins.

Now, say A contained counterfeit coin. Then, name the two divided piles of A as A and B, and, repeat.

PS: I solved this puzzle with 3^n coins to start (a few years back). It also takes same number of steps, as its complexity is (log3(n) (+1)). I'll leave it as your next question to solve.

PPS: I'll leave the second part of the question to you. Apply Master's theorem yourself.
HINT: Same as that of binary search.