下面的问题是我在这个 wiki page 上遇到的一个问题.

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?"

我的算法:

1. 用随机薪水值填充两个数组(女性和男性)。

2. 随机将一名女性与一名男性配对，然后比较薪水。如果是女的 工资低于男性，增加婚姻柜台。集双女 男性 isMarried 值为 true。

3. 继续约会过程，直到未婚男性的最高工资为 低于未婚女性的最低工资。

这是我的实现:

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);


    srand(time(NULL));


    int min = 1;
    int max = 1000000;
    Male male[100];
    Female female[100];
    double count = 0;
    bool done = false;





    //Fill array of Females and Males with random salaries ranging from 1 to 10
    for(int i=0; i<100; i++){
        int output = min + (rand() % (int)(max - min + 1));
        male[i].salary = output;
    }
    for(int i=0; i<100; i++){
        int output = min + (rand() % (int)(max - min + 1));
        female[i].salary = output;
    }


    //Start dating
    //Keep dating until the maximum salary of males is lower than minimum salary of females

    do{
        random_shuffle(begin(male), end(male));               //Shuffle array of males
        random_shuffle(begin(female), end(female));           //Shuffle array of females


        for(int i=0; i<100; i++){                              //Compare a female and male from both arrays
            if(female[i].salary < male[i].salary)
                if(!female[i].isMarried && !male[i].isMarried){
                    count++;
                    female[i].isMarried = true;
                    male[i].isMarried = true;
                    cout << "Female salary: " << female[i].salary << endl;
                    cout << "Male salary: " << male[i].salary << endl;
                }
        }

        int maxMen = 0;
        for(int i=0; i<100; i++){
            if(male[i].salary > maxMen && !male[i].isMarried)
                maxMen = male[i].salary;
        }

        int minWomen = 1000000;
        for(int i=0; i<100; i++){
            if(female[i].salary < minWomen && !female[i].isMarried)
                minWomen = female[i].salary;
        }

        if(maxMen <= minWomen)
            done = true;


    }while(!done);


    cout << "Percentage: " << count/100;
    cout << endl;

    int unmarried = 0;
    cout << "Number of unmarried females: ";
    for(int i=0; i<100; i++)
        if(!female[i].isMarried)
            unmarried++;
    cout << unmarried << endl;

    unmarried = 0;
    cout << "Number of unmarried males: ";
    for(int i=0; i<100; i++)
        if(!male[i].isMarried)
            unmarried++;
    cout << unmarried << endl;

    cout << endl;




    return a.exec();
}

我在 Programmers.SE 上问过这个问题，显然，I should be getting 68% . 我得到的百分比值在 35% 到 40% 之间。我做错了什么？

最佳答案

1) 您的条件变量已初始化:

bool done=false;  

这可能会导致比计划更早退出循环，因为它仅在 maxMen < minWomen 时设置为可预测的值。 .

2) 您的结束条件设置不正确:

你只在maxMen < minWomen时完成了.但是如果 maxMen == minWomen没有女人会再结婚，所以你会有一个无限循环。如果你的工资规模很小，这种现象很可能发生。如果你从 1 到 1000，这种情况不太可能发生。但为了避免不可能的情况，将子句更改为:

    if (maxMen <= minWomen)   // no new wedding in sight
        done = true;

结合前面的问题，你的循环条件是错误的。你应该循环，只要它没有完成(如果 maxMen > minWomen，仍然有婚礼的可能)。所以改写为:

...
} while (! done);

结论

通过这 3 个更改，当我多次重新运行程序时，我得到的百分比从 55% 到 74%，大多数值在 65% 到 70% 之间。

其他建议

您应该避免硬编码数字。而不是 10 , 但更喜欢 max+1 .在开头定义const int N=100;并替换所有文字 100与 N .通过这种方式，可以更轻松地使用模拟参数(使用不同的薪水范围或更大的人口)。

您可以将模拟放在一个单独的函数中，将百分比作为值返回，然后在 main() 中多次运行模拟(100 次、1000 次？)，计算百分比的平均值和标准差。这比手动运行和粗略估计提供更准确的结果。

如果您对模拟感兴趣，可能值得看看 <random> :它提供了大量的随机生成器和随机分布选择，比 rand() 强大得多。示例:

    mt19937 generator(time(NULL));  // mersene twister generator seeded with time 
    ...
    uniform_int_distribution<int> distribution(min, max);  // after declaration of your min and max
    ...
    male[i].salary = distribution(generator);   // and same for female 

顺便说一下，您可能对 std::count_if 感兴趣, std::min() 和 std::max()这可以轻松地为您节省 for 循环的重复编码。

关于c++ - 已婚人口的比例是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25477141/