找女朋友的策略

金眼睛

来解一下这道题，时间有限，还有一点没研究透，实际当中不鼓励甩掉初恋啊！人并不是数字那么简单，呵呵！言归正传，策略如下：

设总数为N，其中最好的一个为第m个，我们从第S个开始考虑要或者不要，也就是放弃前S-1个，仅作为参考，从S开始，遇到所有见过当中最好的就选定，否则继续看下去。

这样当m<S的情况下，我们能成功的概率为0，因为我们放弃了最好的那一个；
当m>=S的情况下，我们能否成功的概率取决于从第一个到第m个当中次好的一个，设其位置为第k个，当k<S的时候，我们放弃了次好，由此为标准，我们一定能选到最好的第m个。当k>=S的时候，按策略，次好将被我们选中，失败。次好出现在第一个到第m-1个，能成功的概率为其在第S位之前的概率，即(S-1)/(m-1)。

总概率为：P0=P(最好在第m位且能被选中)    (m=1~N之和)
                     =P(最好在第m位且能被选中)    (m=S~N之和)
                     =P(m)*P(k<S)    (m=S~N之和)
                     =1/N*(S-1)/(m-1)     (m=S~N之和)
                (注：(S-1)/(S-1)认为等于1)

由无穷级数概念，当N比较大时，此概率可以写成：

P0=(S-1)/N*ln(N/(S-1))
对S求偏导数并令偏导为0：
(ln(N/(S-1))-1)/N=0
得到：N/(S-1)=e
即：S=[N/e]+1
(注：[ ]为取整符号)

由于这是N较大时的估算值，如果想真正取得最大值不建议直接得出结论，可以计算出S=[N/e]+1附近几个数的真实概率，然后通过比较确定S。
如N=20时，S=[20/e]+1=8

P(8)=1/20*(8-1)/(m-1)    (m=8~20之和)= 0.38421
同理可得：P(6)=0.3661      P(7)=0.37932     P(9)=0.38195    P(10)=0.37345
可见真的是S=8最大，不过当N为其他数值时，按公式算出的不一定正确，如何给出最为准确的公式，这点我还没有想好，抛砖引玉吧，有错误的地方也请大家指出。

[ 本帖最后由 金眼睛 于 2009-3-1 01:32 编辑 ]

金眼睛

原帖由 lulijie 于 2009-3-1 14:45 发表
金眼睛兄，当总次数较大时，你把数列换成对数来近似，进而得出结论，很好，妙！
不过当总次数很小时，结论也是成立的，又如何证明呢。
还有你的近似计算公式准确率约为69%，
若稍微修正一下，变成我的计算公式，准 ...

公式来源于推导，既然对于任意N和m，概率都能够计算了，又何必执着于最准确的公式呢？

否则看下面的公式int((N+0.858)/e)+1，在1000以内，正确率100%，不过能说明什么意义呢？是吧？：）

[ 本帖最后由 金眼睛 于 2009-3-1 16:29 编辑 ]

金眼睛

呵呵，我也不知道怎么证明，不过如果在有限情况下都成立本身就算证明吧？穷举法也可以证明一些问题啊 ：）

通过理论推导，我发现N和m近似满足下面的超越方程：

N=exp((m-1)/(m-2))*(m-2)

由N算m比较难，不过由m算N就方便多了，所以如果想求近似公式，也还存在另一种思路。

可以找出那些引起m变化的N值，看看它们与m有什么联系，这方面还得lulijie 等有能力，有时间的魔友继续研究了。

列出N，m的前几项：

m=1，2，3，4，5，6 ……
N=1，3，5，8，11，13 ……

金眼睛

再来提供一点线索，以及一个比较理想的近似公式，呵呵！

1/N*(S-1)/(m-1)     (m=S~N之和)
在N比较大时，以Pmin=(S-1)/N*ln(N/(S-1))为下界；以Pmax=(S-1)/N*ln(N/(S-2))为上界。


再给出一个近似计算公式，刚才验证了一下，可以保证到N=500000，准确率100%，可以按照这个公式的思路继续往下构造，保证公式的100%准确。


S=floor(N/exp(1)+1.31605935892)-
floor(1/(abs(N-97)*abs(N-24586)+1))+
floor(1/(abs(N-443900)+1))；
如果认为0的0次方为1（有些计算软件如此规定，不过通常认为无意义，或其值不定），公式还可以写为：
S=floor(N/exp(1)+1.31605935892)-0^(abs(N-97)*abs(N-24586))+0^abs(N-443900)；

上述公式是编程写法，写成数学形式为：
S=[ N/e+1.31605935892]-[1/(|N-97|*|N-24586|+1)]+ [1/(|N-443900|+1)]；
或S=[ N/e+1.31605935892]-0^(|N-97|*|N-24586|)+ 0^|N-443900|；