Рубрики

Алгоритмы | Разное | Вопрос 11

Дано 8 одинаковых монет, из которых одна монета тяжелая и баланс сковороды . Сколько минимального количества измерений необходимо, чтобы найти тяжелую монету?
(А) 2
(Б) 3
(С) 4
(D) 7

Ответ: (А)
Объяснение:

Divide the coins into three groups and name the coins according to there group:
A: A1, A2, A3
B: B1, B2, B3
C: C1, C2

Measure group A and group B. Two cases arise:
1. They are equal. One more measurement is needed to find the heavy 
   coin in group C. Total two measurements needed in this case.
2. They are not equal. Find the heavy group, say A. Pick any two coins
   from this group,  say A1 and A3. Measure A1 and A3 in the pan balance. 
   Two cases arise:
   2.1 They are equal. A2 is the heavy coin. Total two measurements 
       needed.
   2.2 They are not equal. It is known which of A1 or A3 is heavy. 
       Total two measurements needed.
So, the above observations says that in any case, 2 measurements are enough
to find the heavy coin.

Follow up:
Generalize the minimum number of measurements for n coins 
with one coin heavy.

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Разное | Вопрос 11

0.00 (0%) 0 votes