Almindelige logiske gåder - Knights and Knaves, Monty Hall og Dining Philosophers Problemer forklaret

Selvom det ikke er strengt relateret til programmering, er logiske gåder en god opvarmning til din næste kodningssession. Du kan støde på et logikpuslespil i dit næste tekniske interview som en måde at bedømme dine færdigheder til problemløsning, så det er værd at være forberedt.

I denne artikel har vi samlet et par berømte logiske gåder og deres løsninger. Kan du løse dem uden at kigge på svaret?

Riddere og knapper

Forestil dig, at der er to typer mennesker til dette logiske puslespil, riddere og knive. Riddere fortæller kun sandheden, mens Knaves kun fortæller løgne.

Der er mange variationer af dette puslespil, men de fleste involverer at stille et spørgsmål for at finde ud af, hvem der er ridder og hvem der er kniven.

Rød og blå

Der står to mennesker foran dig, rød og blå. Blue siger: "Vi er begge knive." Hvem er virkelig ridderen, og hvem er kniven?

Opløsning

Det er umuligt for Blue at være ridder. Hvis Blue var en ridder, ville udsagnet "Vi er begge knive" faktisk være en løgn. Derfor er Blue en kniv, da hans udsagn er en løgn, og Rød skal være en ridder.

To stier

Du ankommer til en gaffel i vejen og har brug for at vælge den rigtige sti, der fører til din destination. Der står to mennesker ved gaflen, og du ved, at den ene skal være en ridder, og den anden skal være en kniv.

Hvilket enkelt spørgsmål kan du stille til en af ​​befolkningen for at bestemme den rigtige vej, A eller B?

Opløsning

Spørgsmålet, du kan stille en af ​​parterne, er: "Hvilken vej vil den anden person fortælle mig, er den rigtige?" Svaret vil altid være den forkerte vej at tage, og du kan med sikkerhed tage den anden vej.

Forestil dig, at den rigtige sti er A.

Hvis du spørger direkte, "Hvilken er den rigtige vej?" kniven vil sige B er korrekt, mens ridderen vil sige A.

Men når man bliver spurgt om hvilken sti den anden person vil sige er korrekt, vil kæben lyve og sige at ridderen vil fortælle dig at sti B er korrekt. I mellemtiden vil ridderen fortælle sandheden om knivens svar og sige, at kniven vil fortælle dig, at sti B er den rigtige.

I begge tilfælde ved du, at svar, sti B, faktisk er en løgn, så du skal tage den anden sti.

Monty Hall-problemet

Monty Hall-problemet er en gåde om sandsynlighed, der er opkaldt efter værten for 70'ernes spiludstilling, den er baseret på, Lad os lave en aftale . Dette særlige problem er et veridisk paradoks, hvilket betyder, at der er en løsning, der virker kontraintuitiv, men alligevel bevist at være sand.

Forestil dig, at du er på et spilshow, og der er 3 døre, hver med en anden præmie bag sig. Bag en af ​​de tre døre er der en bil. Bag de to andre døre er der geder.

Du skal vælge en af ​​de 3 døre, der skal vælges som din præmie.

Sig, at du beslutter dig for at åbne dør 1. Værten, der ved, hvor bilen er, åbner en anden dør, dør 2, som afslører en ged. Han spørger derefter, om du vil åbne dør 3 i stedet.

Skal du vælge dør 3 frem for dit oprindelige valg? Betyder det endda noget?

Opløsning

Det viser sig, at dit valg virkelig betyder noget, og det er faktisk til din fordel at vælge Dør 3 i stedet for Dør 1. Her er hvorfor.

Når du valgte Dør 1 blandt de 3 lukkede døre, havde du en 1 ud af 3 chance for at du valgte den rigtige. Både dør 2 og dør 3 har også en 1 ud af 3 chance for at have en bil bag sig.

En anden måde at tænke over det er, at Døre 2 og 3 har en 2 ud af 3 chance for at have en bil bag sig kombineret .

Men når værten åbner dør 2 og afslører geden, har du pludselig flere oplysninger om problemet.

Husk at døre 2 og 3 har en kombineret sandsynlighed for at skjule bilen 2/3 af tiden. Da dør 2 blev åbnet, ved du, at der ikke var nogen bil bag den.

Men denne afsløring ændrer ikke den kombinerede sandsynlighed for de to døre. Det er den vigtigste afhentning her!

Da du ved, at dør 2 har en 0/3 chance for at skjule bilen, kan du nu sige, at der er en 2/3 chance for, at bilen er bag dør 3. Dør 1 forbliver uændret - der er kun en 1/3, bilen er bag det.

Så hvis du beslutter at skifte, går du fra cirka 33,33% chance til 66,67% chance for at finde bilen. Med andre ord fordobler du dine chancer for succes ved at åbne Dør 3 i stedet!

Ja, det er muligt, at dør 1 gemte sig hele tiden, og værten narede dig. Det betyder ikke noget. Du spiller ved at tage aftalen, men du spiller smart. Du skal tage den bedste beslutning med de oplysninger, du får, og lade terningerne kaste.

I det lange løb ville du klare dig bedre ved at skifte end en deltager, der beslutter at gå med deres førstevalg. Selvom det ikke er umiddelbart indlysende, gør værten dig faktisk en tjeneste ved at tilbyde dig en bedre aftale.

Dining Philosophers Problem

Spisningsfilosofernes problem er et klassisk eksempel inden for datalogi for at illustrere problemer med synkronisering. Det blev oprindeligt oprettet af Edsger Dijkstra i 1965, der præsenterede det for sine studerende som en håndfuld computere, der konkurrerer om adgang til delte bånddrev.

Forestil dig fem tavse filosoffer, der sidder rundt om et bord, hver med en skål spaghetti. Der er gafler på bordet mellem hvert par tilstødende filosoffer.

Hver filosof kan kun gøre én ting ad gangen: tænke og spise. En filosof kan dog kun spise spaghetti, når de har både venstre og højre gafler. En gaffel kan kun holdes af en filosof ad gangen.

Når en filosof er færdig med at spise, skal de lægge både venstre og højre gafler ned, så de er tilgængelige for de andre. En filosof kan tage en gaffel, så snart den er tilgængelig, men kan kun begynde at spise, når de har begge gafler.

Filosofferne er berømte for deres appetit - de kan alle spise uendeligt og aldrig blive mætte. Derudover fyldes skålene med spaghetti magisk, uanset hvor meget der spises.

Problemet er, hvordan kan du sikre, at ingen filosof sulter, og at de kan fortsætte med at spise og tænke for evigt?

Synkronisering og blokering

Enkelt sagt er spisefilosofernes problem en illustration af, hvordan synkroniseret adgang til en delt ressource kan resultere i skabelse af en blokeret situation.

Synkronisering bruges til at kontrollere samtidig adgang til en delt ressource. Dette er nødvendigt i enhver situation, hvor flere uafhængige aktører kan konkurrere om brugen af ​​en ressource som gaflerne. Da der kun er én ressource tilgængelig, bruger vi synkronisering til at forhindre forvirring og kaos.

En deadlock er en systemtilstand, hvor ingen fremskridt er mulig. Denne situation kan opstå, når synkronisering håndhæves, og mange processer ender med at vente på en delt ressource, der holdes af en anden proces. Ligesom med de filosoffer, der enten sidder fast eller spiser eller tænker, fortsætter processerne bare og venter ikke længere.

Løsninger

Ved første øjekast ser det ud til, at det ikke ville være muligt for en dødvande, hvor alle filosoffer sidder fast, hverken spiser eller tænker. For eksempel kan mønster for hver filosof at følge være:

1: tænk, indtil venstre gaffel er tilgængelig; når det er, så tag det op;

2: tænk, indtil den rigtige gaffel er tilgængelig; når det er, så tag det op;

3: når begge gafler holdes, spis i en fast periode;

4: læg derefter den højre gaffel ned;

5: læg derefter venstre gaffel ned;

6: gentag fra begyndelsen.

Kilde: Wikipedia

Der er mange mulige løsninger for at forhindre blokering. Hvis vi ser nøje, er et problem i algoritmen ovenfor, at alle filosoffer har lige chance (har samme prioritet) for at erhverve en fork. Dette forhindrer nogen i at erhverve to gafler, og hele systemet standser.

Her er nogle mulige løsninger:

  1. Prioritet : Nogle filosoffer tildeles højere prioritet, så chancen for at erhverve begge gafler øges.
  2. Befrielse (høflighed): Filosoffer opgiver den erhvervede gaffel uden at spise, hvis den anden gaffel ikke er tilgængelig.
  3. Voldgift : En mægler tildeler gafler, der sikrer, at der gives to gafler til en person i stedet for en til mange.

Nu hvor du ved, hvordan du løser disse logiske gåder, kan du forkæle dig selv med en endeløs skål spaghetti. Du har tjent det.