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

そもそも、女性が「ランダムにデートする」とはどういうことかという問題には、あいまいな点があります。もっともらしい解釈が少なくとも 2 つあります。

  1. あなたは未婚の女性を巡回し、それぞれが未婚の男性の 1 人を無作為に選び、給料に基づいて結婚するかどうかを決定します。利用可能な女性を通過するたびに、これはおそらく、利用可能な男性の一部が複数の女性とデートし、他の男性が誰ともデートしないという結果になります.

  2. 各トライアルをラウンドに分割します。各ラウンドで、未婚の女性の中から未婚の男性をランダムにシャッフルし、各未婚の男性がちょうど 1 人の未婚の女性とデートするようにします。

いずれの場合も、一致する可能性がなくなるまでマッチングを繰り返す必要があります。これは、適格な男性の最高給与が適格な女性の最低給与以下になる場合に発生します。

私のテストでは、2 つの解釈はわずかに異なる統計を生成しました: 解釈 1 を使用して約 69.5% が結婚し、解釈 2 を使用して約 67.6% が結婚しました。それぞれ 100 組の潜在的なカップルの 100 回の試行は、実行間の分散をかなり低くするのに十分でした。この用語の一般的な (非統計的な) 意味では、たとえば、10 回の実行の 1 つのセットからの結果は、67.13% から 68.27% の間で変化しました。

しかし、あなたはそれらの解釈のいずれもとっていないようです。私があなたのコードを正しく読んでいれば、あなたは女性を一度だけ調べ、その女性が結婚できる人を見つけるか、すべての人をテストするまで、ランダムな男性を描き続けます. これにより、リストの早い段階で女性が結婚する可能性が高くなり、順序に基づくバイアスが少なくとも結果の分散を増加させることは明らかです. それがより多くの結婚に正味の偏りを及ぼすことももっともらしいと思いますが、それを支持する良い議論はありません.

さらに、コメントで書いたように、ランダムな整数を選択する方法によってバイアスが発生します。このrand()関数は、可能な値としてとのint間(両端を含む) を返します。議論のために、これらの値がその範囲に均一に分布していると仮定しましょう。演算子を使用して結果の範囲を可能な値に縮小する場合、その結果は均等に分割される場合にのみ均一に分散されます。そうしないと、他の値にマップするよりも多くの結果が一部の値にマップされるためです。実際、これは、結果の範囲を狭めるために考えられる厳密な数学的変換に適用されます。0RAND_MAXRAND_MAX + 1%NNRAND_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 に答える