Задача 6.
На дне моря щука нашла три яйца, в каком-то одном из которых лежит игла (а на конце иглы — Кощеева смерть). У Ивана Царевича есть волшебная шкатулка: кладёшь в неё яйца, а она человеческим голосом говорит, есть ли в каком-то из них игла, или нет. Есть одна загвоздка. У шкатулки с Иваном уговор: один раз вместо «да, внутри меня есть игла» шкатулка имеет право соврать и сказать «нет, иглы нет» (но может и не врать).
Требуется найти иглу за три вопроса шкатулке. Нужно указать последовательность действий (алгоритм), позволяющий однозначно понять, в каком яйце находится игла.
Первый вопрос. Какие яйца положить в шкатулку?
Второй вопрос. Какие яйца положить в шкатулку, если:
- на первый вопрос получили ответ «иглы нет»?
- на первый вопрос получили ответ «игла есть»?
Третий вопрос. Какие яйца положить в шкатулку, если:
- на первый и второй вопросы получили ответы «нет» и «нет»?
- на первый и второй вопросы получили ответы «нет» и «есть»?
- на первый и второй вопросы получили ответы «есть» и «нет»?
- на первый и второй вопросы получили ответы «есть» и «есть»?
Ответ на Задачу 6.
Приведём один из возможных алгоритмов. Проверяем сначала 1-е яйцо. Если ответ положительный, то игла — в 1-м яйце. В противном случае проверяем пару 1-е + 2-е яйца, и тогда возможны два случая:
1) Ответ положительный — ещё раз проверим 1-е яйцо:
- если ответ положительный, то игла в 1-м яйце
- в противном случае игла в 2-м яйце
2) Ответ отрицательный — проверим 2-е яйцо:
- если ответ положительный, то игла в 2-м яйце
- в противном случае игла в 3-м яйце
