Общи логически пъзели - Обяснени проблеми на рицарите и мошениците, Монти Хол и философите на трапезата

Макар и да не са строго свързани с програмирането, логическите пъзели са добра подгрявка за следващата ви сесия за кодиране. Може да срещнете логически пъзел при следващото си техническо интервю като начин да прецените уменията си за решаване на проблеми, така че си струва да бъдете подготвени.

В тази статия сме събрали няколко известни логически пъзела и техните решения. Можете ли да ги разрешите, без да надничате отговора?

Рицари и Knaves

За този логически пъзел, представете си, че има два вида хора, рицари и knaves. Рицарите казват само истината, докато Knaves казват само лъжи.

Има много вариации на този пъзел, но повечето включват задаване на въпрос, за да разберете кой е рицарят и кой е измамникът.

Червено и синьо

Пред вас стоят двама души, Червен и Син. Блу казва: „И двамата сме измамници“. Кой всъщност е рицарят и кой е гаврата?

Решение

Невъзможно е Блу да бъде рицарят. Ако Блу ​​беше рицар, твърдението „И двамата сме мошеници“ всъщност би било лъжа. Следователно, Blue е мошеник, тъй като изказването му е лъжа, а Red трябва да е рицар.

Две пътеки

Стигате до разклон на пътя и трябва да изберете правилния път, който води до вашата дестинация. На разклонението стоят двама души и вие знаете, че единият трябва да е рицар, а другият трябва да бъде мошеник.

Какъв един въпрос бихте могли да зададете на един от хората, за да определи правилния път, A или B?

Решение

Въпросът, който можете да зададете на всеки човек, е: "Какъв път би ми казал другият, че е правилният?" Отговорът винаги ще бъде погрешният път и вие можете спокойно да поемете по другия път.

Представете си, че правилният път е А.

Ако попитате директно: "Кой е правилният път?" knave ще каже B е вярно, докато рицарят ще каже A.

Когато обаче го попитат кой път другият би казал, че е правилен, хамът ще излъже и ще каже, че рицарят ще ви каже, че пътят Б е правилен. Междувременно рицарят ще каже истината за отговора на хамбара и ще каже, че хамбарът ще ви каже, че пътят В е правилният.

И в двата случая знаете, че тогава отговорът, път Б, всъщност е лъжа, така че трябва да поемете по другия път.

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

Проблемът с Монти Хол е загадка за вероятността, кръстена на водещия на шоуто от 70-те години, на което се основава, Нека направим сделка . Този конкретен проблем е парадикс, който означава, че има решение, което изглежда контраинтуитивно, но доказано, че е вярно.

Представете си, че сте на игрално шоу и има 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 да се е крила през цялото време и домакинът ви е подмамил. Това няма значение. Вие залагате, като приемете сделката, но залагате умно. Трябва да вземете най-доброто решение с информацията, която сте получили, и да оставите заровете да се хвърлят.

В дългосрочен план бихте се представили по-добре чрез смяна от състезател, който реши да отиде с първия си избор. Въпреки че не е очевидно веднага, домакинът всъщност ви прави услуга, като ви предлага по-добра сделка.

Проблемът на философите за хранене

Проблемът на философите за хранене е класически пример в компютърните науки, който илюстрира проблеми със синхронизирането. Първоначално е създаден от Edsger Dijkstra през 1965 г., който го представя на своите ученици като шепа компютри, състезаващи се за достъп до споделени лентови устройства.

Представете си петима мълчаливи философи, седнали около една маса, всеки с купичка спагети. На масата има вилици между всяка двойка съседни философи.

Всеки философ може да прави само едно нещо наведнъж: да мисли и да яде. Философът обаче може да яде спагети само когато имат и лявата, и дясната вилица. Вилица може да държи само един философ наведнъж.

След като философът приключи с храненето, те трябва да оставят и лявата и дясната вилица, за да са на разположение на останалите. Философът може да вземе вилица веднага щом е налична, но може да започне да яде само след като имат и двете вилици.

Философите са известни със своите апетити - всички те могат да се хранят безкрайно и никога да не се наситят. На всичкото отгоре купичките спагети магически се попълват, независимо колко се яде.

Проблемът е в това как можете да гарантирате, че никой философ няма да гладува и че те могат да продължат да се хранят и да мислят завинаги?

Синхронизация и задънена улица

С прости думи, проблемът на философите за хранене е илюстрация на това как синхронизираният достъп до споделен ресурс може да доведе до създаване на ситуация на блокиране.

Синхронизацията се използва за контрол на едновременния достъп до споделен ресурс. Това е необходимо във всяка ситуация, когато множество независими участници могат да се конкурират за използването на един ресурс като разклоненията. Тъй като има само един наличен ресурс, ние използваме синхронизация, за да предотвратим объркване и хаос.

А Deadlock е система състояние, където е възможно, няма напредък. Тази ситуация може да възникне, когато се налага синхронизация и много процеси в крайна сметка чакат споделен ресурс, който се задържа от друг процес. Подобно на философите, които или са закъсали да се хранят или мислят, процесите просто продължават да чакат и не се изпълняват повече.

Решения

На пръв поглед изглежда, че не би било възможно да се стигне до задънена улица, където всички философи са закъсали или да се хранят, или да мислят. Например модел, който всеки философ да следва, може да бъде:

1: помислете, докато е налична лявата вилица; когато е, вземете го;

2: помислете, докато се намери подходящата вилица; когато е, вземете го;

3: когато се държат и двете вилици, яжте за определен период от време;

4: след това поставете дясната вилица надолу;

5: след това оставете лявата вилица надолу;

6: повторете от самото начало.

Източник: Уикипедия

Има много възможни решения за предотвратяване на задънена улица. Ако се вгледаме отблизо, един проблем в алгоритъма по-горе е, че всички философи имат еднакъв шанс (имат един и същ приоритет) да придобият една вилица. Това не позволява на никого да придобие две вилици и цялата система спира да спира.

Ето няколко възможни решения:

  1. Приоритет : Някои философи получават по-висок приоритет, така че шансът да се сдобият с двете вилици се увеличава.
  2. Превенция (учтивост): Философите се отказват от придобитата вилица, без да ядат, в случай че другата вилица не е на разположение.
  3. Арбитраж : Медиаторът разпределя вилици, като гарантира, че две вили се дават на един човек, вместо един на много.

Сега, след като знаете как да решавате тези логически пъзели, поглезете се с безкрайна купичка спагети. Спечелихте го.