Deși nu sunt strict legate de programare, puzzle-urile logice sunt o încălzire bună pentru următoarea dvs. sesiune de codare. Este posibil să întâlniți un puzzle logic în următorul dvs. interviu tehnic ca o modalitate de a vă judeca abilitățile de rezolvare a problemelor, așa că merită să vă pregătiți.

În acest articol, am colectat câteva puzzle-uri logice celebre și soluțiile lor. Puteți să le rezolvați fără să aruncați o privire la răspuns?

Cavaleri și Knaves

Pentru acest puzzle logic, imaginați-vă că există două tipuri de oameni, cavaleri și boli. Cavalerii spun doar adevărul, în timp ce Knaves spun doar minciuni.

Există multe variante ale acestui puzzle, dar cele mai multe implică să puneți o întrebare pentru a afla cine este cavalerul și cine este sclavul.

Rosu si albastru

Sunt doi oameni care stau în fața ta, Roșu și Albastru. Albastru spune: „Amândoi suntem niște stăpâni”. Cine este cu adevărat cavalerul și cine este șmecherul?

Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Soluţie
Este imposibil ca Blue să fie cavalerul. Dacă Albastru ar fi un cavaler, afirmația „Amândoi suntem niște cavaleri” ar fi de fapt o minciună. Prin urmare, Albastru este un șiretlic, deoarece afirmația sa este o minciună, iar Roșu trebuie să fie cavaler.

Două cărări

Ajungi la o bifurcație a drumului și trebuie să alegi calea corectă care duce la destinație. Sunt doi oameni care stau la bifurcație și știi că unul trebuie să fie cavaler, iar celălalt trebuie să fie un șiret.

Ce singură întrebare i-ai putea pune unuia dintre oameni pentru a determina calea corectă, A sau B?

1612099687 910 Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Soluţie
Întrebarea pe care o puteți pune oricărei persoane este: „Ce cale mi-ar spune cealaltă persoană este cea corectă?” Răspunsul va fi întotdeauna calea greșită de urmat și puteți lua în siguranță cealaltă cale.

Imaginați-vă că calea corectă este A.

Dacă întrebați direct „Care este calea corectă?” ciupitorul va spune că B este corect, în timp ce cavalerul va spune A.

Cu toate acestea, când a fost întrebat care este calea alte persoana ar spune că este corectă, șmecherul va minți și va spune că cavalerul ți-ar spune că drumul B este corect. Între timp, cavalerul va spune adevărul despre răspunsul scârțâitorului și va spune că scârțosul îți va spune că calea B este cea corectă.

În ambele cazuri știți că atunci răspunsul, calea B, este de fapt o minciună, așa că ar trebui să luați cealaltă cale.

Problema Monty Hall

The Monty Hall Problem este o enigmă a probabilității numită după gazda spectacolului de jocuri din anii 70 pe care se bazează, Să facem o afacere. Această problemă specială este o paradox veridic, ceea ce înseamnă că există o soluție care pare contraintuitivă, dar dovedită a fi adevărată.

Imaginați-vă că sunteți într-un spectacol de jocuri și există 3 uși, fiecare cu un premiu diferit în spate. În spatele uneia dintre cele trei uși se află o mașină. În spatele celorlalte două uși sunt capre.

Trebuie să alegeți una dintre cele 3 uși pe care să o selectați ca premiu.

Spuneți că decideți să deschideți ușa 1. Gazda, care știe unde este mașina, deschide o ușă diferită, ușa 2, care dezvăluie o capră. Apoi vă întreabă dacă doriți să deschideți ușa 3 în schimb.

Ar trebui să alegeți ușa 3 în locul alegerii inițiale? Ba chiar contează?

Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Soluţie
Se pare că alegerea ta contează cu adevărat și este de fapt în beneficiul tău să alegi ușa 3 în locul ușii 1. Iată de ce.

Când ai ales ușa 1 din cele 3 uși închise, ai avut șansa 1 din 3 să o alegi pe cea potrivită. Atât ușa 2, cât și ușa 3 au, de asemenea, o șansă de 1 din 3 să aibă o mașină în spatele ei.

O altă modalitate de gândire este că ușile 2 și 3 au șanse 2 din 3 de a avea o mașină în spatele ei combinate.

Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Dar când gazda deschide ușa 2 și dezvăluie capra, ai brusc mai multe informații despre problemă.

Amintiți-vă că ușile 2 și 3 au o probabilitate combinată de a ascunde mașina 2/3 din timp. Când ușa 2 a fost deschisă, știți că nu era nicio mașină în spatele ei.

Dar această dezvăluire nu schimbă probabilitatea combinată a celor două uși. Aceasta este cheia de luat masa aici!

1612099687 583 Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Din moment ce știți că ușa 2 are 0/3 șanse să ascundă mașina, puteți spune acum că există o șansă de 2/3 ca mașina să fie în spatele ușii 3. Ușa 1 rămâne neschimbată – există doar 1/3 mașina este in spatele.

Deci, dacă decideți să schimbați, treceți de la o șansă de aproximativ 33,33% la o șansă de 66,67% de a găsi mașina. Cu alte cuvinte, vă dublați șansele de succes deschizând în schimb ușa 3!

Da, este posibil ca ușa 1 să se fi ascuns tot timpul și gazda să te fi păcălit. Asta nu contează. Pariați luând afacerea, dar joci inteligent. Ar trebui să luați cea mai bună decizie cu informațiile pe care vi le oferim și să lăsați zarurile să ruleze.

Pe termen lung, ai avea performanțe mai bune prin schimbare decât un concurent care decide să meargă cu prima lor alegere. Deși nu este imediat evident, gazda vă face de fapt o favoare oferindu-vă o ofertă mai bună.

Problema Filozofilor de luat masa

Problema filosofilor culinare este un exemplu clasic în informatică pentru a ilustra problemele legate de sincronizare. A fost creat inițial de Edsger Dijkstra în 1965, care l-a prezentat studenților săi ca o mână de computere care concurează pentru accesul la unitățile de bandă partajate.

Imaginați-vă cinci filozofi tăcuți stând în jurul unei mese, fiecare cu un castron de spaghete. Există furci pe masă între fiecare pereche de filozofi adiacenți.

1612099687 321 Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si
Imagine oferită de adit.io.

Fiecare filosof nu poate face decât un singur lucru odată: gândiți și mâncați. Cu toate acestea, un filozof poate mânca spaghete numai atunci când are atât furculița stângă, cât și cea dreaptă. O furculiță poate fi ținută doar de un filozof la un moment dat.

După ce un filozof termină de mâncat, trebuie să pună jos atât furcile din stânga cât și din dreapta, astfel încât să fie disponibile celorlalți. Un filozof poate lua o furculiță imediat ce este disponibil, dar poate începe să mănânce numai după ce au ambele furci.

Filozofii sunt renumiți pentru apetitul lor – toți pot mânca la nesfârșit și nu se pot sătura niciodată. În plus, bolurile de spaghete se umple magic, indiferent cât de mult se mănâncă.

Problema este, cum te poți asigura că niciun filosof nu va muri de foame și că poate continua să mănânce și să gândească pentru totdeauna?

1612099688 834 Puzzle uri logice obisnuite Cavalerii si Knaves Monty Hall si

Sincronizare și blocare

În termeni simpli, problema filosofilor culinare este o ilustrare a modului în care accesul sincronizat la o resursă partajată poate duce la crearea unei situații de impas.

Sincronizare este folosit pentru a controla accesul simultan la o resursă partajată. Acest lucru este necesar în orice situație în care mai mulți actori independenți pot concura pentru utilizarea unei resurse, cum ar fi furculițele. Deoarece există o singură resursă disponibilă, folosim sincronizarea pentru a preveni confuzia și haosul.

A Impas este o stare de sistem în care nu este posibil niciun progres. Această situație poate apărea atunci când sincronizarea este pusă în aplicare și multe procese ajung să aștepte o resursă partajată care este deținută de un alt proces. Ca și în cazul filozofilor care sunt fie blocați mâncând, fie gândind, procesele continuă să aștepte și nu se mai execută.

Soluții

La prima vedere se pare că nu ar fi posibil pentru un impas în care toți filozofii sunt blocați fie mâncând, fie gândind. De exemplu, modelul pe care trebuie să îl urmeze fiecare filozof ar putea fi:

1: gândiți-vă până când furculița din stânga este disponibilă; când este, ridică-l;

2: gândiți-vă până când furca potrivită este disponibilă; când este, ridică-l;

3: când ambele furci sunt ținute, mâncați pentru o perioadă fixă ​​de timp;

4: apoi, pune furculița dreaptă jos;

5: apoi, puneți furculița stângă în jos;

6: repetă de la început.

Sursă: Wikipedia

Există multe soluții posibile pentru a preveni blocarea. Dacă ne uităm cu atenție, o problemă din algoritmul de mai sus este că toți filosofii au șanse egale (au aceeași prioritate) de a dobândi o furcă. Acest lucru împiedică pe oricine să achiziționeze două furci și întregul sistem se oprește.

Iată câteva soluții posibile:

  1. Prioritate: Unora dintre filozofi li se atribuie o prioritate mai mare, astfel încât șansa de a dobândi ambele furci este crescută.
  2. Preempțiune (Politețe): filozofii renunță la furculița dobândită fără să mănânce, în cazul în care cealaltă furcă nu este disponibilă.
  3. Arbitraj: Un mediator alocă furculițe asigurându-se că două furci sunt date unei persoane, în loc de una mai multor persoane.

Acum, că știi cum să rezolvi aceste puzzle-uri logice, răsfăță-te cu un bol nesfârșit de spaghete. Ai castigat-o.