代碼來解決「劇院行」的腦筋急轉彎

我正在讀一本叫做「五十個具有挑戰性的概率問題」的書，裏面充滿了大量的概率相關的腦筋急轉彎。我無法解決其中的一個問題，也無法理解解決方案。所以，我寫了一個代碼來獲得更好的感覺。這是最初的問題。代碼來解決「劇院行」的腦筋急轉彎

劇院行：八符合資格的單身漢和七個美女模特隨機發生的，以購買劇院的相同的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" 。

這是我的問題。

問題的答案（根據這本書）是7.47，而我從代碼中得到的平均值約爲7左右。有人看到差異的起源嗎？
我的代碼有時似乎相當低效。這是由於我產生隨機序列的方式嗎？（正如你所看到的，爲了產生8個男人和7個女人的隨機序列，我一直要求隨機序列的大小爲15，直到碰巧有8個男人（或「1」）和7個女人（或「0」）。有沒有更好的方式來產生一個隨機序列時，有這樣的限制？

我不是當涉及到編程，以便熟練。我會很感激任何意見。謝謝您的幫助！！

來源

2012-04-20 user1347035

這個劇院在哪個州？可能是100％每次。（忽略，只是一瞬間！） – Marc 2012-04-20 17:15:19

我發現了一個bug並修復了它。模擬答案似乎是正確的。 – user1347035 2012-04-20 19:20:37

如何從序列011100110010011得到答案7？這個劇院在允許一夫多妻的國家，但不是同性婚姻？爲了使它不那麼輕浮，這個問題似乎沒有說明兩對是否可以包含同一個人。 – James 2012-04-29 18:50:04

這個問題是熱鬧。

有1307674368000種可能的組合。

有1對夫婦聚在一起的有203212800個組合。

但是，有2對夫婦聚在一起的3048192000組合。

認爲這個問題的關鍵將首先做一個小規模的問題，並使用該信息來創建您的答案。這只是一個預期的價值問題。

編輯：而不是運行模擬，你可以使用期望值得到確切的答案，將不得不更加思考，但你也將是確切的。我會稍微考慮一下，看看能否拿出確切的答案併發布。

重要編輯（讀）：

請問你的代碼的帳戶，如果你，如果你獲得超過8 0或8 1的。感覺你最多隻能有8個男人和7個女人，然後它應該自動地用剩下的符號來感覺休息。

來源

2015-01-23 16:24:34 Clyde

代碼來解決「劇院行」的腦筋急轉彎

回答

相關問題