有关于一个查找问题（相亲问题）的思考!

前天晚上在寝室和室友卧聊的时候，他提出了这样一个问题：
假如假期之中父母给你安排了100个相亲的对象，你只能跟每个对象约会一次，约会的时候你可以选择表白也可以选择不表白，一旦表白了女方就会答应你的请求，然后相亲活动停止；假如没有表白对于这个对象来说你就没有机会了！在这样的条件下你用什么样的策略才能保证你能够以最大的概率找到你认为更好的女生捏？
乍一看貌似问题不是很难，但是仔细分析起来才发现不是很简单所以现在拿到这个地方跟大家讨论一下，还希望看看众位算法大牛的解释！
首先分析问题：你在跟每个相亲对象约会之前是不知道她的好坏的（当然这里仅限于第一印象的好坏，有点肤浅，:-)）但是每个人你只有一次约会的机会，你在见完所有对象之前你永远不知道后面的相亲对象的情况，一旦决定表白了你就没有机会再见后面的相亲对象了，听起来真是十分的残酷呀！！可能有些人会选择我先把前面的99个都约会一遍，然后不管第一百个怎么样约会的时候直接表白，至少这样把每个人都看了一遍，死也死的没有遗憾了，呵呵开个玩笑。如果你是聪明人肯定不会选择这个策略的！
盯着相亲这个问题来说事，显然大家心思就跑偏了，要解决这个问题我们首先要对他进行建模，这100个相亲对象我们虽然没有见过她们，但是想必她们肯定是有个好坏之分的，所以我们可以把她们抽象成一个具有100个不同大小的元素的整型的数组a[100]。
现在有这样的一种策略，就是我可以先约会前n个对象，只约会不表白，回来之后我给这n个对象打个分，算一个平均值出来，然后在约会剩下的100-n个对象，当我碰到比这个平均值大的对象的时候我就向她表白！貌似这样的策略想来比起瞎找来要强许多，但是现在有个问题就出现了我们如何来确定这个n的大小捏？对的，我们可以写个程序琼举一下。那么怎么来设计这个程序捏，我想出了以下的一个方案：
首先我定义一个整型的数组ivec[100]，用来存储着100个不同分值（分值的大小是从1-100之间随机出来的）的姑娘，然后循环求解n（1-100）的均值，并将在每个n值的情况下选出来的数值记录在另外一个数组cvec[100]之中，然后循环上述过程10000次，将每次对应与每个cvec[]元素的对象值，做和最后求平均值，输出，看一看到底n取多少的时候输出的平均值是最大的，这样就说明了n的最佳取值：

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int average(vector<int> &a, int b)
{
    int sum = 0;
    for(int i= 0; i < b; i++)
    {
        sum += a[i];
    }
    return sum / b;
}
int main()
{
    vector<int> ivec;
    vector<int> cvec;
    int aver = 0;
    int k = 1;
    int j = 0;
    for(int s = 1; s <= 100; s++)
    {
        ivec.push_back(s);
        cvec.push_back(0);
    }
    while(k <= 10000)
    {
        srand(time(0));
        random_shuffle(ivec.begin(), ivec.end());//将数组中的元素随机排列！
        for(int i = 0; i < 100; i++)
        {
            aver = average(ivec,i+1);            //取前n个对象的平均值
            for(j = i+1; j < 100; j++)
            {
                if(ivec[j] > aver)
                {
                    cvec[i] = cvec[i] + ivec[j]; //记录选择出来的数值
                    break;
                }
            }
            if(j == 100)
            {
                cvec[i] += ivec[j-1];
            }
        }
        k++;
    }
    for(int h = 0; h < 100; h++)
    {
        cout << "the sample is " << h+1 << " the counter is: " << cvec[h]/10000 << endl;
    }
    return 0;
}

执行结果：

the sample is 1 the counter is: 72.7971
the sample is 2 the counter is: 73.2202
the sample is 3 the counter is: 71.4259
the sample is 4 the counter is: 75.0164
the sample is 5 the counter is: 74.4297
the sample is 6 the counter is: 76.3934
the sample is 7 the counter is: 77.2789
the sample is 8 the counter is: 77.635
the sample is 9 the counter is: 76.9348
the sample is 10 the counter is: 74.5057
the sample is 11 the counter is: 73.8079
the sample is 12 the counter is: 72.5249
the sample is 13 the counter is: 75.5074
the sample is 14 the counter is: 75.125
the sample is 15 the counter is: 74.9676
the sample is 16 the counter is: 75.6766
the sample is 17 the counter is: 75.4921
the sample is 18 the counter is: 76.3521
the sample is 19 the counter is: 76.2931
the sample is 20 the counter is: 75.9187
the sample is 21 the counter is: 75.2278
the sample is 22 the counter is: 74.449
the sample is 23 the counter is: 73.0363
the sample is 24 the counter is: 68.9686
the sample is 25 the counter is: 69.9028
the sample is 26 the counter is: 72.6237
the sample is 27 the counter is: 69.613
the sample is 28 the counter is: 71.4186
the sample is 29 the counter is: 75.8713
the sample is 30 the counter is: 74.4902
the sample is 31 the counter is: 72.3863
the sample is 32 the counter is: 77.3795
the sample is 33 the counter is: 76.5902
the sample is 34 the counter is: 77.7821
the sample is 35 the counter is: 76.514
the sample is 36 the counter is: 76.5334
the sample is 37 the counter is: 76.2138
the sample is 38 the counter is: 76.2427
the sample is 39 the counter is: 75.2769
the sample is 40 the counter is: 74.5672
the sample is 41 the counter is: 74.2544
the sample is 42 the counter is: 71.6644
the sample is 43 the counter is: 76.5912
the sample is 44 the counter is: 72.7051
the sample is 45 the counter is: 68.3414
the sample is 46 the counter is: 70.0941
the sample is 47 the counter is: 75.0341
the sample is 48 the counter is: 73.8389
the sample is 49 the counter is: 71.382
the sample is 50 the counter is: 76.3986
the sample is 51 the counter is: 75.0583
the sample is 52 the counter is: 71.8271
the sample is 53 the counter is: 75.9133
the sample is 54 the counter is: 76.451
the sample is 55 the counter is: 76.2901
the sample is 56 the counter is: 75.7828
the sample is 57 the counter is: 74.8741
the sample is 58 the counter is: 71.758
the sample is 59 the counter is: 76.1354
the sample is 60 the counter is: 76.4661
the sample is 61 the counter is: 75.2136
the sample is 62 the counter is: 71.2485
the sample is 63 the counter is: 75.5339
the sample is 64 the counter is: 74.6645
the sample is 65 the counter is: 73.3281
the sample is 66 the counter is: 69.7064
the sample is 67 the counter is: 70.2078
the sample is 68 the counter is: 73.6396
the sample is 69 the counter is: 70
the sample is 70 the counter is: 76.1401
the sample is 71 the counter is: 74.1022
the sample is 72 the counter is: 71.3195
the sample is 73 the counter is: 75.7528
the sample is 74 the counter is: 75.3652
the sample is 75 the counter is: 72.6577
the sample is 76 the counter is: 69.6235
the sample is 77 the counter is: 72.8564
the sample is 78 the counter is: 76.9797
the sample is 79 the counter is: 76.4209
the sample is 80 the counter is: 77.6325
the sample is 81 the counter is: 75.9835
the sample is 82 the counter is: 77.0154
the sample is 83 the counter is: 77.4839
the sample is 84 the counter is: 77.3489
the sample is 85 the counter is: 76.4629
the sample is 86 the counter is: 76.721
the sample is 87 the counter is: 77.3822
the sample is 88 the counter is: 78.3564
the sample is 89 the counter is: 76.8349
the sample is 90 the counter is: 77.8339
the sample is 91 the counter is: 78.068
the sample is 92 the counter is: 80.2495
the sample is 93 the counter is: 81.4593
the sample is 94 the counter is: 86.1396
the sample is 95 the counter is: 96
the sample is 96 the counter is: 73.3176
the sample is 97 the counter is: 70.47
the sample is 98 the counter is: 63.4537
the sample is 99 the counter is: 51.3161
the sample is 100 the counter is: 51.3161

实际上这个问题会有一个最佳的n值的:100/e，但是我现在用这个写的算法模拟出来之后的结果，却显得很随机，想了很久比较困惑！至于这个1/e之一的推导是这样来的，其实当我们只对样本中最好的女生感兴趣，其他都不关注的的时候：

我们可以其实可以换一个标准就是我们取k个人只跟她们约会，不表白然后找出这k个人中最大值imax，然后相同的策略遍历后面的n-k个人：

对于某个固定的 k，如果最适合的人出现在了第 i 个位置（k < i ≤ n），要想让他有幸正好被 MM 选中，就必须得满足前 i-1 个人中的最好的人在前 k 个人里，这有 k/(i-1) 的可能。考虑所有可能的 i，我们便得到了试探前 k 个男生之后能选中最佳男生的总概率 P(k)：

用 x 来表示 k/n 的值，并且假设 n 充分大，则上述公式可以写成：

对 -x · ln x 求导，并令这个导数为 0，可以解出 x 的最优值，它就是欧拉研究的神秘常数的倒数—— 1/e
我们按照最大值来设计我们的模拟过程：

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int max(vector<int> &a, int b)
{
    int imax = 0;
    for(int i= 0; i < b; i++)
    {
        if(a[i] > imax)
        {
            imax = a[i];
        }
    }
    return imax;
}
int main()
{
    vector<int> ivec;
    vector<double> cvec;
    int imax = 0;
    int k = 1;
    int j = 0;
    for(int s = 1; s <= 100; s++)
    {
        ivec.push_back(s);
        cvec.push_back(0.0);
    }
    while(k <= 10000)
    {
        srand(time(0));
        random_shuffle(ivec.begin(), ivec.end());
        for(int i = 0; i < 100; i++)
        {
            imax = max(ivec,i+1);
            for(j = i+1; j < 100; j++)
            {
                if(ivec[j] > imax)
                {
                    if(ivec[j] == 100)
                    {
                        cvec[i]++;
                    }
                    break;
                }
            }
        }
        k++;
    }
    for(int h = 0; h < 100; h++)
    {
        cout << "the sample is " << h+1 << " the counter is: " << cvec[h] << endl;
    }
    return 0;
}

得到一下的执行结果：

the sample is 1 the counter is: 408
the sample is 2 the counter is: 612
the sample is 3 the counter is: 816
the sample is 4 the counter is: 1123
the sample is 5 the counter is: 1327
the sample is 6 the counter is: 1429
the sample is 7 the counter is: 1531
the sample is 8 the counter is: 1735
the sample is 9 the counter is: 1939
the sample is 10 the counter is: 2041
the sample is 11 the counter is: 2143
the sample is 12 the counter is: 2143
the sample is 13 the counter is: 2143
the sample is 14 the counter is: 2245
the sample is 15 the counter is: 2245
the sample is 16 the counter is: 2245
the sample is 17 the counter is: 2448
the sample is 18 the counter is: 2652
the sample is 19 the counter is: 2959
the sample is 20 the counter is: 3061
the sample is 21 the counter is: 3163
the sample is 22 the counter is: 3163
the sample is 23 the counter is: 3265
the sample is 24 the counter is: 3265
the sample is 25 the counter is: 3367
the sample is 26 the counter is: 3571
the sample is 27 the counter is: 3571
the sample is 28 the counter is: 3571
the sample is 29 the counter is: 3571
the sample is 30 the counter is: 3571
the sample is 31 the counter is: 3570
the sample is 32 the counter is: 3672
the sample is 33 the counter is: 3672
the sample is 34 the counter is: 3672
the sample is 35 the counter is: 3774
the sample is 36 the counter is: 3672
the sample is 37 the counter is: 3570
the sample is 38 the counter is: 3672
the sample is 39 the counter is: 3774
the sample is 40 the counter is: 3876
the sample is 41 the counter is: 3876
the sample is 42 the counter is: 3876
the sample is 43 the counter is: 3876
the sample is 44 the counter is: 3877
the sample is 45 the counter is: 3877
the sample is 46 the counter is: 3877
the sample is 47 the counter is: 3877
the sample is 48 the counter is: 3877
the sample is 49 the counter is: 3775
the sample is 50 the counter is: 3775
the sample is 51 the counter is: 3673
the sample is 52 the counter is: 3571
the sample is 53 the counter is: 3571
the sample is 54 the counter is: 3469
the sample is 55 the counter is: 3367
the sample is 56 the counter is: 3264
the sample is 57 the counter is: 3264
the sample is 58 the counter is: 3264
the sample is 59 the counter is: 3162
the sample is 60 the counter is: 3162
the sample is 61 the counter is: 3162
the sample is 62 the counter is: 3060
the sample is 63 the counter is: 2958
the sample is 64 the counter is: 2856
the sample is 65 the counter is: 2856
the sample is 66 the counter is: 2754
the sample is 67 the counter is: 2754
the sample is 68 the counter is: 2652
the sample is 69 the counter is: 2550
the sample is 70 the counter is: 2550
the sample is 71 the counter is: 2550
the sample is 72 the counter is: 2448
the sample is 73 the counter is: 2346
the sample is 74 the counter is: 2244
the sample is 75 the counter is: 2142
the sample is 76 the counter is: 2040
the sample is 77 the counter is: 1938
the sample is 78 the counter is: 1938
the sample is 79 the counter is: 1836
the sample is 80 the counter is: 1734
the sample is 81 the counter is: 1632
the sample is 82 the counter is: 1633
the sample is 83 the counter is: 1531
the sample is 84 the counter is: 1429
the sample is 85 the counter is: 1327
the sample is 86 the counter is: 1225
the sample is 87 the counter is: 1123
the sample is 88 the counter is: 1021
the sample is 89 the counter is: 919
the sample is 90 the counter is: 816
the sample is 91 the counter is: 714
the sample is 92 the counter is: 714
the sample is 93 the counter is: 612
the sample is 94 the counter is: 510
the sample is 95 the counter is: 408
the sample is 96 the counter is: 306
the sample is 97 the counter is: 204
the sample is 98 the counter is: 102
the sample is 99 the counter is: 102
the sample is 100 the counter is: 0

可以看到，这次的输出是由规律的，当k = 40左右的时候选到最优秀的女生的概率是最大的，到底问题处在了什么地方了。仔细分析一下：我们采取第一种策略，取前k个人的均值，然后求解在这种策略下的找到对象的均值是均匀分布的，为什么捏？因为对于这件事情本身来看他是一个均匀的分布的事件，我们求均值的策略并没有改变其随机的特性，所以无论我们用多少个样本模拟，当然除了k=100的情况外结果应该是满足均匀分布的特性！因而可以得出这样的结论，当你只求找到平均水平靠上的女生时，无论你采取多大的k值，对于结果影响不会太大，但是除去100跟99，这两种情况，因为这样做是没有意义的！
然而我们第二种策略求解的是找到最佳女生的概率，是跟你k值的选取有密切关系的，而且满足37%的法则！即当你在1/e比例处选取样本，表现最好!当然这跟你n的取值不同会有波动！因为1/e是我们推导出来的一个极限值！