БлогNot. Задача о ста заключённых

Задача о ста заключённых

Ого, пожалуй, самый не-плодотворный во всех смыслах месяц выдаётся за неопределённый период.

А всё почему? Не было положенного летнего перерыва с минимумом компов, интернетов и особенно людей. И день мой стал как ночь, а ночь не питает день снами :)

Сегодня, например, долго снился какой-то муторный военизированно-лягушачий мир, примерно как тут, сейчас, пару часов с утра поработав (опять же, сплошные доделки и исправления, ничего нового), помню только военные звания - болотник, окружбол, обергадмейстер, гадмейстер и ещё кто-то.

Чтобы заметка не была пустой, решим лучше задачу о ста зеках. Она показывает, как важно открывать правильные ящики - шансы выжить из нулевых становятся около волшебной одной трети :)

#include <cstdlib>   // rand
#include <algorithm> // random_shuffle
#include <iostream>  // вывод
#include <iomanip>   // форматирование вывода
#include <Windows.h> // функции для консоли Studio
using namespace std;

class locker { //Шкаф
 static const int PRISONERS = 100; //З/к
public:
 locker() {
  for (int i = 0; i < PRISONERS; i++) boxes[i] = i; //Ящики
  random_shuffle(boxes, boxes + PRISONERS);
 }
 bool playRandom();
 bool playOptimal();
private:
 int boxes[PRISONERS];
};

bool locker::playRandom() { //играть случайно
 bool openedDrawers[PRISONERS] = { 0 };
 for (int prisonerNum = 0; prisonerNum < PRISONERS; prisonerNum++) { 
  //цикл по 100 зекам
  bool prisonerSuccess = false;
  for (int i = 0; i < PRISONERS / 2; i++) {  
   //один зек открывает половину ящиков
   int drawerNum = rand() % PRISONERS;
   if (!openedDrawers[drawerNum]) {
    openedDrawers[drawerNum] = true;
    break;
   }
   if (boxes[drawerNum] == prisonerNum) {
    prisonerSuccess = true;
    break;
   }
  }
  if (!prisonerSuccess) return false;
 }
 return true;
}

bool locker::playOptimal() { //Играть оптимально, насколько это здесь возможно
 for (int prisonerNum = 0; prisonerNum < PRISONERS; prisonerNum++) {
  bool prisonerSuccess = false;
  int checkDrawerNum = prisonerNum;
  for (int i = 0; i < PRISONERS / 2; i++) {
   if (boxes[checkDrawerNum] == prisonerNum) {
    prisonerSuccess = true;
    break;
   }
   else checkDrawerNum = boxes[checkDrawerNum];
  }
  if (!prisonerSuccess) return false;
 }
 return true;
}

double simulate(const int attempts, char strategy) {
 int numberOfSuccesses = 0;
 for (int i = 0; i < attempts; i++) {
  locker d;
  if ((strategy == 'R' && d.playRandom()) || 
      (strategy == 'O' && d.playOptimal())) 
   numberOfSuccesses++;
 }
 return numberOfSuccesses * 100.0 / attempts;
}

int main() {
 SetConsoleCP(1251); SetConsoleOutputCP(1251); //для Studio
 const int attempts = 10000; //Попыток
 cout << "Случайная стратегия:  " << 
  fixed << setprecision(2) << simulate(attempts, 'R') << " %" << endl;
 cout << "Оптимальная стратегия: " << 
  fixed << setprecision(2) << simulate(attempts, 'O') << " %" << endl;
 cin.get();
 return 0;
}

Пример запуска в консоли актуальной сборки Visual Studio 2019:

Случайная стратегия:  0.00 %
Оптимальная стратегия: 30.82 %


теги: c++ личное алгоритм random числа сон

20.03.2021, 08:36; рейтинг: 53