C 中的配对程序？

Question

给我的问题如下：

Write a program to discover the answer to this puzzle:"Let's say men and women are paid equally (from the same uniform distribution). If women date randomly and marry the first man with a higher salary, what fraction of the population will get married?"

From this site

我的问题是，我得到的已婚百分比数字似乎是错误的。另一位发帖者asked this same question on the programmers exchange before，结婚率应该是~68%。但是，我越来越接近 75%（方差很多）。如果哪位大侠能帮我看看哪里错了，不胜感激

我意识到，看看程序员交流中的另一个问题，这不是解决问题的最有效方法。但是，在使用更有效的方法之前，我想以这种方式解决问题。

我的代码在下面，大部分问题是 "solved" 在测试函数中：

#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

首先，关于女性 "date randomly" 意味着什么的问题存在一些歧义。至少有两种似是而非的解释：

你循环浏览未婚女性，每人随机抽取一名未婚男性，并根据薪水决定是否结婚。每次通过可用的女性时，这可能会导致一些可用的男性被多个女性约会，而其他人被 none.
您将每个试验分成几轮。在每一轮中，你在未婚女性中随机洗牌，这样每个未婚男性只和一个未婚女性约会。

在任何一种情况下，您都必须重复匹配，直到没有更多可能的匹配，当符合条件的男性中的最高工资小于或等于符合条件的女性中的最低工资时，就会出现这种情况。

在我的测试中，这两种解释产生了略有不同的统计数据：大约 69.5% 的人使用解释 1，而大约 67.6% 的人使用解释 2。对 100 对潜在夫妇进行 100 次试验，每对都足以在运行之间产生相当低的差异。例如，在该术语的一般（非统计）意义上，一组 10 次运行的结果在 67.13% 和 68.27% 之间变化。

但是，您似乎不接受这两种解释中的任何一种。如果我没看错你的代码，你会准确地一次检查这些女人，并且对于每个女人，你都会不断地随机抽取男人，直到你找到那个女人可以结婚的人或者你已经测试过每个人。应该清楚的是，这会为列表中靠前的女性带来更大的结婚机会，并且基于顺序的偏差至少会增加结果的方差。我发现它也对更多的婚姻产生净偏见是合理的，但我没有很好的论据来支持。

此外，正如我在评论中所写，您通过 select 随机整数的方式引入了一些偏差。 rand() 函数 returns 0 和 RAND_MAX 之间的 int，包括 RAND_MAX + 1 可能的值。为了争论起见，我们假设这些值在该范围内均匀分布。如果您使用 % 运算符将结果的范围缩小到 N 可能的值，那么只有在 N 平均除以 RAND_MAX + 1 时，该结果仍然是均匀分布的，否则rand() 个结果映射到某些值而不是映射到其他值。事实上，这适用于任何严格的数学变换，您可能会想到缩小 rand() 结果的范围。

对于工资，我不明白你为什么还要费心将它们映射到一个限制范围内。 RAND_MAX 与其他最高薪水一样好；从模拟中收集的统计数据不依赖于工资的范围；但仅限于它们的均匀分布。

然而，对于 select 将随机索引放入数组中，无论是绘制人还是洗牌，您都需要限制范围，因此您需要小心。在这种情况下，减少偏差的最佳方法是强制抽取的随机数来自可被选项数量整除的范围，方法是根据需要重新抽取多次确保它：

/*
 * 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;
        }
    }
}

C 中的配对程序？

Matchmaking program in C?

c

probability

cs50

matchmaking