Загальні логічні головоломки - Пояснення проблем лицарів і невільників, Монті Холла та обідніх філософів

Хоча логічні головоломки не суто пов’язані з програмуванням, вони є гарною розминкою до наступного сеансу кодування. Ви можете зустріти логічну головоломку на наступному технічному співбесіді як спосіб оцінити свої навички вирішення проблем, тому варто бути готовим.

У цій статті ми зібрали кілька відомих логічних головоломок та їх рішення. Чи можете ви їх вирішити, не заглядаючи у відповідь?

Лицарі та халапи

Уявіть, що для цієї логічної головоломки існує два типи людей - лицарі та хащі. Лицарі говорять лише правду, тоді як Кнайвс - лише брехню.

Існує безліч варіантів цієї головоломки, але більшість з них пов’язані із запитанням, щоб з’ясувати, хто є лицарем, а хто ловцем.

Червоний і синій

Перед вами стоять двоє людей, Червоний і Синій. Блу каже: "Ми обидва халапи". Хто насправді лицар, а хто злодій?

Рішення

Неможливо, щоб Блу був лицарем. Якби Блю був лицарем, твердження: "Ми обоє халапи" насправді було б брехнею. Отже, Блу - це халап, оскільки його висловлювання - брехня, а Червоний повинен бути лицарем.

Два шляхи

Ви приїжджаєте на розвилку дороги і вам потрібно вибрати правильний шлях, який веде до пункту призначення. На розвилці стоять двоє людей, і ти знаєш, що один повинен бути лицарем, а інший - хамутом.

Яке єдине запитання ви могли б задати одному з людей, щоб визначити правильний шлях, А чи В?

Рішення

Питання, яке ви можете задати будь-якій людині, полягає в наступному: "Який шлях інша людина сказала б мені правильним?" Відповіддю завжди буде неправильний шлях, і ви можете сміливо піти іншим шляхом.

Уявіть, правильний шлях - А.

Якщо ви прямо запитаєте: "Який правильний шлях?" хаврат скаже В правильно, тоді як лицар скаже А.

Однак, коли його запитують, який шлях інша людина сказала б правильним, хамр збреше і скаже, що лицар скаже вам, що шлях Б правильний. Тим часом лицар скаже правду про відповідь хамура і скаже, що хабар скаже вам, що шлях Б правильний.

В обох випадках ви знаєте, що тоді відповідь, шлях Б, насправді є брехнею, тому вам слід піти іншим шляхом.

Проблема Монті Холла

Проблема Монті Холла - загадка про ймовірність, названа на честь ведучого ігрового шоу 70-х, на якому вона базується, “ Давайте укладемо угоду” . Ця особлива проблема - це парадикс, який означає, що існує рішення, яке здається протиінтуїтивним, проте підтвердженим.

Уявіть, що ви перебуваєте на ігровому шоу, а за вами є 3 двері, кожна з яких має різний приз. За однією з трьох дверей - машина. За двома іншими дверима є кози.

Ви повинні вибрати одну з 3-х дверей, щоб вибрати як свій приз.

Скажімо, ви вирішили відкрити Двері 1. Господар, хто знає, де знаходиться машина, відчиняє інші двері, Двері 2, яка відкриває козу. Потім він запитує, чи не хочете ви замість цього відкрити Двері 3?

Чи варто вибрати «Двері 3» перед початковим? Це взагалі має значення?

Рішення

Виявляється, ваш вибір справді має значення, і насправді вам на користь вибрати Двері 3 замість Двері 1. Ось чому.

Коли ви вибрали Двері 1 із 3 закритих дверей, у вас був шанс 1 із 3, що ви вибрали правильну. І двері 2, і двері 3 також мають шанс 1 із 3 мати машину за собою.

Інший спосіб думати про це - це те, що двері 2 і 3 мають шанс 2 із 3 мати комбінований автомобіль .

Але коли господар відкриває Двері 2 і розкриває козу, ви раптом отримуєте більше інформації про проблему.

Пам’ятайте, що двері 2 і 3 мають загальну ймовірність, що приховують машину 2/3 часу. Коли двері 2 відкрили, ви знаєте, що за ними не було машини.

Але це виявлення не змінює сукупну ймовірність двох дверей. Це ключовий винос тут!

Оскільки ви знаєте, що Двері 2 має 0/3 шансів сховати машину, тепер ви можете сказати, що є 2/3 ймовірності, що машина знаходиться позаду Двері 3. Двері 1 залишається незмінною - є лише 1/3 машини за цим.

Отже, якщо ви вирішите перейти, ви переходите від приблизно 33,33% шансів до 66,67% шансів знайти машину. Іншими словами, ви подвоюєте свої шанси на успіх, відкривши замість цього Двері 3!

Так, цілком можливо, що Двері 1 весь час приховувалась і господар обдурив вас. Це не має значення. Ви граєте в азартні ігри, приймаючи угоду, але азартні ігри розумні. Ви повинні прийняти найкраще рішення з наданою вами інформацією, і нехай кістки кидаються.

У довгостроковій перспективі ви б виграли краще, змінившись, ніж той учасник, який вирішив піти зі своїм першим вибором. Хоча це не відразу очевидно, господар фактично робить вам послугу, пропонуючи вам вигіднішу угоду.

Проблема філософів їдальні

Проблема філософів-ресторанів є класичним прикладом інформатики для ілюстрації проблем із синхронізацією. Спочатку його створив Едсгер Дейкстра в 1965 році, який представив його своїм студентам як кілька комп'ютерів, які змагаються за доступ до спільних стрічкових накопичувачів.

Уявіть собі п’ять мовчазних філософів, які сидять за столом, кожен з яких має миску спагетті. На столі між кожною парою сусідніх філософів є виделки.

Кожен філософ може робити лише одне за раз: думати і їсти. Однак філософ може їсти спагетті лише тоді, коли у них є і ліва, і права вилки. Вилку одночасно може тримати лише один філософ.

Після того, як філософ закінчує їсти, їм потрібно відкласти і ліву, і праву виделки, щоб вони були доступні для інших. Філософ може взяти виделку, як тільки вона з’явиться, але починати їсти можна лише після того, як у них є обидві виделки.

Філософи славляться своїми апетитами - всі вони можуть їсти нескінченно і ніколи не насичуватися. На додачу до цього, миски з спагеті чарівним чином поповнюються незалежно від того, скільки з’їдено.

Проблема полягає в тому, як ви можете переконатись, що жоден філософ не буде голодувати, і що вони зможуть продовжувати їсти і думати вічно?

Синхронізація та глухий кут

Простіше кажучи, проблема філософів-ресторанів є ілюстрацією того, як синхронізований доступ до спільного ресурсу може призвести до тупикової ситуації.

Синхронізація використовується для контролю одночасного доступу до спільного ресурсу. Це необхідно в будь-якій ситуації, коли кілька незалежних суб'єктів можуть конкурувати за використання одного ресурсу, такого як форки. Оскільки доступний лише один ресурс, ми використовуємо синхронізацію, щоб запобігти плутанині та хаосу.

Тупик цього стану системи , де прогрес неможливий. Ця ситуація може виникнути, коли синхронізація примусова, і багато процесів в кінцевому підсумку чекають спільного ресурсу, який утримується якимсь іншим процесом. Як і у філософів, які або застрягли в їжі, або думають, процеси просто чекають і не виконуються далі.

Рішення

На перший погляд здається, що не було б можливості зайти в глухий кут, коли всі філософи застрягли або їдять, або думають. Наприклад, зразок для кожного філософа може бути таким:

1: подумайте, поки ліва вилка не стане доступною; коли він є, підніміть його;

2: подумайте, поки не з’явиться потрібна вилка; коли воно є, підніміть його;

3: коли обидві вилки утримуються, їжте протягом певного часу;

4: потім відкладіть праву виделку;

5: потім відкладіть ліву вилку вниз;

6: повторити з початку.

Джерело: Вікіпедія

Існує безліч рішень для запобігання тупикової ситуації. Якщо придивитися, одна проблема в наведеному вище алгоритмі полягає в тому, що всі філософи мають рівні шанси (мають однаковий пріоритет) придбати одну форку. Це заважає кожному придбати дві вилки, і вся система зупиняється.

Ось декілька можливих рішень:

  1. Пріоритет : Деяким філософам присвоюється вищий пріоритет, завдяки чому збільшується шанс придбання обох виделок.
  2. Перевага (ввічливість): Філософи відмовляються від набутої виделки, не з’їдаючи, якщо інша виделка недоступна.
  3. Арбітраж : посередник виділяє вилки, гарантуючи, що дві вилки даються одній людині, а не одній - багатьом.

Тепер, коли ви знаєте, як розгадати ці логічні головоломки, побалуйте себе нескінченною мискою спагетті. Ви це заробили.