Умова:
Відома логічна задача, може бути корисною для програмістів-початківців. Я пообіцяв учасникам i7.juniors детально її пояснити. Давайте розбиратися.
Давайте сформулюємо всі логічні запитання, які можна задати аборигену. Це запитання стосуються як самого аборигена, так і місцезнаходження вашої з ним зустрічі:
- Ти лицар?
- Ти брехун?
- Ти хитрун?
- Ми в селі лицарів?
- Ми в селі брехунів?
- Ми в селі хитрунів?
Шість запитань. Інші запитання на кшталт «Чи є життя на Марсі» нам не підійдуть, тому що нам треба не просто побалакати, а розв’язати задачу за мінімальну кількість запитань.
Далі пропоную розділити задачу на дві проміжні.
Перша – допомогти мандрівнику дізнатися, з ким він розмовляє.
Друга – допомогти мандрівнику дізнатися, в якому селі він знаходиться.
Першу задачу можна розв’язати, якщо задати аборигену запитання номер три двічі поспіль. Тобто запитати два рази: «Ти хитрун?»
Якщо абориген двічі відповість «ні» — перед нами лицар. Якщо абориген відповість двічі «так», то він брехун. Якщо ж він дасть різні відповіді, то це хитрун. В такому випадку нам треба запам’ятати послідовність його відповідей. Тобто, якщо хитрун на запитання «Ти хитрун?» спочатку сказав «так», а потім – «ні», це означає, що спочатку він сказав правду, а потім збрехав. Нам це важливо, тому що, згідно умови задачі, наступний раз хитрун скаже правду. І навпаки.
Далі, дізнавшись «характеристику» аборигена, мандрівнику треба дізнатися, в якому селі вони знаходяться.
Для цього йому потрібно задати запитання номери чотири і п’ять в будь-який послідовності, а саме:
— Ми в селі лицарів?
— Ми в селі брехунів?
Розглянемо три випадки – коли на ці два запитання відповідають лицар, брехун і хитрун.
Нехай перед ним лицар. Тоді мандрівник гарантовано отримає інформацію про своє місцезнаходження за два питання. (якщо на перше питання лицар відповів «так», то вистачить і одного запитання.)
Нехай перед ним брехун. Якщо на перше питання брехун відповів «ні», то мандрівник знаходиться в селі лицарів. Якщо на перше питання брехун відповів «так», значить, мандрівник не в цьому селі, і він повинен поставити ще одне запитання, щоб дізнатися, знаходиться він в селі брехунів або в селі хитрунів. Для того щоб гарантовано це визначити, мандрівнику і знадобиться отримати відповідь на друге запитання.
Третій варіант. Нехай перед ним хитрун. Запам'ятавши відповіді на попередні два запитання, мандрівник може зрозуміти, чи скаже хитрун в наступний раз правду або він збреше. Якщо прийшов час хитруну казати правду і у відповідь на запитання «Я в селі лицарів?», хитрун скаже «так», то мандрівник якраз в цьому селі. Якщо хитруну прийшов час брехати, і на запитання «Чи ми в селі лицарів?" він скаже «ні», то мандрівник також в цьому селі. В інших випадках мандрівнику знадобиться ще одне запитання, четверте.
Отже, мандрівнику потрібно два запитання, щоб зрозуміти, з ким він розмовляє, і ще два запитання, щоб безумовно зрозуміти, в якому він селі. Всього чотири питання.
Нагадаємо які вони:
— Ти хитрун?
— Ти хитрун?
— Ми в селі лицарів?
— Ми в селі брехунів?
Правильна відповідь: 4 запитання.
p.s. Маєте інші версії? Чудово! Пишіть в коменти або приходьте на i7.juniors!