Startseite → Matherätsel → Das Ziegenproblem → Lösung

Lösung: Das Ziegenproblem

Rätsel einblenden

Lösung

Zuerst entscheidet sich der Kandidat für eine Tür. Die Wahrscheinlichkeit, dass das Auto dahinter steht liegt bei 1/3. Die Wahrscheinlichkeit, dass es hinter einer der beiden anderen Türen steht liegt also bei 2/3. Daran ändert auch die Tatsache, dass eine der beiden anderen Türen geöffnet wurde, nichts. Folglich wäre es für den Kandidaten besser, die Tür zu wechseln, denn damit erhöht er seine Gewinnchance von 1/3 auf 2/3.

Ausblenden

Simulationsprogramm

Wer das so nicht glauben kann, der möge sich mal das folgende Simulationsprogramm ansehen, kompilieren (dazu werden die QT-Bibliotheken benötigt) und ausführen. Das Programm basiert auf Threads, kann also die Rechenleistung von Multicore-Prozessoren voll ausnutzen. Es besteht im Wesentlich aus zwei Klassen: einer, in der die eigentliche Simulation implementiert ist und einer, die die Simulation steuert.

Zuerst ein paar Worte zur Simulations-Klasse: In dieser Klasse wurde in der run()-Methode die eigentliche Simulation implementiert. Diese benötigt an verschiedenen Stellen Zufallszahlen. Diese werden durch einen linearen Kongruenzgenerator "errechnet", da der in der cstdlib-Bibliothek implementierte Zufallszahlengenerator nicht so effizient ist. Im Prinzip sind hier sogar drei Generatoren implementiert: einer für das Auto, einer für den Kandidaten und einer für den Moderator. Würde alles über einen Generator laufen, so wären die Zufallszahlen innerhalb einer Spielrunde voneinander abhängig, was das Ergebnis etwas verfälschen würde.

C++/QT-Code
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <QThread>

  5. class Simulation : public QThread {

  7.   private:
  8.   // Konstanten fuer den Zufallszahlengenerator
  9.   static const unsigned long MASK = (1L << 48) - 1;
  10.   static const unsigned long ADD = 0xBL;
  11.   static const unsigned long MULTIPLIER = 0x5DEECE66DL;
  12.   // Hier werden die letzten Zufallszahln gespeichert
  13.   unsigned long m_random[3];
  14.   // Durchlaufzaehler
  15.   int m_counter;
  16.   // mit oder ohne Wechseln
  17.   bool m_shift;
  18.   // Zeiger auf den Gewinnzaehler
  19.   int *m_wins;

  21.   public:
  22.   Simulation(int counter, bool shift, int *wins) {
  23.   m_counter = counter;
  24.   m_shift = shift;
  25.   m_wins = wins;
  26.   // Drei unabhaengige Zufallszahlengeneratoren initialisieren
  27.   for (int i=0;i<3;i++) {
  28.   m_random[i] = rand();
  29.   }
  30.   }

  32.   protected:
  33.   void run() {
  34.   // So oft hat der Kandidat in diesem Thread schon gewonnen
  35.   int wins = 0;
  36.   while (m_counter > 0) {
  37.   // Das Auto wird versteckt
  38.   int car = getRandom(3,0);
  39.   // Der Kandidat entscheidet sich fuer eine Tuer
  40.   int kandidat = getRandom(3,1);
  41.   // Diese Tueren darf der Moderator nicht oeffnen
  42.   bool blocked[3];
  43.   for (int i=0;i<3;i++) {
  44.   blocked[i] = false;
  45.   }
  46.   // Naemlich die mit dem Auto
  47.   blocked[car] = true;
  48.   // und die mit dem Kandidaten
  49.   blocked[kandidat] = true;
  50.   // Jetzt sucht er sich zufaellig Tueren raus, bis
  51.   // eine nicht blockiert ist, und oeffnet diese
  52.   int opened;
  53.   do {
  54.   opened = getRandom(3,2);
  55.   } while (blocked[opened]);
  56.   // Je nachdem, was simuliert wird: Wechseln oder nicht.
  57.   if (m_shift) {
  58.   // Das ist genau die andere verschlossene Tuer
  59.   kandidat = 3 - (kandidat + opened);
  60.   }
  61.   // Gewinnt der Kandidat das Auto?
  62.   if (car == kandidat) {
  63.   wins++;
  64.   }
  65.   // Durchlauf vorbei: Zaehler eins runterzaehlen
  66.   m_counter--;
  67.   }
  68.   // Zum Gesamtergebnis dazuaddieren
  69.   (*m_wins) += wins;
  70.   }

  72.   private:
  73.   int getRandom(long n, int i) {
  74.   // linearer Kongruenzgenerator
  75.   m_random[i] = (MULTIPLIER*m_random[i]+ADD)%MASK;
  76.   return static_cast<int>(m_random[i]%n);
  77.   }

  79. };

Die andere Klasse steuert den Ablauf der Simulation. Im Wesentlichen besteht der Sinn dieser Klasse darin, mehrere Threads zu starten, zu warten, bis diese mit der Simulation fertig sind und zum Schluss das Ergebnis auszugeben. Etwas verwirrend ist vielleicht, dass theThreads.at(i)->start() die run()-Methode der Simulationsklasse aufruft, aber das ist bei der Threadprogrammierung halt so.

C++/QT-Code
  1. #include <vector>
  2. #include <iostream>

  4. #include "Simulation.hpp"

  6. class LetsMakeADeal {

  8.   private:
  9.   // So viele Threads sollen gleichzeitig laufen
  10.   int m_threads;

  12.   public:
  13.   LetsMakeADeal(int threads) {
  14.   m_threads = threads;
  15.   // Titel ausgeben
  16.   std::cout << std::endl;
  17.   std::cout << "Simulation der TV-Show Let's make a deal: "
  18.   << "Das Ziegenproblem" << std::endl;
  19.   std::cout << std::endl;
  20.   }

  22.   void tvShow(int runs, bool shift) {
  23.   // Gewinne zaehlen
  24.   int wins = 0;
  25.   // Hier werden die verschiedenen Threads gespeichert
  26.   std::vector<Simulation*> theThreads;
  27.   // Der erste Thread faengt den Fehler der Integerdivision ab
  28.   int counter = runs / m_threads + runs % m_threads;
  29.   theThreads.push_back(new Simulation(counter,shift,&wins));
  30.   // Der Rest wird auf die anderen Threads aufgeteilt
  31.   counter = runs / m_threads;
  32.   for (int i=1;i<m_threads;i++) {
  33.   theThreads.push_back(new Simulation(counter,shift,&wins));
  34.   }
  35.   // Threads starten
  36.   for (int i=0;i<m_threads;i++) {
  37.   theThreads.at(i)->start();
  38.   }
  39.   // Bis alle Threads fertig sind warten
  40.   for (int i=0;i<m_threads;i++) {
  41.   theThreads.at(i)->wait();
  42.   }
  43.   // Das Ergebnis der Simulation ausgeben
  44.   std::cout << "Simulation " << (shift ? "mit" : "ohne")
  45.   << " Wechsel der Tuer." << std::endl;
  46.   std::cout << wins << " Gewinne in " << runs
  47.   << " Runden." << std::endl;
  48.   std::cout << "Anteil der Gewinne: "
  49.   << ((double)wins)/((double)runs) << std::endl;
  50.   std::cout << std::endl;
  51.   }

  53. };

Zur main()-Methode gibt es nicht viel zu sagen. Hier werden die für die Simulation relevanten Konstanten festgelegt und die Simulation einmal mit einem "Wechsel-Kandidaten" und einmal mit einem "nicht-Wechsel-Kandidaten" gestartet.

C++/QT-Code
  1. #include "LetsMakeADeal.hpp"

  3. int main() {
  4.   // So oft soll simuliert werden
  5.   const int RUNS = 2147483647;
  6.   // So viele Threads sollen benutzt werden
  7.   const int THREADS = 2;
  8.   // Zufallszahlengenerator initialisieren
  9.   srand((unsigned)time(NULL));
  10.   // Simuliere mit Threads
  11.   LetsMakeADeal* theShow = new LetsMakeADeal(THREADS);
  12.   // Zuerst mit Wechseln
  13.   theShow->tvShow(RUNS,true);
  14.   // dann ohne Wechseln
  15.   theShow->tvShow(RUNS,false);
  16.   return 0;
  17. }

Ich habe das Programm mit diesen Konstanten auf meinem Rechner (CPU: AMD Turion™ 64 X2 TL-50 @ 1,6 GHz (Dual-Core)) durchlaufen lassen und habe folgendes Ergebnis bekommen:

Simulation der TV-Show Let's make a deal: Das Ziegenproblem Simulation mit Wechsel der Tuer. 1431362079 Gewinne in 2147483647 Runden. Anteil der Gewinne: 0.66653 Simulation ohne Wechsel der Tuer. 715745454 Gewinne in 2147483647 Runden. Anteil der Gewinne: 0.333295

Das ganze hat 2:38 Minuten bei voller Prozessorauslastung gedauert. Danach habe ich das Programm nochmal mit nur einem Thread, also auch nur auf einem Prozessor, gestartet. Nach 5:12 Minuten hatte ich ein ähnliches Ergebnis. Die Programmierung mit Threads hat also in diesem Fall die Laufzeit auf die Hälfte verkürzt.

Zum Abschluss habe ich das Programm dann noch mit acht Threads auf einem Server (CPU: Intel® Xeon® E5420 @ 2,5 GHz (Dual-Quad-Core)) laufen lassen. Dieser war schon nach 30 Sekunden mit der Simulation fertig.