1

私は「確率に関する 50 の挑戦的な問題」という本を読んでいました。この本には、確率に関する多くの頭の体操が詰まっています。私はそこにある問題の 1 つを解決できず、解決策も理解できませんでした。それで、私はより良い感じを得るためにコードを書いていました. 元の問題はこちら。

The Theater Row: 8 人の有能な独身男性と 7 人の美しいモデルが、たまたま劇場の同じ 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 に縮小されます。縮小された形式では、隣接するペアの数を計算するには、「size- 1」。

これが私の質問です。

  1. 質問への答え (本によると) は 7.47 ですが、コードからは平均で約 7 が得られます。不一致がどこで発生したかを誰かが見ていますか?

  2. 私のコードは時々非常に非効率的です。ランダムなシーケンスを生成する方法が原因ですか? (ご覧のとおり、8 人の男性と 7 人の女性のランダムなシーケンスを生成するために、たまたま 8 人の男性 (または「1」) と 7 人の女性 (または「0」) になるまで、サイズ 15 のランダムなシーケンスを要求し続けます)このような制約がある場合、ランダムなシーケンスを生成するより良い方法はありますか?

プログラミングに関しては、私はそれほど熟練していません。コメントをいただければ幸いです。助けてくれてありがとう!!

4

1 に答える 1