最大概率选择到“最好女孩”的算法

假设你是一位男孩,而上天在你20-30岁间安排了20位适合你的女孩。这些女孩都愿意作为你的伴侣,但你只能选择他们其中一个。选择的条件如下:

  1. 对于你来说,这20位女孩是可以排序的,也就是说事后你可以对她们的质量进行排名,排名第一的女孩对你来说就是最好的,排名第二十的对你来说就是最差的。
  2. 这20位女孩不是同时出现在你的生命中,而是按照时间顺序先后出现,每出现一个你都要决定留下还是拒绝。如果留下她,她就会成为你的终身伴侣,你将没有权利选择后面的女孩;如果你拒绝,你还可以选择后面的女孩,但是对前面已经拒绝的女孩就没有机会从头再来。

假设上天是完全随机安排各个时间段出现的女孩,即出现的时间先后和女孩的质量完全没有关系。那么,你应该在什么时候决定接受一位女孩,并使得被接受的那位女孩属于最好女孩的可能性最大呢?

该问题已被保护

保护原因:避免来自新用户不合宜或无意义的致谢、跟帖答案。

评论 (17)链接2012-01-13 
  • 0 支持
    其实我不懂程序,所以就把我的想法直接写成文字了
    这个问题其实很经典,也有个很简单的解决方案,就是 首先不选则第一位,然后如果下一位比第一位好,就选择她。
    根据这个答案得到的公式大概就是这样
    输入第一位,记录第一位数值
    输入第二位,比较两位
    if比第一位好,结婚
    else继续选择下一位
    按照这个公式与最好的姑娘结婚的概率最大。
    – BearTher 2012-11-13
  • 0 支持
    @BearTher 那到第20个都else了而且第一个没了怎么办…… – sksandking 2012-11-16
  • 0 支持
    其实这是概率里很经典的例子之一——Secretary problem,也有叫37%法则,有很多研究了,有兴趣还可以看看Monty hall problem和Petersburg paradox。账号不能给答案,只能这么简单说了…… – queeniexxy 2012-12-05
  • 0 支持
    想看看回答是怎么的 – 满俊松 2013-03-06
显示更多隐藏的评论

很有意思的问题,我首先下意识的想到是先看一看,比一比,不求最好,后来在网上看到这样的策略算出来的概率还是挺高的,先转载一下网上完整的答案:

策略1:事先抽签,抽到第几个就第几个。比如,抽到第10位,那么第10个在你生命中出现的女孩就事前被确定为你的伴侣。而她刚好是最好的女孩之概率是多少呢?答案是1/20=0.05。这种策略使你有5%的可能性获得最好的女孩。这样的概率显然太小,很难发生。

策略2:把全部女孩分成前后两段,最先出现的10位均不接受,但了解了这10位女孩的质量,然后在后来出现的10位女孩当中,第一次碰到比以前都可爱的女孩子,就立马接受。这是一种等一等、看一看的策略。这样的策略中,你得到最好的女孩子的概率是(10/20)*(10/19)=0.263。这个概率已经不算太小。

补充说明一下策略2中概率的算法:这样的规则下,确保得到最好的女孩子必然要求最好的女孩子在后10名女孩子中出现——否则你怎么也得不到最好的了 ——其概率是(10/20),同时,还要求第二好的女孩子出现在前10名,其概率为(10/19)——为什么是(10/19)?因为除了最好的,剩下人数 19个,第二好的女孩出现在前10名的概率就是(10/19)——这样就确保了你会得到最好的女孩子。

但是,策略2得到最好女孩子的概率真的是0.263吗?可能不是,因为这只是第二好的女孩刚好在前10个出现的情况;实际上,即使第二好女孩子没有出现在先前的10个,但只要在最好的女孩出现之前的所有女孩中质量最高的出现在前10个,那么策略2也可确保得到最好的女孩子(这一点要想通,否则就难以明白接下来的内容)。也就是说,策略2获得最好的女孩子的概率实际上是超过0.263的(实际上我们在后面会发现这个概率应是0.3594。哇!这的确已经是一个不小的概率了)。

但是,还有更好的方法吗?或者我们可以问,放弃先出现的10个女孩是否是最优的?如果不是,那么应该放弃几个先出现的女孩子呢?

事实上,我们确有更好的策略(你应该先把前面的内容看懂,如果前面没看懂,下面可能就更看不懂了)。既然20个质量不同的女孩子其质量在你生命里是随机出现的,没有任何规律,那么,第k个女孩刚好是最好女孩的概率是1/20,而刚好把这个最好的女孩子选择到的概率是多少?对此的考虑应该是:既然给定了第k个女孩子质量最好,而我们决定放弃前面n-1个女孩子,从第n个开始执行策略2的规则,那么必须要求在k之前的女孩子中质量排名最高的那个必须出现前 n-1个女孩子中,这样才能确保k被选中,其概率就是(n-1)/(k-1)。从而第k个女孩子刚好是最好的女孩子而且又一定被选中的概率就是(1 /20)[(n-1)/(k-1)]。这里,k的取值范围显然应该是[n,20]中的整数。所以,放弃n-1个女孩子而一定会得到最可爱的那个女孩子的概率实际上就是(1/20)[(n-1)/(n-1)]+ (1/20)[(n-1)/(n)]+ (1/20)[(n-1)/(n+1)]+…+(1/20)[(n-1)/(20-1)]。这个概率可以用Mathematica软件来计算,或者用 Excel来计算也可以,读者会发现,当n=8时,该概率有最大值0.3842。也就是说,如果我们放弃前7个女孩子,先看一看,心里有个谱,然后只要看到比前7个女孩子中最好的女孩还要好的女孩子,那么我们就立即选择接受。而这个被接受的女孩子刚好属于最好女孩的概率是0.3842。这比我们放弃10 个女孩(n*=11)的策略2要好,按照策略2根据上述公式计算得到获得最好女孩的概率为0.3594。

我们用Mathematica软件绘出获得最好女孩子的概率图形(纵轴是概率,横轴表示从第几个开始认真考虑接受。最大概率出现在n*=8,即放弃前7个,从第8个开始认真考虑接受)。
请输入图片描述

根据这样的结果,我们可以这样结论:如果一个人确定结婚对象在20-30岁之间,而这20个女孩子以每年两个的平均分布出现,那么你应当在24岁才开始认真考虑终身大事。

这个例子也可任意改动数据后用同样的方法求解。比如,如果是30个女孩子,那么你应该从第11个女孩子开始认真考虑终身大事。

这个例子也可以改成其他的版本,比如:在20层楼中,每层楼都放着一颗宝石,每颗宝石的大小不一。现在你从第一楼开始上楼,每到一层楼你都可决定要不要该层楼中的宝石。如果不要,不能回头。如果要,则以后不能再取。问:你应该如何才可以有最大的机会获得最大那颗宝石?这个问题,据说是微软公司的面试题。但它的道理,与最大可能获得女孩子的道理是一样的。

转自:http://hi.baidu.com/%B0s%C5z/blog/item/10f85a01218711673912bbe2.html

可以证明, 当采用这种策略是, 应当放弃前n/e个女生, 这样选到最优的概率是最大的. 其中n是总数, e是自然对数的底. 证明方法来自果壳网: http://www.guokr.com/article/6768/

雷宸_焱
雷宸_焱
63
编辑于 2012-08-24
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (4)链接 • 2012-01-13
  • 0 支持
    犀利哦~~~~ – wyg1990 2012-08-25
  • 0 支持
    牛人,学习了。不过有个问题很是奇怪,你用算法,理论,公式算出来的结果,其实一个不懂编程的人都明白,现实生活中大家早已这么做了,但从来没想过这也能计算。我觉得不是所有问题都可以就算的,就好比设计这么一道算法取解决你的婚姻问题估计算法再严密,你都会觉得不靠谱吧 – 索隆 2012-08-29
  • 0 支持
    编程实验结果,10000000次实验,基本吻合:
    放弃前0 个女孩: 0.0500204
    放弃前1 个女孩: 0.1858382
    放弃前2 个女孩: 0.262082
    放弃前3 个女孩: 0.3131794
    放弃前4 个女孩: 0.3467431
    放弃前5 个女孩: 0.3682456
    放弃前6 个女孩: 0.3806641
    放弃前7 个女孩: 0.3844664
    放弃前8 个女孩: 0.3819299
    放弃前9 个女孩: 0.3733048
    放弃前10 个女孩: 0.359212
    放弃前11 个女孩: 0.3402164
    放弃前12 个女孩: 0.3165595
    放弃前13 个女孩: 0.2888349
    放弃前14 个女孩: 0.2571635
    放弃前15 个女孩: 0.2219201
    放弃前16 个女孩: 0.1834275
    放弃前17 个女孩: 0.14186
    放弃前18 个女孩: 0.0974367
    放弃前19 个女孩: 0.0500245
    – 58823136 2013-02-04
  • 0 支持
    @58823136 – aio- 2013-03-16

我写了一个程序来计算从哪个开始认真考虑能得到最优解的概率最大。
(名词解释:从第几个开始认真考虑,认真考虑的意思是,之前只是做参考,从这个开始,碰到比之前参考的好的,就选择,否则就不选)

得到的结果是
从第 06 个开始认真考虑得到 最好 的概率是 0.261450 最大
从第 07 个开始认真考虑得到 最好 的概率是 0.260500 第二
从第 05 个开始认真考虑得到 最好 的概率是 0.255020 第三

从第 20 个开始认真考虑得到 最差 的概率是 0.049680 最差

所以结论是 从第6个开始认真考虑。那样有最大的可能得到最好的选择
千万不要 从第20个才开始认真考虑。那样有最大的可能得到最差的选择

具体的代码与原始输出文件请看下面

  
#include "stdafx.h"
#include "memory.h"
#include "stdlib.h"
#include "time.h"

int _tmain(int argc, _TCHAR* argv[])
{
//enum
//{
int GirlNum = 20;
int CalcNum = 10000;
int OutNum = 5;
//int GirlPointBegin = 100;
//int GirlPointOffset = 20;
//;
for (int i = 1; i < argc; ++i)
{
if (i == 1) GirlNum = ::_ttoi(argv[i]);
if (i == 2) CalcNum = ::_ttoi(argv[i]);
if (i == 3) OutNum = ::_ttoi(argv[i]);
//if (i == 4) GirlPointOffset = ::_ttoi(argv[i]);
}
printf("=========================================\r\n");
printf("%d 个选择; 每次循环 %d次; 输出前后各 %d 个得到最优选择和得到最差选择的概率\r\n",GirlNum, CalcNum, OutNum);
printf("=========================================\r\n");
srand(time(NULL));
//int pointList[GirlNum][GirlNum];
int* pointList = new int[GirlNum * GirlNum];
::memset(pointList, 0, GirlNum * GirlNum * sizeof(int));
for (int i = 1; i < GirlNum; ++i)//从第几个开始认真考虑,认真考虑的意思是,之前只是做参考,从这个开始,碰到比之前参考的好的,就选择,否则就不选
//明显不能从第0个开始认真考虑,因为之前没有参考。
{
for (int j = 0; j < CalcNum; ++j)
{
int theBestGirl = -1;//参考阶段最好的女孩
int marryGirl = -1;
for (int w = 0; w < GirlNum; ++w)
{
int agirl = rand() % GirlNum;//随机出现一个女孩
if (w < i)//还在参考阶段
{
if (agirl> theBestGirl)
{
theBestGirl = agirl;
}
}
else//认真考虑阶段
{
if (agirl > theBestGirl)//有更好的就行了,别的考虑了
{
marryGirl = agirl;
break;
}
if (w == (GirlNum - 1))//如果已经是最后一个了,没有找到比参考的好的,则只能选最后一个了
{
marryGirl = agirl;
break;
}
}
}
if (marryGirl != -1)
{
//pointList[i][marryGirl] += 1;//从第i次开始考虑,在CalcNum次循环中的一次。选中了一位。这一位的计数加1
*(pointList + i * GirlNum + marryGirl) += 1;
}
else
{
printf("error");
}
}
}
printf("每次经过%d次随机测试\r\n", CalcNum);
printf("得到最差的次数,第二差的次数,第三差的次数。。。。最好的次数分别是\r\n");
for (int i = 1; i < GirlNum; ++i)
{
printf("从第 %02d 个开始认真考虑\r\n", i + 1);
int total = 0;
for (int j = 0; j < GirlNum; ++j)
{
total += *(pointList + i * GirlNum + j);//pointList[i][j];
printf("%05d ", *(pointList + i * GirlNum + j));//pointList[i][j]);
}
printf("total %d \r\n", total);
}

printf("计算得最优前 %d 个的概率\r\n", OutNum);
//int getBestNum = *(pointList + i * GirlNum + GirlNum - 1);//pointList[i][GirlNum - 1];
//float rate = getBestNum * 1.0f;
//rate = rate / CalcNum;
//printf("从第 %02d 个开始认真考虑得到最好的概率是 %05f\r\n", i + 1, rate);
for (int j = 0; j < OutNum; ++j)
{
for (int i = 1; i < GirlNum; ++i)
{
printf("从第 %02d 个开始认真考虑得到 ", i + 1);
if (j == 0)
{
printf("最");
}
else
{
for (int m = 0; m < j; ++m)
printf("次");
}
int num = *(pointList + i * GirlNum + GirlNum - 1 - j);
float rate = num * 1.0f;
rate = rate / CalcNum;
printf("好 的概率是 %05f\r\n", rate);
}
}
printf("计算得最差前 %d 个的概率\r\n", OutNum);
//int getBestNum = *(pointList + i * GirlNum + GirlNum - 1);//pointList[i][GirlNum - 1];
//float rate = getBestNum * 1.0f;
//rate = rate / CalcNum;
//printf("从第 %02d 个开始认真考虑得到最好的概率是 %05f\r\n", i + 1, rate);
for (int j = 0; j < OutNum; ++j)
{
for (int i = 1; i < GirlNum; ++i)
{
printf("从第 %02d 个开始认真考虑得到 ", i + 1);
if (j == 0)
{
printf("最");
}
else
{
for (int m = 0; m < j; ++m)
printf("次");
}
int num = *(pointList + i * GirlNum + j);
float rate = num * 1.0f;
rate = rate / CalcNum;
printf("差 的概率是 %05f\r\n", rate);
}
}
//::_sleep(100000);

return 0;
}

得到的输出是

  
    =========================================
20 个选择; 每次循环 100000次; 输出前后各 3 个得到最优选择和得到最差选择的概率
=========================================
每次经过100000次随机测试
得到最差的次数,第二差的次数,第三差的次数。。。。最好的次数分别是
从第 02 个开始认真考虑
00398 00717 00938 01248 01596 01901 02225 02732 03086 03438 03919 04550 05145 05799 06826 07736 08933 10366 12825 15622 total 100000
从第 03 个开始认真考虑
00777 00813 00832 00925 01058 01179 01392 01609 01954 02340 02736 03400 04100 04942 06107 07543 09369 12175 15741 21008 total 100000
从第 04 个开始认真考虑
01147 01162 01195 01120 01262 01260 01309 01454 01731 01977 02207 02611 03158 04134 05251 06831 08908 12283 16918 24082 total 100000
从第 05 个开始认真考虑
01551 01488 01548 01493 01486 01552 01560 01639 01740 01862 02058 02398 02820 03498 04635 06158 08301 11861 16850 25502 total 100000
从第 06 个开始认真考虑
01872 01771 01884 01837 01887 01828 01936 01935 01907 01933 02172 02335 02675 03107 04024 05457 07673 11093 16529 26145 total 100000
从第 07 个开始认真考虑
02175 02123 02181 02185 02117 02183 02108 02105 02199 02283 02259 02427 02652 03143 03707 05077 06938 10048 16040 26050 total 100000
从第 08 个开始认真考虑
02429 02361 02347 02459 02465 02574 02379 02371 02466 02441 02502 02603 02751 03069 03616 04610 06352 09672 15037 25496 total 100000
从第 09 个开始认真考虑
02672 02711 02714 02684 02743 02684 02724 02745 02705 02781 02757 02817 02946 03102 03573 04325 05964 08794 14249 24310 total 100000
从第 10 个开始认真考虑
02930 03209 02998 03034 03011 03025 02988 02945 02997 02964 03001 03033 03106 03260 03558 04209 05498 08174 13248 22812 total 100000
从第 11 个开始认真考虑
03216 03321 03259 03209 03251 03180 03193 03263 03225 03215 03302 03289 03267 03352 03681 04161 05299 07520 12365 21432 total 100000
从第 12 个开始认真考虑
03523 03469 03533 03524 03538 03445 03502 03453 03464 03452 03560 03480 03445 03582 03668 04252 05002 07107 11154 19847 total 100000
从第 13 个开始认真考虑
03737 03703 03747 03681 03740 03793 03757 03725 03696 03593 03637 03785 03630 03743 03873 04138 04958 06655 10330 18079 total 100000
从第 14 个开始认真考虑
03954 03962 03894 03944 03929 04032 03899 03918 03888 03909 03926 03947 03977 04037 04103 04176 04944 06087 09294 16180 total 100000
从第 15 个开始认真考虑
04133 04173 04137 04195 04211 04080 03998 04154 04141 04101 04136 04227 04087 04109 04206 04390 04778 05856 08459 14429 total 100000
从第 16 个开始认真考虑
04350 04410 04366 04291 04378 04448 04286 04244 04459 04204 04333 04306 04424 04340 04331 04298 04760 05608 07849 12315 total 100000
从第 17 个开始认真考虑
04420 04408 04516 04548 04568 04548 04517 04546 04442 04521 04405 04497 04474 04549 04601 04640 04821 05383 06938 10658 total 100000
从第 18 个开始认真考虑
04817 04603 04715 04638 04736 04729 04727 04677 04687 04703 04710 04705 04631 04687 04654 04590 04761 05277 06294 08659 total 100000
从第 19 个开始认真考虑
04837 04739 04908 04927 04769 04763 04847 04926 04801 04904 04916 04836 04729 04877 04831 04918 04881 05082 05578 06931 total 100000
从第 20 个开始认真考虑
04968 05068 04998 05025 05046 04947 04937 04950 04967 04955 05026 05015 05016 04925 05094 05061 05021 05083 04921 04977 total 100000
计算得最优前 3 个的概率
从第 02 个开始认真考虑得到 最好 的概率是 0.156220
从第 03 个开始认真考虑得到 最好 的概率是 0.210080
从第 04 个开始认真考虑得到 最好 的概率是 0.240820
从第 05 个开始认真考虑得到 最好 的概率是 0.255020
从第 06 个开始认真考虑得到 最好 的概率是 0.261450
从第 07 个开始认真考虑得到 最好 的概率是 0.260500
从第 08 个开始认真考虑得到 最好 的概率是 0.254960
从第 09 个开始认真考虑得到 最好 的概率是 0.243100
从第 10 个开始认真考虑得到 最好 的概率是 0.228120
从第 11 个开始认真考虑得到 最好 的概率是 0.214320
从第 12 个开始认真考虑得到 最好 的概率是 0.198470
从第 13 个开始认真考虑得到 最好 的概率是 0.180790
从第 14 个开始认真考虑得到 最好 的概率是 0.161800
从第 15 个开始认真考虑得到 最好 的概率是 0.144290
从第 16 个开始认真考虑得到 最好 的概率是 0.123150
从第 17 个开始认真考虑得到 最好 的概率是 0.106580
从第 18 个开始认真考虑得到 最好 的概率是 0.086590
从第 19 个开始认真考虑得到 最好 的概率是 0.069310
从第 20 个开始认真考虑得到 最好 的概率是 0.049770
从第 02 个开始认真考虑得到 次好 的概率是 0.128250
从第 03 个开始认真考虑得到 次好 的概率是 0.157410
从第 04 个开始认真考虑得到 次好 的概率是 0.169180
从第 05 个开始认真考虑得到 次好 的概率是 0.168500
从第 06 个开始认真考虑得到 次好 的概率是 0.165290
从第 07 个开始认真考虑得到 次好 的概率是 0.160400
从第 08 个开始认真考虑得到 次好 的概率是 0.150370
从第 09 个开始认真考虑得到 次好 的概率是 0.142490
从第 10 个开始认真考虑得到 次好 的概率是 0.132480
从第 11 个开始认真考虑得到 次好 的概率是 0.123650
从第 12 个开始认真考虑得到 次好 的概率是 0.111540
从第 13 个开始认真考虑得到 次好 的概率是 0.103300
从第 14 个开始认真考虑得到 次好 的概率是 0.092940
从第 15 个开始认真考虑得到 次好 的概率是 0.084590
从第 16 个开始认真考虑得到 次好 的概率是 0.078490
从第 17 个开始认真考虑得到 次好 的概率是 0.069380
从第 18 个开始认真考虑得到 次好 的概率是 0.062940
从第 19 个开始认真考虑得到 次好 的概率是 0.055780
从第 20 个开始认真考虑得到 次好 的概率是 0.049210
从第 02 个开始认真考虑得到 次次好 的概率是 0.103660
从第 03 个开始认真考虑得到 次次好 的概率是 0.121750
从第 04 个开始认真考虑得到 次次好 的概率是 0.122830
从第 05 个开始认真考虑得到 次次好 的概率是 0.118610
从第 06 个开始认真考虑得到 次次好 的概率是 0.110930
从第 07 个开始认真考虑得到 次次好 的概率是 0.100480
从第 08 个开始认真考虑得到 次次好 的概率是 0.096720
从第 09 个开始认真考虑得到 次次好 的概率是 0.087940
从第 10 个开始认真考虑得到 次次好 的概率是 0.081740
从第 11 个开始认真考虑得到 次次好 的概率是 0.075200
从第 12 个开始认真考虑得到 次次好 的概率是 0.071070
从第 13 个开始认真考虑得到 次次好 的概率是 0.066550
从第 14 个开始认真考虑得到 次次好 的概率是 0.060870
从第 15 个开始认真考虑得到 次次好 的概率是 0.058560
从第 16 个开始认真考虑得到 次次好 的概率是 0.056080
从第 17 个开始认真考虑得到 次次好 的概率是 0.053830
从第 18 个开始认真考虑得到 次次好 的概率是 0.052770
从第 19 个开始认真考虑得到 次次好 的概率是 0.050820
从第 20 个开始认真考虑得到 次次好 的概率是 0.050830
计算得最差前 3 个的概率
从第 02 个开始认真考虑得到 最差 的概率是 0.003980
从第 03 个开始认真考虑得到 最差 的概率是 0.007770
从第 04 个开始认真考虑得到 最差 的概率是 0.011470
从第 05 个开始认真考虑得到 最差 的概率是 0.015510
从第 06 个开始认真考虑得到 最差 的概率是 0.018720
从第 07 个开始认真考虑得到 最差 的概率是 0.021750
从第 08 个开始认真考虑得到 最差 的概率是 0.024290
从第 09 个开始认真考虑得到 最差 的概率是 0.026720
从第 10 个开始认真考虑得到 最差 的概率是 0.029300
从第 11 个开始认真考虑得到 最差 的概率是 0.032160
从第 12 个开始认真考虑得到 最差 的概率是 0.035230
从第 13 个开始认真考虑得到 最差 的概率是 0.037370
从第 14 个开始认真考虑得到 最差 的概率是 0.039540
从第 15 个开始认真考虑得到 最差 的概率是 0.041330
从第 16 个开始认真考虑得到 最差 的概率是 0.043500
从第 17 个开始认真考虑得到 最差 的概率是 0.044200
从第 18 个开始认真考虑得到 最差 的概率是 0.048170
从第 19 个开始认真考虑得到 最差 的概率是 0.048370
从第 20 个开始认真考虑得到 最差 的概率是 0.049680
从第 02 个开始认真考虑得到 次差 的概率是 0.007170
从第 03 个开始认真考虑得到 次差 的概率是 0.008130
从第 04 个开始认真考虑得到 次差 的概率是 0.011620
从第 05 个开始认真考虑得到 次差 的概率是 0.014880
从第 06 个开始认真考虑得到 次差 的概率是 0.017710
从第 07 个开始认真考虑得到 次差 的概率是 0.021230
从第 08 个开始认真考虑得到 次差 的概率是 0.023610
从第 09 个开始认真考虑得到 次差 的概率是 0.027110
从第 10 个开始认真考虑得到 次差 的概率是 0.032090
从第 11 个开始认真考虑得到 次差 的概率是 0.033210
从第 12 个开始认真考虑得到 次差 的概率是 0.034690
从第 13 个开始认真考虑得到 次差 的概率是 0.037030
从第 14 个开始认真考虑得到 次差 的概率是 0.039620
从第 15 个开始认真考虑得到 次差 的概率是 0.041730
从第 16 个开始认真考虑得到 次差 的概率是 0.044100
从第 17 个开始认真考虑得到 次差 的概率是 0.044080
从第 18 个开始认真考虑得到 次差 的概率是 0.046030
从第 19 个开始认真考虑得到 次差 的概率是 0.047390
从第 20 个开始认真考虑得到 次差 的概率是 0.050680
从第 02 个开始认真考虑得到 次次差 的概率是 0.009380
从第 03 个开始认真考虑得到 次次差 的概率是 0.008320
从第 04 个开始认真考虑得到 次次差 的概率是 0.011950
从第 05 个开始认真考虑得到 次次差 的概率是 0.015480
从第 06 个开始认真考虑得到 次次差 的概率是 0.018840
从第 07 个开始认真考虑得到 次次差 的概率是 0.021810
从第 08 个开始认真考虑得到 次次差 的概率是 0.023470
从第 09 个开始认真考虑得到 次次差 的概率是 0.027140
从第 10 个开始认真考虑得到 次次差 的概率是 0.029980
从第 11 个开始认真考虑得到 次次差 的概率是 0.032590
从第 12 个开始认真考虑得到 次次差 的概率是 0.035330
从第 13 个开始认真考虑得到 次次差 的概率是 0.037470
从第 14 个开始认真考虑得到 次次差 的概率是 0.038940
从第 15 个开始认真考虑得到 次次差 的概率是 0.041370
从第 16 个开始认真考虑得到 次次差 的概率是 0.043660
从第 17 个开始认真考虑得到 次次差 的概率是 0.045160
从第 18 个开始认真考虑得到 次次差 的概率是 0.047150
从第 19 个开始认真考虑得到 次次差 的概率是 0.049080
从第 20 个开始认真考虑得到 次次差 的概率是 0.049980
冯义军
冯义军
14.02K
编辑于 2012-04-26
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (1)链接 • 2012-04-26
  • 0 支持
    一看到 这句:从第 20 个开始认真考虑得到 最好 的概率是 0.049770,就知道算法有问题,因为即使是从第20个开始,最差的概率也是1/20,即0.05,怎么可能比0.05还小呢 – rwxdfbb 2012-10-12

分析开来,这个是一个只有一次循环的随机数组抽取算法,只能循环一次,不可逆,换句话说,时间在这里面是没有意义的。数组长度为20,意味着可以放弃19次,不过到19次,你就审美疲劳了,认了吧。

一个方法,二分法,前10个做参考,可以比较出来质量好最好的;然后后10个里,只要有比上10个最好的那个好的,就可以选了~几率比较大。

不过,可能你前10个里已经遇到最好的了,但是你为了验证这个实验,放弃了,但是精神可嘉!

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-01-13

以前看过一道类似的题目,就是概率问题,不过总数10个,方法拿前面3个中作为候选,选出一个最好的,之后只要出现一个比前三个最好的那个还优秀的,那么就是这个了,因为这时选到最优秀的人的概率已经到了百分之九十多了。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (12)链接 • 2012-01-13
  • 0 支持
    这个我觉的可以前10个一个也不选,制作记录,记录最好的一个,从第十一个开始,选取接近前十当中记录最好的一个。。。 – AaronDjc 2013-01-08
  • 0 支持
    @BearTher 你的概率很低:(1/20)*(1/19)=0.002631 – liulam 2013-02-16
  • 0 支持
    哈哈,这个还真有意思 – wxf_fly 2013-02-16
  • 0 支持
    这个问题最后会不会变成讨论人生理想方向。。 – 王正武 2013-03-19
显示更多隐藏的评论
  • 社区维基

    1 票

  • 别凡溪
    6

sqrt(20)个是最好的概率是最大的,数学可以证明的

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-08-11
德问是一个专业的编程问答社区,请 登录注册 后再提交答案