Gemeinsame Logik-Rätsel - Die Probleme der Ritter und Schurken, Monty Hall und Dining Philosophen erklärt

Logikpuzzles sind zwar nicht eng mit der Programmierung verbunden, aber eine gute Vorbereitung für Ihre nächste Codierungssitzung. Möglicherweise stoßen Sie in Ihrem nächsten technischen Interview auf ein logisches Rätsel, um Ihre Fähigkeiten zur Problemlösung zu beurteilen. Es lohnt sich also, darauf vorbereitet zu sein.

In diesem Artikel haben wir einige berühmte Logikrätsel und ihre Lösungen zusammengestellt. Können Sie sie lösen, ohne auf die Antwort zu schauen?

Ritter und Schurken

Stellen Sie sich für dieses logische Rätsel zwei Arten von Menschen vor, Ritter und Schurken. Ritter sagen nur die Wahrheit, während Schurken nur Lügen erzählen.

Es gibt viele Variationen dieses Puzzles, aber die meisten beinhalten das Stellen einer Frage, um herauszufinden, wer der Ritter und wer der Schurke ist.

Rot und Blau

Vor dir stehen zwei Leute, Rot und Blau. Blue sagt: "Wir sind beide Schurken." Wer ist wirklich der Ritter und wer ist der Schurke?

Lösung

Es ist unmöglich für Blue, der Ritter zu sein. Wenn Blue ein Ritter wäre, wäre die Aussage "Wir sind beide Schurken" tatsächlich eine Lüge. Daher ist Blau ein Schurke, da seine Aussage eine Lüge ist, und Rot muss ein Ritter sein.

Zwei Wege

Sie kommen an einer Weggabelung an und müssen den richtigen Weg wählen, der zu Ihrem Ziel führt. An der Gabelung stehen zwei Personen, und Sie wissen, dass eine ein Ritter und die andere ein Schurke sein muss.

Welche einzelne Frage könnten Sie einem der Leute stellen, um den richtigen Weg zu bestimmen, A oder B?

Lösung

Die Frage, die Sie jeder Person stellen können, lautet: "Welchen Weg würde die andere Person mir sagen, ist der richtige?" Die Antwort wird immer der falsche Weg sein, und Sie können sicher den anderen Weg einschlagen.

Stellen Sie sich vor, der richtige Pfad ist A.

Wenn Sie direkt fragen: "Welcher ist der richtige Weg?" Der Schurke sagt, dass B korrekt ist, während der Ritter A sagt.

Auf die Frage, welcher Weg die andere Person für richtig hält, lügt der Schurke und sagt, der Ritter würde Ihnen sagen, dass Weg B richtig ist. In der Zwischenzeit wird der Ritter die Wahrheit über die Antwort des Schurken sagen und sagen, dass der Schurke Ihnen sagen wird, dass Pfad B der richtige ist.

In beiden Fällen wissen Sie, dass die Antwort, Pfad B, tatsächlich eine Lüge ist, also sollten Sie den anderen Pfad nehmen.

Das Monty Hall Problem

Das Monty Hall-Problem ist ein Rätsel um die Wahrscheinlichkeit, das nach dem Moderator der Spielshow der 70er Jahre benannt ist, auf der es basiert: Let's Make a Deal . Dieses spezielle Problem ist ein wahres Paradoxon, was bedeutet, dass es eine Lösung gibt, die kontraintuitiv erscheint, sich jedoch als wahr erwiesen hat.

Stellen Sie sich vor, Sie sind in einer Spielshow und es gibt 3 Türen mit jeweils einem anderen Preis. Hinter einer der drei Türen steht ein Auto. Hinter den beiden anderen Türen stehen Ziegen.

Sie müssen eine der 3 Türen auswählen, um sie als Preis auszuwählen.

Angenommen, Sie möchten Tür 1 öffnen. Der Gastgeber, der weiß, wo sich das Auto befindet, öffnet eine andere Tür, Tür 2, die eine Ziege enthüllt. Er fragt dann, ob Sie stattdessen Tür 3 öffnen möchten.

Sollten Sie Tür 3 Ihrer ursprünglichen Wahl vorziehen? Ist es überhaupt wichtig?

Lösung

Es stellt sich heraus, dass Ihre Wahl wirklich wichtig ist, und es ist tatsächlich zu Ihrem Vorteil, Tür 3 anstelle von Tür 1 zu wählen. Hier ist der Grund dafür.

Wenn Sie Tür 1 aus den 3 geschlossenen Türen ausgewählt haben, hatten Sie eine 1 von 3 Chancen, dass Sie die richtige ausgewählt haben. Sowohl Tür 2 als auch Tür 3 haben eine 1 von 3 Chancen, ein Auto dahinter zu haben.

Eine weitere Möglichkeit , darüber nachzudenken ist , dass Türen 2 und 3 haben eine 2 von 3 Chance auf ein Auto dahinter kombiniert .

Aber wenn der Wirt Tür 2 öffnet und die Ziege enthüllt, haben Sie plötzlich mehr Informationen über das Problem.

Denken Sie daran, dass die Türen 2 und 3 eine kombinierte Wahrscheinlichkeit haben, das Auto 2/3 der Zeit zu verstecken. Als Tür 2 geöffnet wurde, wissen Sie, dass sich kein Auto dahinter befand.

Diese Enthüllung ändert jedoch nichts an der kombinierten Wahrscheinlichkeit der beiden Türen. Das ist der Schlüssel zum Mitnehmen hier!

Da Sie wissen, dass Tür 2 eine 0/3-Chance hat, das Auto zu verstecken, können Sie jetzt sagen, dass es eine 2/3 Chance gibt, dass sich das Auto hinter Tür 3 befindet. Tür 1 bleibt unverändert - es gibt nur ein 1/3 des Autos dahinter.

Wenn Sie sich also für einen Wechsel entscheiden, steigen Sie von einer Chance von ungefähr 33,33% auf eine Chance von 66,67%, das Auto zu finden. Mit anderen Worten, Sie verdoppeln Ihre Erfolgschancen, indem Sie stattdessen Tür 3 öffnen!

Ja, es ist möglich, dass sich Tür 1 die ganze Zeit versteckt hat und der Gastgeber Sie ausgetrickst hat. Das ist egal. Sie spielen, indem Sie den Deal abschließen, aber Sie spielen klug. Sie sollten mit den Informationen, die Sie erhalten, die beste Entscheidung treffen und die Würfel rollen lassen.

Auf lange Sicht würden Sie durch einen Wechsel eine bessere Leistung erbringen als ein Kandidat, der sich für seine erste Wahl entscheidet. Obwohl es nicht sofort offensichtlich ist, tut der Gastgeber Ihnen tatsächlich einen Gefallen, indem er Ihnen ein besseres Angebot macht.

Das Problem der Speisephilosophen

Das Problem der Essensphilosophen ist ein klassisches Beispiel in der Informatik, um Probleme mit der Synchronisation zu veranschaulichen. Es wurde ursprünglich von Edsger Dijkstra im Jahr 1965 erstellt, der es seinen Schülern als eine Handvoll Computer vorstellte, die um den Zugriff auf gemeinsam genutzte Bandlaufwerke konkurrierten.

Stellen Sie sich fünf stille Philosophen vor, die an einem Tisch sitzen und jeweils eine Schüssel Spaghetti haben. Zwischen jedem Paar benachbarter Philosophen liegen Gabeln auf dem Tisch.

Jeder Philosoph kann immer nur eines tun: denken und essen. Ein Philosoph kann jedoch nur Spaghetti essen, wenn er sowohl die linke als auch die rechte Gabel hat. Eine Gabel kann jeweils nur von einem Philosophen gehalten werden.

Nachdem ein Philosoph mit dem Essen fertig ist, muss er sowohl die linke als auch die rechte Gabel ablegen, damit sie den anderen zur Verfügung stehen. Ein Philosoph kann eine Gabel nehmen, sobald sie verfügbar ist, aber erst dann mit dem Essen beginnen, wenn er beide Gabeln hat.

Die Philosophen sind berühmt für ihren Appetit - sie können alle endlos essen und werden nie satt. Darüber hinaus füllen sich die Schalen mit Spaghetti auf magische Weise wieder auf, egal wie viel gegessen wird.

Das Problem ist, wie können Sie sicherstellen, dass kein Philosoph verhungert und dass er für immer weiter essen und denken kann?

Synchronisation und Deadlock

In einfachen Worten ist das Problem der Speisephilosophen ein Beispiel dafür, wie der synchronisierte Zugriff auf eine gemeinsam genutzte Ressource zur Entstehung einer Deadlock-Situation führen kann.

Die Synchronisierung wird verwendet, um den gleichzeitigen Zugriff auf eine gemeinsam genutzte Ressource zu steuern. Dies ist in jeder Situation erforderlich, in der mehrere unabhängige Akteure um die Verwendung einer Ressource wie der Gabeln konkurrieren können. Da nur eine Ressource verfügbar ist, verwenden wir die Synchronisierung, um Verwirrung und Chaos zu vermeiden.

Ein Deadlock ist ein Systemstatus, in dem kein Fortschritt möglich ist. Diese Situation kann auftreten, wenn die Synchronisierung erzwungen wird und viele Prozesse auf eine gemeinsam genutzte Ressource warten, die von einem anderen Prozess gehalten wird. Wie bei den Philosophen, die entweder nicht essen oder denken, warten die Prozesse einfach weiter und werden nicht weiter ausgeführt.

Lösungen

Auf den ersten Blick scheint es nicht möglich zu sein, dass alle Philosophen entweder essen oder denken. Das Muster für jeden Philosophen könnte beispielsweise sein:

1: Denken Sie nach, bis die linke Gabel verfügbar ist. wenn es ist, nimm es auf;

2: Denken Sie nach, bis die richtige Gabel verfügbar ist. wenn es ist, nimm es auf;

3: Wenn beide Gabeln gehalten werden, essen Sie für eine feste Zeit;

4: dann lege die rechte Gabel hin;

5: dann lege die linke Gabel hin;

6: von Anfang an wiederholen.

Quelle: Wikipedia

Es gibt viele mögliche Lösungen, um einen Deadlock zu verhindern. Wenn wir genau hinschauen, besteht ein Problem im obigen Algorithmus darin, dass alle Philosophen die gleiche Chance (die gleiche Priorität) haben, eine Gabel zu erwerben. Dies verhindert, dass jemand zwei Gabeln erwirbt und das gesamte System zum Stillstand kommt.

Hier sind einige mögliche Lösungen:

  1. Priorität : Einige Philosophen erhalten eine höhere Priorität, so dass die Chance, beide Gabeln zu erwerben, erhöht wird.
  2. Preemption (Höflichkeit): Philosophen geben die erworbene Gabel ohne zu essen auf, falls die andere Gabel nicht verfügbar ist.
  3. Schiedsgerichtsbarkeit : Ein Mediator weist Gabeln zu, um sicherzustellen, dass zwei Gabeln einer Person anstatt einer zu vielen gegeben werden.

Nachdem Sie nun wissen, wie Sie diese logischen Rätsel lösen können, gönnen Sie sich eine endlose Schüssel Spaghetti. Du hast es verdient.