找女朋友的策略

金眼睛

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

设总数为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 编辑 ]

tonylmd

啊……除了设的变量刚好相反 结论完全一样啊……囧…
原来是偏导数求出e?没学到呢 厉害了

tonylmd

lulijie给了公式62#以及下贴
http://bbs.mf8-china.com/viewthread.php?tid=22929
~
金眼睛给了证明过程83#
~
此题完结

[ 本帖最后由 tonylmd 于 2009-3-1 01:53 编辑 ]

傲气第六

都要了.....................

lulijie

金眼睛兄，当总次数较大时，你把数列换成对数来近似，进而得出结论，很好，妙！
不过当总次数很小时，结论也是成立的，又如何证明呢。
还有你的近似计算公式准确率约为69%，
若稍微修正一下，变成我的计算公式，准确率可达到95%。
详见http://bbs.mf8-china.com/viewthread.php?tid=22929&amp;extra=page%3D1

金眼睛

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

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

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

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

lulijie

不过当总次数很小时，概率公式不能用对数的近似公式来模拟，但结论仍然是成立的，又如何证明呢。

lulijie

确实有概率的精确计算公式，但不求助电脑的话，计算非常麻烦，
如果有个好的，正确率高的近似公式，让人人都可以计算出正确的结果，又有什么不好呢？
N的计算公式  N=int[(m+△)/e] +1        int为取整函数。  修正值△的不同，确实影响到模拟结果的正确率。
但发现m=97是个奇怪的值，若通过△的修正，使得m=97能由公式正确计算出，比如取△=0.858，但m较大时，却造成了错误率更高。
若不理睬m=97，却发现其他m值计算不正确的，可以通过△的修正而变成正确。
我计算了10万以内的m值：
当    0.859133408　<= △<=0.859138412  ，   计算公式仅在m=97有偏差。
     △=0.859133407，   计算公式在m=97和73757有偏差。
     △=0.859138413，   计算公式在m=97和24586有偏差。
是不是除了m=97，对于更大的m值，计算公式的偏差都可以通过△的修正得以消除呢？△必须在以下范围内：
          0.859133407< △<0.859138413

金眼睛

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

通过理论推导，我发现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 ……

lulijie

从  N的计算公式  N=int[(m+△)/e] +1     
  变形为   N=int(m/e + △‘ ）+1   

   随m值的增加，N的增加严格按照m/e的比率增加，与m是否足够大无关，对于很小的m也成立。
这中间难道没有 还不为人知的内在的规律嘛？
--------------------------------------------------------
假设，概率计算公式   P(N) =(N-1)/m   *    ∑ 1/i    （ ∑中的 i 从N-1到 m-1）  
    能通过推广，使得N可以取实数，N取整数只是这个函数的特例，那么P(X)的极值问题就不会因为整数的不连续性，N值被迫要从
   int(m/e ）  和   int(m/e)+1      两个数中取一个。
那样的话，取极值时的N，不再因为是整数需二者选一，而不能确定到底是哪个，就可以光明正大的写成以下：
       X=m/e     时   P(X) 取极值。
金眼睛兄的    函数  P(X)=(X-1)/m * ln(m/(X-1))      确实X=m/e时取极值，
但却不是  概率计算公式 的推广，只能算是m值较大，X值较大时的一个近似值，对于m值较小，X值较小时偏差较大，所以还不是我们要寻找的P（X）。
-------------------------------------------
符合自变量X为实数的概率计算公式P(X) 到底是什么东东呢，如此的神秘，谁能揪出它来。  （X若规定取整数，就可化为本贴题目。并且满足   X=m/e    时   P(X) 取极值。）