Közös logikai feladványok - a lovagok és a knaves, a Monty Hall és az étkezési filozófusok magyarázata

Noha a szigorúan nem kapcsolódnak a programozáshoz, a logikai feladványok jó felmelegedést jelentenek a következő kódolási munkamenetre. A következő technikai interjú során találkozhat egy logikai fejtörővel, amely megítélheti problémamegoldó képességeit, ezért érdemes felkészülni.

Ebben a cikkben összegyűjtöttünk néhány híres logikai feladványt és azok megoldásait. Meg tudja oldani őket anélkül, hogy a választ lesi?

Lovagok és Knaves

Képzeljük el, hogy ehhez a logikai rejtvényhez kétféle ember létezik: lovagok és lovagok. A lovagok csak az igazat mondják, míg a Knaves csak a hazugságokat.

Ennek a rejtvénynek sok változata van, de a legtöbb kérdés feltevésével jár, hogy kiderüljön, ki a lovag és ki a knave.

Piros és Kék

Két ember áll előtted, Piros és Kék. Blue azt mondja: "Mindketten knave-ek vagyunk". Ki valójában a lovag és ki a lovag?

Megoldás

Kék lehetetlen lovag lenni. Ha Blue lovag lenne, a "Mindketten knave-ek" kijelentés valójában hazugság lenne. Ezért Kék knave, mivel állítása hazugság, és Rednek lovagnak kell lennie.

Két Út

Az útelágazáshoz érkezik, és ki kell választania a helyes utat, amely az úticéljához vezet. Két ember áll az elágazásnál, és tudod, hogy az egyiknek lovagnak, a másiknak lovagnak kell lennie.

Milyen egyetlen kérdést tehetne fel az emberek egyikének, hogy meghatározza a helyes utat, A vagy B?

Megoldás

A kérdés, amelyet bármelyik embernek feltehet, a következő: "Milyen utat mondana nekem a másik?" A válasz mindig a rossz út lesz, és nyugodtan haladhat a másik úton is.

Képzelje el, hogy a helyes útvonal A.

Ha közvetlenül kérdezi: "Melyik a helyes út?" a knave azt mondja, hogy B helyes, míg a lovag A.-t.

Amikor azonban megkérdezik, hogy a másik személy melyik utat mondja helyesnek, a knave hazudik, és azt mondja, hogy a lovag megmondja, hogy a B út helyes. Eközben a lovag elmondja az igazságot a knave válaszáról, és azt mondja, hogy a knave megmondja, hogy a B út a helyes.

Mindkét esetben tudja, hogy akkor a válasz, a B út valójában hazugság, ezért a másik utat kell választania.

A Monty Hall-probléma

A Monty Hall-probléma egy rejtvény a valószínűségről, amelyet a 70-es évekbeli játék show műsorvezetőjéről, a Csináljunk üzletet neveztek el . Ez a bizonyos probléma veridikus paradoxon, ami azt jelenti, hogy létezik olyan megoldás, amely ellentmondásosnak tűnik, ugyanakkor igaznak bizonyult.

Képzelje el, hogy részt vesz egy játékbemutatón, és 3 ajtó van, mindegyik mögött más a nyeremény. A három ajtó mögött egy autó található. A másik két ajtó mögött kecskék vannak.

Nyereményként a 3 ajtó egyikét kell választania.

Mondja, hogy úgy dönt, hogy kinyitja az 1. ajtót. A házigazda, aki tudja, hol van az autó, kinyit egy másik ajtót, a 2. ajtót, amelyből kiderül egy kecske. Ezután megkérdezi, hogy nyitja-e helyette a 3. ajtót.

Ha a 3. ajtót választja az eredeti választása helyett? Egyáltalán számít?

Megoldás

Kiderült, hogy a választása valóban számít, és valóban előnyös, ha az 1. ajtó helyett a 3. ajtót választja. Itt van miért.

Amikor az 1-es ajtót választotta a 3 zárt ajtó közül, akkor 1-ből 3 esélye volt arra, hogy a megfelelőt választotta. A 2. és a 3. ajtónak is van 1 esélye a 3 közül arra, hogy autó álljon mögötte.

A másik gondolkodásmód az, hogy a 2. és a 3. ajtónak 2-ből 2-re van esélye arra, hogy együtt legyen mögöttük egy autó .

De amikor a házigazda kinyitja a 2. ajtót és feltárja a kecskét, hirtelen több információja van a problémáról.

Ne feledje, hogy a 2. és a 3. ajtó együttes valószínűsége elrejti az autót az idő 2/3-a. Amikor a 2. ajtót kinyitották, tudja, hogy nem volt mögötte autó.

De ez a felfedés nem változtatja meg a két ajtó együttes valószínűségét. Ez a legfontosabb elvihetőség itt!

Mivel tudod, hogy a 2-es ajtónak 0/3-as esélye van az autó elrejtésére, most azt mondhatod, hogy 2/3-os esély van arra, hogy az autó a 3-as ajtó mögött van. Az 1. ajtó változatlan marad - csak az autó 1/3-a van mögötte.

Tehát, ha úgy dönt, hogy vált, nagyjából 33,33% -ról 66,67% -ra talál az autó. Más szavakkal: megduplázza a siker esélyét azzal, hogy helyette kinyitja a 3. ajtót!

Igen, lehetséges, hogy az 1. ajtó végig bujkált, és a házigazda becsapott. Ez nem számít. Ön szerencsejátékot köt az üzlet megkötésével, de okosan. Meg kell hoznia a legjobb döntést a kapott információkkal, és hagynia kell dobni a kockát.

Hosszú távon jobban teljesítene, ha váltana, mint egy versenyző, aki úgy dönt, hogy első választása mellett dönt. Bár ez nem azonnal nyilvánvaló, a fogadó valójában egy szívességet tesz Önnek azzal, hogy jobb ajánlatot kínál Önnek.

Az étkező filozófusok problémája

Az étkezési filozófusok problémája klasszikus példa a számítástechnikában, hogy szinkronizálással szemléltesse a kérdéseket. Eredetileg Edsger Dijkstra hozta létre 1965-ben, aki egy maroknyi számítógépként mutatta be hallgatóinak, akik versengenek a megosztott szalagos meghajtókhoz való hozzáférésért.

Képzeljen el öt csendes filozófust, akik egy asztal körül ülnek, egyenként egy tál spagettivel. A szomszédos filozófuspárok között villák vannak az asztalon.

Minden filozófus egyszerre csak egyet tehet: gondolkodni és enni. A filozófus azonban csak akkor ehet spagettit, ha mind a bal, mind a jobb villa van. Villát egyszerre csak egy filozófus tarthat.

Miután egy filozófus befejezte az evést, le kell tenniük a bal és a jobb villát is, hogy elérhetőek legyenek a többiek számára. A filozófus elvehet egy villát, amint elérhető, de csak akkor kezdhet el enni, ha mindkét villa megvan.

A filozófusok híresek az étvágyukról - mindnyájan végtelenül ehetnek, és soha nem tudnak jóllakni. Ráadásul a spagettitálak varázslatosan feltöltődnek, függetlenül attól, hogy mennyit fogyasztanak.

A probléma az, hogyan lehet biztosítani, hogy egyetlen filozófus sem éhen haljon, és hogy örökké folytathassák az evést és a gondolkodást?

Szinkronizálás és holtpont

Egyszerűbben fogalmazva: az étkezési filozófusok problémája szemlélteti, hogy a megosztott erőforrásokhoz való szinkronizált hozzáférés holtponthoz vezethet.

A szinkronizálást egy megosztott erőforrás párhuzamos hozzáférésének szabályozására használják. Erre szükség van minden olyan helyzetben, amikor több független szereplő versenyezhet egy erőforrás, például a villák használatáért. Mivel csak egy erőforrás áll rendelkezésre, a szinkronizálást használjuk a zavar és a káosz megelőzésére.

A holtpont egy olyan rendszerállapot, ahol nem lehetséges előrelépés. Ez a helyzet akkor fordulhat elő, amikor a szinkronizálást kényszerítik, és sok folyamat végül egy megosztott erőforrásra vár, amelyet valamilyen más folyamat tart. Akár az evéshez, akár a gondolkodáshoz ragadt filozófusokhoz hasonlóan, a folyamatok is csak várakoznak, és nem hajtanak végre tovább.

Megoldások

Első pillantásra úgy tűnik, hogy nem lenne lehetséges holtpont, ahol az összes filozófus elakadt vagy eszik, vagy gondolkodik. Például az egyes filozófusok követendő mintája a következő lehet:

1: gondolkodjon addig, amíg a bal villa rendelkezésre nem áll; amikor van, vedd fel;

2: gondolkodjon addig, amíg a megfelelő villa rendelkezésre nem áll; amikor van, vedd fel;

3: ha mindkét villát tartják, akkor egyenek egy meghatározott ideig;

4: majd tegye le a megfelelő villát;

5: majd tegye le a bal villát;

6: ismételje meg az elejétől.

Forrás: Wikipédia

Számos megoldás lehetséges a holtpont megelőzésére. Ha jól megnézzük, a fenti algoritmus egyik problémája az, hogy minden filozófusnak azonos esélye van (azonos prioritással rendelkezik) egy villa megszerzéséhez. Ez megakadályozza, hogy bárki megszerezzen két villát, és az egész rendszer leáll.

Íme néhány lehetséges megoldás:

  1. Prioritás : Néhány filozófusnak magasabb prioritást tulajdonítanak, így megnő a két villa megszerzésének esélye.
  2. Elővétel (udvariasság): A filozófusok evés nélkül lemondanak a megszerzett villáról, hátha a másik villa nem áll rendelkezésre.
  3. Választottbíróság : A közvetítő villákat oszt ki annak biztosítására, hogy két villát egy személy kapjon, egy helyett sokakat.

Most, hogy tudja, hogyan oldja meg ezeket a logikai rejtvényeket, kényeztesse magát egy végtelen tál spagettivel. Megérdemelted.