77 lines
2.1 KiB
C++
77 lines
2.1 KiB
C++
#include <cstdlib> // for rand
|
|
#include <algorithm> // for random_shuffle
|
|
#include <iostream> // for output
|
|
|
|
using namespace std;
|
|
|
|
class cupboard {
|
|
public:
|
|
cupboard() {
|
|
for (int i = 0; i < 100; i++)
|
|
drawers[i] = i;
|
|
random_shuffle(drawers, drawers + 100);
|
|
}
|
|
|
|
bool playRandom();
|
|
bool playOptimal();
|
|
|
|
private:
|
|
int drawers[100];
|
|
};
|
|
|
|
bool cupboard::playRandom() {
|
|
bool openedDrawers[100] = { 0 };
|
|
for (int prisonerNum = 0; prisonerNum < 100; prisonerNum++) { // loops through prisoners numbered 0 through 99
|
|
bool prisonerSuccess = false;
|
|
for (int i = 0; i < 100 / 2; i++) { // loops through 50 draws for each prisoner
|
|
int drawerNum = rand() % 100;
|
|
if (!openedDrawers[drawerNum]) {
|
|
openedDrawers[drawerNum] = true;
|
|
break;
|
|
}
|
|
if (drawers[drawerNum] == prisonerNum) {
|
|
prisonerSuccess = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!prisonerSuccess)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool cupboard::playOptimal() {
|
|
for (int prisonerNum = 0; prisonerNum < 100; prisonerNum++) {
|
|
bool prisonerSuccess = false;
|
|
int checkDrawerNum = prisonerNum;
|
|
for (int i = 0; i < 100 / 2; i++) {
|
|
if (drawers[checkDrawerNum] == prisonerNum) {
|
|
prisonerSuccess = true;
|
|
break;
|
|
} else
|
|
checkDrawerNum = drawers[checkDrawerNum];
|
|
}
|
|
if (!prisonerSuccess)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
double simulate(char strategy) {
|
|
int numberOfSuccesses = 0;
|
|
for (int i = 0; i < 10000; i++) {
|
|
cupboard d;
|
|
if ((strategy == 'R' && d.playRandom()) || (strategy == 'O' && d.playOptimal())) // will run playRandom or playOptimal but not both because of short-circuit evaluation
|
|
numberOfSuccesses++;
|
|
}
|
|
|
|
return numberOfSuccesses * 100.0 / 10000;
|
|
}
|
|
|
|
int main() {
|
|
cout << "Random strategy: " << simulate('R') << " %" << endl;
|
|
cout << "Optimal strategy: " << simulate('O') << " %" << endl;
|
|
system("PAUSE"); // for Windows
|
|
return 0;
|
|
}
|