Викиучебник

Реализации алгоритмов/Парадокс Монти Холла: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Строка 1:
Здесь приведены программы на разных языках программирования, моделирующие события игры, описанной в статье [[w:Парадокс Монти Холла|Парадокс Монти Холла]].
__FORCETOC__
 
== [[Python]] ==
Вывод программы — это число раз (из 10000), когда победил участник, не сменивший решение и затем число раз когда победил участник сменивший решение.
Строка 95 ⟶ 96 :
</source>
 
== [[:w:C++|Си++]] ==
== Программа на [[Javascript]], моделирующая задачу. ==
Вычисление условных вероятностей по [[Теорема Байеса|теореме Байеса]]. <br />
Если слева и справа отобразить мнимые двери, периодически повторяющиеся, то получим:
-0,-1,[-2,'''0,1,2,'''+0],+1,+2 <br />
В этом случае можно точно утвержать, что какую бы дверь не выбрал игрок, ведущий откроет, или следующую, или предыдущую. <br />
Если игрок выбрал дверь 0, то предыдущая будет -2 или, что эквивалентно, просто 2. <br />
Если игрок выбрал дверь 2, то следующая будет +0 или, что эквивалентно, просто 0. <br />
В решении задачки по Байесу эту симметрию оговаривали и считали, что игрок выбирает всегда нулевую дверь, от этого допущения смысл не меняется. <br />
Поэтому эксперимент расскладывается на две группы не пересекающихся событий: <br />
0)Ведущий открыл следующую, от выбранной игроком, дверь. <br />
1)Ведущий открыл предыдущую, от выбранной игроком, дверь. <br />
Все вероятности подсчитываются для каждого из событий 0) и 1) отдельно. <br />
Кроме стратегий игрока "менять выбор" и "не менять выбор", добавлены стратегии ведущего "честный", "нечестный 0" и "нечестный 1".
<source lang="cpp">
using namespace std;
 
// равновероятная генерация случайных чисел 0, 1
int rand2()
{
return (rand() % 2);
}
 
// равновероятная генерация случайных чисел 0, 1, 2
int rand3()
{
return (rand() % 3);
}
 
// случайно прячем приз
class CSituation
{
public:
void GenerateRandom()
{
m_nPriceNo = rand3();
m_bOpened[0] = m_bOpened[1] = m_bOpened[2] = false;
m_nOpenedByAnchor = -1;
m_nSelectedByUserFirstTime = m_nSelectedByUserSecondTime = -1;
}
 
bool m_bOpened[3]; // двери
int m_nPriceNo; // где спрятан приз
 
// выбор игрока и ведущего
int m_nSelectedByUserFirstTime, m_nSelectedByUserSecondTime, m_nOpenedByAnchor;
};
 
// стратегия честного ведущего,
// игроку выгодно менять выбор, шансы удваиваются
class CAnchorStrategyOpenRandom
{
public:
static void Act(CSituation& situation)
{
int arVars[2] =
{
(situation.m_nSelectedByUserFirstTime + 1) % 3,
(situation.m_nSelectedByUserFirstTime + 2) % 3
};
// Ведущий открывает случайную дверь, если игрок первым выбором угадал приз
int nVariantNo = rand2();
int nVariant = arVars[nVariantNo];
if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo];
situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true;
}
 
static char* GetName(){return "Anchorman randomly opens an empty door, 50% : 50%";}
};
 
// 0 стратегия нечестного ведущего,
// для игрока не важно менять выбор или нет, шансы равны,
// в ситуации если ведущим открыта дверь, следующая сразу за выбранной игроком
class CAnchorStrategyOpenNotRandom0
{
public:
static void Act(CSituation& situation)
{
int arVars[2] =
{
(situation.m_nSelectedByUserFirstTime + 1) % 3,
(situation.m_nSelectedByUserFirstTime + 2) % 3
};
// Ведущему больше нравится дверь, следующая сразу за выбранной игроком.
// Если он её отркыл, значит приз равновероятно может находиться в двух оставшихся.
int nVariantNo = 0;
int nVariant = arVars[nVariantNo];
if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo];
situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true;
}
 
static char* GetName(){return "Anchorman tries to open only the next empty door.";}
};
 
// 1 стратегия нечестного ведущего,
// меняя выбор, игрок гарантированно выигрывает приз,
// в ситуации если открыта дверь, следующая сразу за выбранной игроком
class CAnchorStrategyOpenNotRandom1
{
public:
static void Act(CSituation& situation)
{
int arVars[2] =
{
(situation.m_nSelectedByUserFirstTime + 1) % 3,
(situation.m_nSelectedByUserFirstTime + 2) % 3
};
// Ведущему больше нравится дверь, идущая перед выбранной игроком.
// Если он её не отркыл, значит там точно лежит приз.
int nVariantNo = 1;
int nVariant = arVars[nVariantNo];
if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo];
situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true;
}
 
static char* GetName(){return "Anchorman tries to open only the previous empty door.";}
};
 
// выбор игроком двери
class CUserStrategySelectFirst
{
public:
static void Act(CSituation& situation)
{
situation.m_nSelectedByUserFirstTime = rand3();
}
};
 
// игрок не меняет выбор
class CUserStrategyKeepTheChoose
{
public:
static void Act(CSituation& situation)
{
situation.m_nSelectedByUserSecondTime = situation.m_nSelectedByUserFirstTime;
situation.m_bOpened[situation.m_nSelectedByUserSecondTime] = true;
}
 
static char* GetName(){return "Keep the choose";}
};
 
// игрок меняет выбор
class CUserStrategyChange
{
public:
static void Act(CSituation& situation)
{
situation.m_nSelectedByUserSecondTime = (situation.m_nSelectedByUserFirstTime + 1) % 3;
if(situation.m_bOpened[situation.m_nSelectedByUserSecondTime])
situation.m_nSelectedByUserSecondTime = (situation.m_nSelectedByUserSecondTime + 1) % 3;
situation.m_bOpened[situation.m_nSelectedByUserSecondTime] = true;
}
 
static char* GetName(){return "Change the choose";}
};
 
// симуляция игры
// TUserStrategy - стратегия игрока
// TAnhorStrategy - стратегия ведущего
// nCountIteration - количество испытаний
template<class TUserStrategy, class TAnhorStrategy, int nCountIteration>
void TestFull()
{
const char* pcszDesc0 = "next door was opened";
const char* pcszDesc1 = "previous door was opened";
 
int nWin[2] = {0};
int nLoose[2] = {0};
const char* aDesc[] = {pcszDesc0, pcszDesc1};
 
CSituation situation;
 
for(int i = 0; i < nCountIteration; i++)
{
situation.GenerateRandom();
 
CUserStrategySelectFirst::Act(situation);
 
TAnhorStrategy::Act(situation);
TUserStrategy::Act(situation);
 
int iNextDoor = (situation.m_nSelectedByUserFirstTime + 1)%3;
bool bIsConditionNextDoor = (situation.m_nOpenedByAnchor == iNextDoor);
int iCondition = bIsConditionNextDoor?0:1;
 
// Посчитаем шансы на выигрыш для каждой ситуации:
// 0 - известно, что ведущий открыл дверь, которая сразу следует за выбранной игроком
// 1 - известно, что ведущий открыл дверь, которая предшествует выбранной игроком
 
if( situation.m_bOpened[situation.m_nPriceNo])
{
nWin[iCondition]++;
}
else
{
nLoose[iCondition]++;
}
}
 
for(int i = 0; i < sizeof(nWin)/sizeof(int); i++)
{
int nCount = nWin[i] + nLoose[i];
cout << i << ") " << aDesc[i] << " (" << nCount*100/nCountIteration << "%)" << " - ";
cout << "Wins: " << nWin[i] << " (" << nWin[i]*100/nCount << "%)" << "; ";
cout << "Loose: " << nLoose[i] << " (" << nLoose[i]*100/nCount << "%)" << endl;
}
}
 
// две стратегии игрока, для одной стратегии ведущего
// TAnhorStrategy - стратегия ведущего
// nCountIteration - количество испытаний
template<class TAnhorStrategy, int nCountIteration>
void Test()
{
cout << "========================================================" << endl;
cout << "Anchorman strategy: " << TAnhorStrategy::GetName() << endl;
cout << endl;
cout << "User strategy: " << CUserStrategyKeepTheChoose::GetName() << endl;
TestFull<CUserStrategyKeepTheChoose, TAnhorStrategy, nCountIteration>();
 
cout << endl;
 
cout << "User strategy: " << CUserStrategyChange::GetName() << endl;
TestFull<CUserStrategyChange, TAnhorStrategy, nCountIteration>();
 
cout << endl;
}
 
// главная точка входа программы
int _tmain(int argc, _TCHAR* argv[])
{
srand( (unsigned)time( NULL ) );
 
const int nCountIteration = 1500000; // количество испытаний
 
cout << "Number of iteration: " << nCountIteration << endl;
Test<CAnchorStrategyOpenRandom, nCountIteration>(); // честный ведущий
Test<CAnchorStrategyOpenNotRandom0, nCountIteration>(); // нечестный 0
Test<CAnchorStrategyOpenNotRandom1, nCountIteration>(); // нечестный 1
 
cin.get();
 
return 0;
}
</source>
 
Вывод (пример)
<source lang="text">
Number of iteration: 1500000
========================================================
Anchorman strategy: Anchorman randomly opens an empty door, 50% : 50%
 
User strategy: Keep the choose
0) next door was opened (50%) - Wins: 249595 (33%); Loose: 500575 (66%)
1) previous door was opened (49%) - Wins: 249423 (33%); Loose: 500407 (66%)
 
User strategy: Change the choose
0) next door was opened (50%) - Wins: 499649 (66%); Loose: 250748 (33%)
1) previous door was opened (49%) - Wins: 499504 (66%); Loose: 250099 (33%)
 
========================================================
Anchorman strategy: Anchorman tries to open only the next empty door.
 
User strategy: Keep the choose
0) next door was opened (66%) - Wins: 500077 (50%); Loose: 499641 (49%)
1) previous door was opened (33%) - Wins: 0 (0%); Loose: 500282 (100%)
 
User strategy: Change the choose
0) next door was opened (66%) - Wins: 500856 (50%); Loose: 500137 (49%)
1) previous door was opened (33%) - Wins: 499007 (100%); Loose: 0 (0%)
 
========================================================
Anchorman strategy: Anchorman tries to open only the previous empty door.
 
User strategy: Keep the choose
0) next door was opened (33%) - Wins: 0 (0%); Loose: 499974 (100%)
1) previous door was opened (66%) - Wins: 499930 (49%); Loose: 500096 (50%)
 
User strategy: Change the choose
0) next door was opened (33%) - Wins: 500122 (100%); Loose: 0 (0%)
1) previous door was opened (66%) - Wins: 499991 (50%); Loose: 499887 (49%)
</source>
 
--[[Участник:ViPetroFF|ViPetroFF]] 18:00, 8 октября 2009 (UTC)
== Программа на [[Javascript]], моделирующая задачу ==
Можно просто вставить в файл monty-hall.html и открыть в браузере
 
Строка 184 ⟶ 468 :
</pre>
 
== Программа на Turbo [[Pascal]], моделирующая задачу. ==
 
<pre>
Строка 282 ⟶ 566 :
end.
</pre>
Из миллиона вариантов это программа показала верными 555830, что превышает 50 %.
 
== Программа на [http://ru.wikipedia.org/wiki/Delphi_(%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F) Delphi] ==
 
Программа на [http://ru.wikipedia.org/wiki/Delphi_(%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F) Delphi] , позволяющая пользователю вводить кол-во итераций и случайным образом рассчитывать на ПК кол-во выигрышей.
 
<pre>
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Парадокс_Монти_Холла