Задача о ста заключённых
Ого, пожалуй, самый не-плодотворный во всех смыслах месяц выдаётся за неопределённый период.
А всё почему? Не было положенного летнего перерыва с минимумом компов, интернетов и особенно людей. И день мой стал как ночь, а ночь не питает день снами :)
Сегодня, например, долго снился какой-то муторный военизированно-лягушачий мир, примерно как тут, сейчас, пару часов с утра поработав (опять же, сплошные доделки и исправления, ничего нового), помню только военные звания - болотник, окружбол, обергадмейстер, гадмейстер и ещё кто-то.
Чтобы заметка не была пустой, решим лучше задачу о ста зеках. Она показывает, как важно открывать правильные ящики - шансы выжить из нулевых становятся около волшебной одной трети :)
#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 %
20.03.2021, 08:36 [1043 просмотра]