C中的對接程序？

Question

我給出的問題如下：

編寫一個程序來發現這個問題的答案的難題：「比方說，男人和女人是平等支付（從相同的均勻分佈）如果女性約會隨機嫁給第一個薪水更高的人，多少人口會結婚？「

From this site

我的問題是，它似乎％的已婚數字我得到是錯誤的。另一張海報asked this same question on the programmers exchange before，結婚的比例應該是〜68％。但是，我越來越接近75％（差異很多）。如果任何人都可以看一看，並讓我知道我出錯的地方，我會非常感激。

我意識到，看着程序員交換的另一個問題，即這不是解決問題的最有效方法。但是，我想在使用更有效的方法之前以這種方式解決問題。

我的代碼如下，問題的大部分是在測試功能「解決」：

#include <cs50.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define ARRAY_SIZE 100 
#define MARRIED 1 
#define SINGLE 0 
#define MAX_SALARY 1000000 

bool arrayContains(int* array, int val); 
int test(); 

int main() 
{ 
    printf("Trial count: "); 
    int trials = GetInt(); 

    int sum = 0; 
    for(int i = 0; i < trials; i++) 
    { 
     sum += test(); 
    } 

    int average = (sum/trials) * 100; 

    printf("Approximately %d %% of the population will get married\n", average/ARRAY_SIZE); 
} 

int test() 
{ 
    srand(time(NULL)); 

    int femArray[ARRAY_SIZE][2];  
    int maleArray[ARRAY_SIZE][2]; 

    // load up random numbers 
    for (int i = 0; i < ARRAY_SIZE; i++) 
    { 
     femArray[i][0] = (rand() % MAX_SALARY); 
     femArray[i][1] = SINGLE; 

     maleArray[i][0] = (rand() % MAX_SALARY); 
     maleArray[i][1] = SINGLE; 
    } 

    srand(time(NULL)); 
    int singleFemales = 0; 

    for (int k = 0; k < ARRAY_SIZE; k++) 
    { 
     int searches = 0; // count the unsuccessful matches 
     int checkedMates[ARRAY_SIZE] = {[0 ... ARRAY_SIZE - 1] = ARRAY_SIZE + 1}; 

     while(true) 
     { 
      // ARRAY_SIZE - k is number of available people, subtract searches for people left 
      // checked all possible mates 
      if(((ARRAY_SIZE - k) - searches) == 0) 
      { 
       singleFemales++; 
       break; 
      } 

      int randMale = rand() % ARRAY_SIZE; // find a random male 

      while(arrayContains(checkedMates, randMale)) // ensure that the male was not checked earlier 
      { 
       randMale = rand() % ARRAY_SIZE;    
      } 
      checkedMates[searches] = randMale; 

      // male has a greater income and is single    
      if((femArray[k][0] < maleArray[randMale][0]) && (maleArray[randMale][1] == SINGLE)) 
      { 
       femArray[k][1] = MARRIED; 
       maleArray[randMale][1] = MARRIED; 
       break; 
      } 
      else 
      { 
       searches++; 
       continue; 
      } 
     } 
    } 

    return ARRAY_SIZE - singleFemales; 
} 

bool arrayContains(int* array, int val) 
{ 
    for(int i = 0; i < ARRAY_SIZE; i++) 
    { 
     if (array[i] == val) 
      return true; 
    } 
    return false; 
} 

Answer 1

首先，存在的問題，對一些不確定性意味着什麼女人到「隨機約會」。至少有兩種可能的解釋：

1. 通過未婚女性您週期，每一個隨機繪製的未婚男性和一個決定，根據工資，是否結婚。在通過現有女性的每次通過時，這可能導致一些可用的男性由多個女性約會，而其他男性約會不會。

2. 你將每個試驗分成幾輪。在每一輪中，你都會對未婚女性隨機洗牌，這樣每個未婚男人就只能跟一位未婚女人約會。

在這兩種情況下，直到沒有更多的匹配可能的，當符合條件的男性中的最高薪水是小於或等於符合條件的婦女之間的最低工資發生，你必須重複匹配。

在我的測試中，這兩種解釋產生了稍微不同的統計數據：約69.5％使用解釋1結婚，約67.6％使用解釋2.每100個潛在夫婦的100次試驗足以在運行間產生相當低的差異。例如，在該術語的通用（非統計）意義上，一組10次運行的結果在67.13％和68.27％之間變化。

但是，您似乎沒有采取任何一種解釋。如果我正確地閱讀了你的代碼，你會完全通過一次，並且對於每一個你不斷繪製隨機男人，直到你找到一個那個女人可以結婚或者你已經測試了每個人。應該清楚的是，這會給名單上的女性早婚的機會更大，並且基於訂單的偏差至少會增加結果的差異。我認爲它也可能對更多婚姻產生淨偏見，但我沒有很好的論據支持。

此外，正如我在評論中寫的，你通過選擇隨機整數的方式引入了一些偏見。rand()函數在0和RAND_MAX之間返回int，包括的可能值。爲了論證，我們假設這些值均勻分佈在該範圍內。如果使用%運算符將結果範圍縮小爲N可能的值，那麼只有當N均勻分配RAND_MAX + 1時，該結果仍然是均勻分佈的，因爲否則更多rand()結果會映射到某些值，而不會映射到其他值。實際上，這適用於任何嚴格的數學轉換，您可能會想到縮小rand()結果的範圍。

對於薪水，我不明白爲什麼你甚至懶得把他們映射到一個有限的範圍內。 RAND_MAX與其他任何人一樣是最高的工資;從模擬中收集的統計數據不取決於工資的範圍;但只限於其均勻分佈。

但是，爲了在數組中選擇隨機索引，無論是繪製人還是洗牌，您都需要一個有限的範圍，所以您需要小心。減少在這種情況下偏差的最好方法是強制抽取的隨機數通過重新繪製的必要，以確保它儘可能多的時間來從衆多是均勻地通過選項的數整除：

/* 
* Returns a random `int` in the half-open interval [0, upper_bound). 
* upper_bound must be positive, and should not exceed RAND_MAX + 1. 
*/ 
int random_draw(int upper_bound) { 
    /* integer division truncates the remainder: */ 
    int rand_bound = (RAND_MAX/upper_bound) * upper_bound; 

    for (;;) { 
     int r = rand(); 

     if (r < rand_bound) { 
      return r % upper_bound; 
     } 
    } 
}