Uobičajene logičke zagonetke - Objašnjeni problemi s vitezovima i noževima, Monty Hallom i blagovaonicama

Iako nisu strogo povezane s programiranjem, logičke su zagonetke dobro zagrijavanje za sljedeću sesiju kodiranja. Na sljedećem tehničkom razgovoru možda ćete naići na logičku slagalicu kao način prosudbe svojih vještina rješavanja problema, pa vrijedi biti pripremljen.

U ovom smo članku prikupili nekoliko poznatih logičkih zagonetki i njihovih rješenja. Možete li ih riješiti bez zavirivanja u odgovor?

Vitezovi i noževi

Za ovu logičku slagalicu zamislite da postoje dvije vrste ljudi, vitezovi i knajevi. Vitezovi govore samo istinu, dok Knaves govori samo laži.

Postoje mnoge varijacije ove zagonetke, ali većina uključuje postavljanje pitanja kako biste shvatili tko je vitez, a tko knav.

Crvena i plava

Ispred vas stoje dvije osobe, Crvena i Plava. Blue kaže: "Oboje smo knajevi." Tko je zapravo vitez, a tko knaj?

Riješenje

Nemoguće je da Blue bude vitez. Da je Blue vitez, izjava "Oboje smo knajevi" zapravo bi bila laž. Prema tome, Blue je knaj, jer je njegova izjava laž, a Red mora biti vitez.

Dvije staze

Dolazite do račvanja na cesti i morate odabrati točnu stazu koja vodi do vašeg odredišta. Na račvanju stoje dvoje ljudi, a vi znate da jedan mora biti vitez, a drugi kant.

Koje biste pojedinačno pitanje mogli postaviti jednom od ljudi kako biste odredili ispravan put, A ili B?

Riješenje

Pitanje koje možete postaviti bilo kojoj osobi je: "Koji put bi mi druga osoba rekla da je ispravan?" Odgovor će uvijek biti pogrešan put, a vi možete sigurno ići drugim putem.

Zamislite da je ispravan put A.

Ako izravno pitate: "Koji je ispravan put?" knaj će reći da je B točno, dok će vitez reći A.

Međutim, na pitanje koji put bi druga osoba rekla da je točan, knave će lagati i reći da će vam vitez reći da je put B točan. U međuvremenu, vitez će reći istinu o odgovoru knave i reći da će vam knaj reći da je put B ispravan.

U oba slučaja znate da je tada odgovor, put B, zapravo laž, pa biste trebali krenuti drugim putem.

Problem Monty Halla

Problem Monty Halla zagonetka je o vjerojatnosti nazvana po voditelju emisije iz 70-ih na kojoj se temelji, Let's Make Deal . Ovaj je poseban problem veridical paradoks, što znači da postoji rješenje koje se čini kontraintuitivnim, a dokazano istinitim.

Zamislite da ste na igranom showu i tu su 3 vrata, a svaka iza njih ima drugačiju nagradu. Iza jednog od troja vrata nalazi se automobil. Iza druga dva vrata nalaze se koze.

Morate odabrati jedno od 3 vrata koja ćete odabrati kao nagradu.

Recimo da ste odlučili otvoriti vrata 1. Domaćin, koji zna gdje je automobil, otvara druga vrata, vrata 2, koja otkrivaju kozu. Zatim pita želite li umjesto toga otvoriti vrata 3.

Trebate li odabrati Door 3 umjesto svog originalnog izbora? Je li uopće važno?

Riješenje

Ispostavilo se da je vaš izbor doista važan i zapravo vam je u korist odabrati vrata 3 umjesto vrata 1. Evo zašto.

Kada ste odabrali Vrata 1 od 3 zatvorena vrata, imali ste 1 od 3 šanse da ste odabrali pravo. I vrata 2 i vrata 3 također imaju 1 od 3 šanse da iza sebe imaju automobil.

Drugi način da se o tome razmišlja je da vrata 2 i 3 imaju 2 od 3 šanse da kombiniraju automobil iza sebe .

Ali kad domaćin otvori vrata 2 i otkrije kozu, odjednom imate više informacija o problemu.

Imajte na umu da vrata 2 i 3 imaju kombiniranu vjerojatnost da skrivaju automobil 2/3 vremena. Kad su otvorena vrata 2, znate da iza njih nije bio automobil.

Ali ovo otkriće ne mijenja kombiniranu vjerojatnost dvoja vrata. To je ovdje ključno za poneti!

Budući da znate da Vrata 2 imaju 0/3 šanse da sakriju automobil, sada možete reći da postoji 2/3 šanse da je automobil iza Vrata 3. Vrata 1 ostaju nepromijenjena - samo je 1/3 automobila iza toga.

Dakle, ako se odlučite za promjenu, idete od otprilike 33,33% šanse do 66,67% šanse da pronađete automobil. Drugim riječima, udvostručujete šanse za uspjeh otvaranjem vrata 3!

Da, moguće je da su se vrata 1 cijelo vrijeme skrivala i da vas je domaćin prevario. To nije važno. Kockate se prihvaćajući dogovor, ali kocate pametno. Trebali biste donijeti najbolju odluku s informacijama koje ste dobili i pustiti da se kockice zavrte.

Dugoročno, zamijenili biste se boljim nastupom od natjecatelja koji odluči krenuti s prvim izborom. Iako to nije odmah očito, domaćin vam zapravo čini uslugu nudeći vam bolju ponudu.

Problem blagovaona filozofije

Problem filozofa blagovaonice klasičan je primjer u računalnoj znanosti koji ilustrira probleme sa sinkronizacijom. Izvorno ga je stvorio Edsger Dijkstra 1965. godine, koji ga je predstavio svojim studentima kao pregršt računala koja se natječu za pristup zajedničkim pogonima trake.

Zamislite pet šutljivih filozofa kako sjede oko stola, svaki sa zdjelom špageta. Na stolu su vilice između svakog para susjednih filozofa.

Svaki filozof istodobno može raditi samo jednu stvar: razmišljati i jesti. Međutim, filozof može jesti špagete samo kad imaju i lijevu i desnu vilicu. Vilicu istodobno može držati samo jedan filozof.

Nakon što filozof završi s jelom, moraju spustiti i lijevu i desnu vilicu kako bi bili dostupni ostalima. Filozof može uzeti vilicu čim je dostupna, ali može početi jesti tek kad imaju obje vilice.

Filozofi su poznati po svojim apetitima - svi mogu jesti beskrajno i nikad se ne mogu zasititi. Povrh toga, zdjelice špageta magično se nadopunjavaju bez obzira na to koliko se pojede.

Problem je u tome kako možete osigurati da niti jedan filozof neće gladovati i da može nastaviti jesti i razmišljati zauvijek?

Sinkronizacija i zastoj

Jednostavno rečeno, problem filozofa blagovaonice ilustrira kako sinkronizirani pristup zajedničkom resursu može rezultirati stvaranjem mrtve točke.

Sinkronizacija se koristi za kontrolu istodobnog pristupa zajedničkom resursu. To je neophodno u bilo kojoj situaciji u kojoj se više neovisnih aktera može natjecati za korištenje jednog resursa poput vilica. Budući da je dostupan samo jedan resurs, koristimo sinkronizaciju kako bismo spriječili zbrku i kaos.

Zastoj je državni sustav u kojem je moguće nikakav napredak. Ta se situacija može dogoditi kada se izvrši sinkronizacija, a mnogi procesi na kraju čekaju zajednički resurs koji se zadržava u nekom drugom procesu. Kao i kod filozofa koji su zaglavljeni u jelu ili razmišljanju, procesi samo čekaju i ne izvršavaju se dalje.

Rješenja

Na prvi pogled izgleda kao da ne bi bilo moguće zastoj u kojem su svi filozofi zaglavljeni ili jedu ili razmišljaju. Na primjer, obrazac koji bi svaki filozof trebao slijediti mogao bi biti:

1: razmislite dok ne bude dostupna lijeva vilica; kad je, podignite je;

2: razmislite dok ne bude dostupna prava vilica; kad je, podignite je;

3: kad se drže obje vilice, jedite određeno vrijeme;

4: zatim odložite desnu vilicu;

5: zatim odložite lijevu vilicu;

6: ponovite od početka.

Izvor: Wikipedia

Mnogo je mogućih rješenja za sprečavanje zastoja. Ako pažljivo pogledamo, jedan je problem gore navedenog algoritma taj što svi filozofi imaju jednake šanse (imaju isti prioritet) za stjecanje jedne vilice. To sprječava bilo koga da nabavi dvije vilice i cijeli se sustav zaustavlja.

Evo nekoliko mogućih rješenja:

  1. Prioritet : Nekim filozofima je dodijeljen veći prioritet, tako da je povećana šansa za stjecanje obje vilice.
  2. Prednost (uljudnost): Filozofi se odriču stečene vilice bez jela, u slučaju da druga vilica nije dostupna.
  3. Arbitraža : Posrednik dodjeljuje vilice osiguravajući da se dvije vilice daju jednoj osobi, umjesto jedne većini.

Sad kad znate kako riješiti ove logičke zagonetke, priuštite si beskrajnu zdjelu špageta. Vi ste to zaradili.