Код для решения головоломки "Театральный ряд"

Я читал книгу под названием "Пятьдесят сложных проблем вероятности", в которой много дразнилок, связанных с вероятностью. Я не смог решить одну из проблем и не смог понять решение. Итак, я писал код, чтобы почувствовать себя лучше. Вот оригинальная проблема.

Театральный ряд: восемь элегантных холостяков и семь прекрасных моделей случайно приобрели отдельные места в одном и том же 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".

Вот мои вопросы.

  1. Ответ на вопрос (согласно книге) - 7,47, а я получаю в среднем около 7 или около того из кода. Кто-нибудь видит, где возникает расхождение?

  2. Мой код иногда кажется неэффективным. Это связано с тем, как я генерирую случайную последовательность? (Как видите, для генерации случайной последовательности из 8 мужчин и 7 женщин я продолжаю просить случайную последовательность размером 15, пока в ней не будет 8 мужчин (или "1") и 7 женщин (или "0") Есть ли лучший способ для создания случайной последовательности, когда есть такое ограничение?

Я не очень опытный, когда дело доходит до программирования. Буду признателен за любые комментарии. Спасибо за помощь!!

1 ответ

Эта проблема смешная.

Есть 1307674368000 возможных комбинаций.

Есть 203212800 комбинаций, в которых собирается 1 пара.

Но есть 3048192000 комбинаций, в которых собираются две пары.

Подумайте, что ключом к этой проблеме было бы сначала сделать проблему меньшего масштаба, и используйте эту информацию, чтобы создать свой ответ. Это просто ожидаемая проблема стоимости.

Изменить: вместо запуска моделирования, вы можете просто получить точный ответ, используя ожидаемое значение, придется подумать сложнее, но вы также будете точны. Я возьму немного, чтобы посмотреть, смогу ли я придумать точный ответ и опубликовать его.

Важно Редактировать (Читать):

Имеет ли ваш код учетную запись, если вы получаете более 8 0 или 8 1. В смысле, вы можете иметь максимум 8 мужчин и 7 женщин, тогда он должен автоматически чувствовать остальное с помощью оставшихся символов.

Другие вопросы по тегам