找女朋友的策略

tiawing

假定有人给你介绍了20个女朋友,但每次你只能见其中一个,而且必须和前面的分手后,才能见下一个,也不允许再回去见已经分手的女友.
在这种条件下,请你给出一个策略,以期用最大概率找到你最满意的女友.

金眼睛

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

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|；

奇遇

清华的猥琐题目。。。。

light13

原帖由 lulijie 于 2009-2-24 23:40 发表
最满意的女朋友，只有比较了才知道。
最满意的女朋友相亲的顺序是随机的。
以下方案：
A方案：只要第一个，相中最满意的女朋友的概率是1/20，
B方案：第一个不要，后面相亲的比前面的都好就要，相中最满意的女朋 ...

说得很有道理，但是这个问题有一个地方我觉得不是很好。
女朋友不是一相处就知道好不好的，不同人有不同特点啊。
呵呵，这么说的就把一道好题糟蹋了。

lulijie

概率取最大值时，N必定是  int(m/e)+1  和 int(m/e) +2 之一。已经在
            http://bbs.mf8-china.com/viewthread.php?tid=22929&;page=2&extra=page%3D1#pid443741
             中的11#中得到证明。   不管m是大还是小。
证明过程中若有不当之处，希望大家批评指出。

[ 本帖最后由 lulijie 于 2009-3-2 19:23 编辑 ]

haohejiao

随缘~~~~~~~~~~~~

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) 取极值。）

金眼睛

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

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

lulijie

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