0

我遇到的问题如下：

编写一个程序来找出这个谜题的答案：“假设男性和女性的报酬是平等的（来自相同的均匀分布）。如果女性随机约会并嫁给第一个薪水更高的男性，那么有多少人口会结婚？”

从这个网站

我的问题是，我得到的已婚百分比似乎是错误的。之前在程序员交流会上也有发帖人问过同样的问题，结婚的比例应该是~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;
}
4

1 回答 1

2

首先，对于女性“随机约会”意味着什么，这个问题存在一些模糊性。至少有两种合理的解释：

  1. 你循环遍历未婚女性，每人随机抽取一名未婚男性，并根据薪水决定是否结婚。在每次通过可用的女性时，这可能会导致一些可用的男性被多个女性约会，而另一些则没有约会。

  2. 您将每个试验分成几轮。在每一轮中，你随机将未婚男性从未婚女性中随机洗牌，使每个未婚男性与一位未婚女性约会。

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

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

但是，您似乎不接受其中任何一种解释。如果我正确地阅读了您的代码，您将只检查一次女性，并且对于每个女性，您都会随机抽取男性，直到您找到该女性可以结婚的男性，或者您已经测试了每个女性。应该清楚的是，这为列表中的早期女性提供了更大的结婚机会，并且基于顺序的偏见至少会增加结果的差异。我认为它也对更多的婚姻产生了净偏见，但我没有很好的论据支持。

此外，正如我在评论中所写，您通过选择随机整数的方式引入了一些偏差。该函数为可能的值rand()返回一个int介于0和RAND_MAX（含）之间。RAND_MAX + 1为了论证起见，让我们假设这些值均匀分布在该范围内。如果您使用%运算符将​​结果的范围缩小到可能的值，那么只有当均匀除以时，N该结果仍然是均匀分布的，否则更多的结果映射到某些值而不是映射到其他值。事实上，这适用于您可能想到的任何严格的数学变换，以缩小结果的范围。NRAND_MAX + 1rand()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;
        }
    }
}
于 2016-02-02T19:35:55.233 回答