Код для решения головоломки "Театральный ряд"
Я читал книгу под названием "Пятьдесят сложных проблем вероятности", в которой много дразнилок, связанных с вероятностью. Я не смог решить одну из проблем и не смог понять решение. Итак, я писал код, чтобы почувствовать себя лучше. Вот оригинальная проблема.
Театральный ряд: восемь элегантных холостяков и семь прекрасных моделей случайно приобрели отдельные места в одном и том же 15-местном ряду театра. В среднем, сколько пар смежных мест выбрано для супружеских пар?
А вот мой код, получающий среднее количество соседних пар из 100 случайных выборок:
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <numeric>
using namespace std;
// computes the probability for the "theater row" problem
// in the book fifty challenging probabilty problems.
vector<int> reduce(vector<int>& seats); // This function reduces a sequence to a form
// in which there is no adjacent 0's or 1's.
// *example: reduce(111001)=101*
int main()
{
srand(time(0));
int total=15;
int Num=100;
int count0=0; // number of women
int count1=0; // number of men
vector<int> seats; // vector representing a seat assignment,
// seats.size()=total
vector<int> vpair; // vector that has number of adjacent pairs
// as its element, size.vpair()=Num
for (int i=0; i<Num; ++i) {
count0=count1=0;
while ((count1-count0)!=1) {
count0=count1=0;
seats.clear();
for (int j=0; j<total; ++j) {
int r=rand()%2;
if (r==0)
++count0;
else
++count1;
seats.push_back(r);
}
}
for (int k=0;k<seats.size();++k)
cout<<seats[k];
reduce(seats);
for (int k=0;k<seats.size();++k)
cout<<" "<<seats[k];
vpair.push_back(seats.size()-1); // seats.size()-1 is the number
// of adj pairs.
cout<<endl;
}
double avg=static_cast<double>(accumulate(vpair.begin(),vpair.end(),0))/vpair.size();
cout<<"average pairs: "<<avg<<endl;
return 0;
}
vector<int> reduce(vector<int>& seats)
{
vector<int>::iterator iter = seats.begin();
while (iter!=seats.end()) {
if (iter+1==seats.end())
++iter;
else if (*iter==*(iter+1))
iter=seats.erase(iter);
else
++iter;
}
return seats;
}
Код генерирует случайные серии из 0 (представляющих женщин) и 1 (мужчин). Затем он "уменьшает" случайную последовательность, чтобы не было повторяющихся нулей или единиц. Например, если код генерирует случайную последовательность 011100110010011 (которая имеет 7 смежных пар), последовательность сокращается до 01010101. В уменьшенном формате, чтобы выяснить количество соседних пар, вам просто нужно получить "size-1".
Вот мои вопросы.
Ответ на вопрос (согласно книге) - 7,47, а я получаю в среднем около 7 или около того из кода. Кто-нибудь видит, где возникает расхождение?
Мой код иногда кажется неэффективным. Это связано с тем, как я генерирую случайную последовательность? (Как видите, для генерации случайной последовательности из 8 мужчин и 7 женщин я продолжаю просить случайную последовательность размером 15, пока в ней не будет 8 мужчин (или "1") и 7 женщин (или "0") Есть ли лучший способ для создания случайной последовательности, когда есть такое ограничение?
Я не очень опытный, когда дело доходит до программирования. Буду признателен за любые комментарии. Спасибо за помощь!!
1 ответ
Эта проблема смешная.
Есть 1307674368000 возможных комбинаций.
Есть 203212800 комбинаций, в которых собирается 1 пара.
Но есть 3048192000 комбинаций, в которых собираются две пары.
Подумайте, что ключом к этой проблеме было бы сначала сделать проблему меньшего масштаба, и используйте эту информацию, чтобы создать свой ответ. Это просто ожидаемая проблема стоимости.
Изменить: вместо запуска моделирования, вы можете просто получить точный ответ, используя ожидаемое значение, придется подумать сложнее, но вы также будете точны. Я возьму немного, чтобы посмотреть, смогу ли я придумать точный ответ и опубликовать его.
Важно Редактировать (Читать):
Имеет ли ваш код учетную запись, если вы получаете более 8 0 или 8 1. В смысле, вы можете иметь максимум 8 мужчин и 7 женщин, тогда он должен автоматически чувствовать остальное с помощью оставшихся символов.