Levinud loogikamõistatused - rüütlid ja rüütlid, Monty Hall ja söögifilosoofide probleemid

Ehkki see pole programmeerimisega seotud, on loogikamõistatused teie järgmise kodeerimisseansi jaoks hea soojendus. Järgmises tehnilises intervjuus võite kohata loogikamõistatust, et hinnata oma probleemide lahendamise oskusi, nii et tasub olla valmis.

Selles artiklis oleme kogunud mõned kuulsad loogikamõistatused ja nende lahendused. Kas saate need lahendada ilma vastust piilumata?

Rüütlid ja rüütlid

Kujutage selle loogikamõistatuse jaoks ette kahte tüüpi inimesi, rüütleid ja rüütleid. Rüütlid räägivad ainult tõtt, samas kui Knaves vaid valesid.

Selles mõistatuses on palju variatsioone, kuid enamik neist hõlmab küsimuse esitamist, et välja selgitada, kes on rüütel ja kes on rüütel.

Punane ja Sinine

Teie ees seisab kaks inimest, punane ja sinine. Sinine ütleb: "Me oleme mõlemad pättid." Kes on tegelikult rüütel ja kes on rüütel?

Lahendus

Sinil on võimatu olla rüütel. Kui Sinine oleks rüütel, oleks väide: "Me oleme mõlemad knavesid" tegelikult vale. Seetõttu on Sinine rüütel, kuna tema väide on vale ja Red peab olema rüütel.

Kaks rada

Jõuate teehargile ja peate valima õige tee, mis viib sihtkohta. Hargis seisab kaks inimest ja teate, et üks peab olema rüütel ja teine ​​rüütel.

Millise ühe küsimuse võiksite küsida ühelt inimeselt, et määrata õige tee A või B?

Lahendus

Küsimus, mille võite kummalegi inimesele esitada, on järgmine: "Mis teed teine ​​inimene mulle ütleks, on õige?" Vastus on alati vale tee, mida saate minna, ja võite julgelt minna ka teist teed.

Kujutage ette, et õige tee on A

Kui küsite otse: "Kumb on õige tee?" rüütel ütleb, et B on õige, rüütel aga A.

Kui aga küsitakse, millise tee teine inimene õigeks peaks, valetab sõtk ja ütleb, et rüütel ütleks, et tee B on õige. Vahepeal räägib rüütel tõe knave vastusest ja ütleb, et knave ütleb teile, et tee B on õige.

Mõlemal juhul teate, et siis on vastus B tee tegelikult vale, seega peaksite minema teisele teele.

Monty Halli probleem

Monty Halli probleem on mõistatus tõenäosuse kohta, mis on nimetatud 70ndate mänguprogrammi, millel see põhineb, saate teeme, teeme . See konkreetne probleem on tõeline paradoks, mis tähendab, et on olemas lahendus, mis näib olevat intuitiivne, kuid tõestatuna tõene.

Kujutage ette, et olete mängusaates ja seal on 3 ust, millest igaühel on erinev auhind taga. Ühe kolme ukse taga on auto. Kahe teise ukse taga on kitsed.

Auhinnaks valimiseks peate valima ühe kolmest uksest.

Oletame, et otsustate avada ukse 1. Peremees, kes teab, kus auto asub, avab teise ukse, ukse 2, mis paljastab kitse. Seejärel küsib ta, kas soovite selle asemel ukse 3 avada.

Kas peaksite oma algse valiku asemel valima Uks 3? Kas see on üldse oluline?

Lahendus

Selgub, et teie valikul on tõesti tähtsust ja tegelikult on teie kasuks valida uks 3 asemel uks 3. Sellepärast.

Kui valisite 3 suletud ukse seast ukse 1, oli teil 1-st võimalus 3-st, et valisite õige. Nii uksel 2 kui ka uksel 3 on 1 võimalus kolmest, kui auto taga on.

Teine võimalus mõelda on see, et uksed 2 ja 3 on 2 välja 3 võimalus, millel auto taga kombineeritud .

Aga kui peremees avab ukse 2 ja paljastab kitse, on teil äkki probleemi kohta rohkem teavet.

Pidage meeles, et ustel 2 ja 3 on kombineeritud tõenäosus auto peita 2/3 ajast. Kui uks 2 avati, teate, et selle taga polnud ühtegi autot.

Kuid see paljastus ei muuda kahe ukse ühist tõenäosust. See on siin peamine võtmiskoht!

Kuna teate, et 2. uksel on 0/3 võimalus auto peitmiseks, võite nüüd öelda, et on 2/3 tõenäosus, et auto jääb ukse 3 taha. 1. uks jääb muutumatuks - auto on ainult 1/3 selle taga.

Nii et kui otsustate vahetada, lähete auto leidmise tõenäosuselt umbes 33,33% -lt 66,67% -ni. Teisisõnu, kahekordistate oma eduvõimalusi, avades selle asemel ukse 3!

Jah, on võimalik, et uks 1 oli kogu aeg peidus ja host pettis sind. See pole oluline. Mängite tehingu sõlmimisega, kuid mängite nutikalt. Peaksite teile antud teabe põhjal tegema parima otsuse ja laskma täringul veereda.

Pikas perspektiivis töötaksite vahetades paremini kui võistleja, kes otsustab oma esimese valiku teha. Kuigi see pole kohe ilmne, teeb peremees teile hoopis teene, pakkudes teile paremat pakkumist.

Söögifilosoofide probleem

Söögifilosoofide probleem on arvutiteaduses klassikaline näide sünkroniseerimise probleemide illustreerimiseks. Algselt lõi selle Edsger Dijkstra 1965. aastal, esitades seda oma õpilastele käputäie arvutitena, kes võistlevad juurdepääsu eest jagatud lindiseadmetele.

Kujutage ette viit vaikivat filosoofi, kes istuksid laua ümber ja igaühel kauss spagette. Iga külgneva filosoofipaari vahel on laual kahvlid.

Iga filosoof saab korraga teha ainult ühte asja: mõelda ja süüa. Filosoof saab spagette süüa aga ainult siis, kui neil on nii vasak kui ka parem kahvliharud. Kahvlit saab korraga hoida ainult üks filosoof.

Kui filosoof on söömise lõpetanud, peavad nad maha panema nii vasaku kui ka parema kahvli, et need oleksid teistele kättesaadavad. Filosoof võib kahvli võtta kohe, kui see on saadaval, kuid sööma saab hakata alles siis, kui neil on mõlemad kahvlid olemas.

Filosoofid on kuulsad oma isude poolest - nad kõik saavad süüa lõputult ega saa kunagi täis. Pealegi täiendavad spagetikausid võluväel, hoolimata sellest, kui palju seda süüakse.

Probleem on selles, kuidas saaksite tagada, et ükski filosoof ei nälgiks ja et nad saaksid jätkata söömist ja mõtlemist igavesti?

Sünkroonimine ja ummikseis

Lihtsamalt öeldes on söögifilosoofide probleem illustreeriv, kuidas sünkroniseeritud juurdepääs jagatud ressursile võib põhjustada ummikseisu.

Sünkroonimist kasutatakse samaaegse juurdepääsu kontrollimiseks jagatud ressursile. See on vajalik igas olukorras, kus mitu sõltumatut osalejat võivad konkureerida ühe ressursi nagu kahvlid kasutamise pärast. Kuna saadaval on ainult üks ressurss, kasutame segaduste ja kaose vältimiseks sünkroonimist.

Tupikseisu on süsteem, kus ei ole edusamme on võimalik. Selline olukord võib ilmneda sünkroonimise jõustamisel ja paljud protsessid ootavad lõpuks jagatud ressurssi, mida hoiab mõni muu protsess. Nagu filosoofide puhul, kes on kas söömise või mõtlemisega ummikus, jätkavad protsessid lihtsalt ootamist ja ei täida enam midagi.

Lahendused

Esmapilgul näib, nagu poleks võimalik ummikusse sattuda, kus kõik filosoofid on kas söömise või mõtlemise ummikus. Näiteks võib iga filosoofi järgitav muster olla:

1: mõelge, kuni vasak kahvel on saadaval; kui see on, siis korja see üles;

2: mõelge, kuni õige kahvli saab; kui see on, siis korja see üles;

3: kui mõlemad kahvlid on käes, sööge kindla aja jooksul;

4: siis pange parem kahvli alla;

5: siis pange vasak kahvli alla;

6: korda algusest peale.

Allikas: Vikipeedia

Ummiku vältimiseks on palju lahendusi. Kui me vaatame tähelepanelikult, on ülaltoodud algoritmi üks probleem see, et kõigil filosoofidel on võrdsed võimalused (neil on sama prioriteet) ühe kahvli omandamine. See takistab kedagi omandamast kahte kahvlit ja kogu süsteem lihvib seiskumiseni.

Siin on mõned võimalikud lahendused:

  1. Prioriteet : mõnele filosoofile omistatakse kõrgem prioriteet, nii et mõlema kahvli omandamise võimalus suureneb.
  2. Eelistus (viisakus): filosoofid loobuvad omandatud kahvlist söömata, juhul kui teist kahvlit pole saadaval.
  3. Vahekohus : Vahendaja eraldab kahvlid tagamaks, et ühele inimesele antakse kaks kahvlit, ühe asemel mitu.

Nüüd, kui teate, kuidas neid loogikamõistatusi lahendada, lubage endale lõputu spagetikauss. Sa teenisid selle.