Разделяй и властвуй алгоритм, чтобы найти фальшивую монету в O (LOGN)

Question

Привет !! Я попытался найти информацию и примеры для решения этой проблемы, но не смог ее найти. Это мои вопросы подготовки к экзамену, а не задание. Может кто-нибудь объяснить шаги для решения этой проблемы? И любой ресурс со связанными примерами вроде этого? ура !!

Answer 1

Я дам решение в шагах (log2 (n) + 1). +1 - это найти тяжелый или легкий. Если вы знаете эту часть, она примет шаги log2 (n).

Разделите на 2 сваи. Скажем, A и B. Взвешивайте их друг против друга, и вы найдете A<B (читайте, вес кучи A меньше, чем у B). Возьмите кучу, скажите A, разделите и взвешите детали. Если они весят равны, вы получаете 2 факта:

• фальшивая монета находится в B
• Это тяжелее, чем другие монеты.

И тогда вы по-прежнему с ворсом B. (и пошли ваши +1 весом.)

иначе:

• фальшивая монета находится в
• Это легче, чем другие монеты.

Теперь, скажем, содержится поддельная монета. Затем назовите две разделенные груды A как A and B и повторите.

PS: Я решил эту головоломку с помощью 3^n монет, чтобы начать (несколько лет назад). Он также принимает такое же количество шагов, как и его сложность (log3 (n) (+1)). Я оставлю это как ваш следующий вопрос для решения.

PPS: Я оставлю вторую часть вопроса вам. Примените Master's theorem самостоятельно.
СОВЕТ: То же, что и у binary search.