1

我在读一本书，叫《概率中的 50 个具有挑战性的问题》，里面有很多与概率相关的脑筋急转弯。我无法解决其中的一个问题，也无法理解解决方案。所以，我正在编写代码以获得更好的感觉。这是原始问题。

The Theatre Row：八位优秀的单身汉和七位漂亮的模特随机购买了同一排 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（男性）。然后它“减少”随机序列，以便没有重复的 0 或 1。例如，如果代码生成一个随机序列 011100110010011（有 7 个相邻对），则将序列缩减为 01010101。在缩减格式中，要计算出相邻对的数量，只需获取“大小- 1"。

这是我的问题。

  1. 这个问题的答案（根据本书）是 7.47，而我从代码中得到的平均约为 7 左右。有人看到差异的来源吗？

  2. 我的代码有时似乎效率很低。是因为我生成随机序列的方式吗？（如您所见，为了生成 8 名男性和 7 名女性的随机序列，我一直要求一个大小为 15 的随机序列，直到它恰好有 8 名男性（或“1”）和 7 名女性（或“0”） .当有这样的约束时，有没有更好的方法来产生随机序列？

在编程方面我不是很熟练。我会很感激任何评论。谢谢你的帮助！！

4

1 回答 1

0

这个问题很搞笑。

有 1307674368000 种可能的组合。

有 203212800 种组合，其中一对情侣聚在一起。

但是有 3048192000 个组合，其中 2 对情侣聚在一起。

认为这个问题的关键是先做一个小规模的问题，然后使用这些信息来创建你的答案。这只是一个期望值问题。

编辑：而不是运行模拟，您可以使用预期值获得确切的答案，必须更加努力地思考，但您也将是准确的。我会花一点时间看看我是否能想出确切的答案并发布它。

重要编辑（阅读）：

如果您获得超过 8 个 0 或 8 个 1，您的代码是否考虑在内。感觉你最多只能有 8 个男人和 7 个女人，那么它应该会自动感觉到剩下的符号。

于 2015-01-23T16:24:34.900 回答