选中最大数的策略

lulijie

tiawing的那个关于策略的帖子，由于涉及到影响不好的东西，版主强烈要求修改，我就代tiawing修改成本贴，原著者仍归属tiawing。并把一些结论一并发表，有些虽然经电脑证实非常吻合事实，但未经证明。但因为结论非常出人意料，显示了数学的奇妙，所以公布出来，供大家分享。若有人能证明之，希望能不惜笔墨。则不胜欣喜。
---------------------------------------------------------------------------------------------------------------
有m个实数，两两不等，每次只显示一个数给你看，你可以选择获取它或放过它看下一个数。你的目标是得到最大的数。
那么如何安排策略，才能使得获取最大数的概率最高？
策略（N)  ：放过前面的N-1个数，从第N个数开始，若与前面的所有数相比是最大的，就选择该数，否则放过，看下一个数，一直到所看的数与前面的所有数相比是最大的为止，选择该数。若看到了最后一个数，就只能选择最后一个。

那么：
    策略（N) 获取最大数的概率P(N) =(N-1)/m   *    ∑ 1/i    （ ∑中的 i 从N-1到 m-1）       N>1   
                                               P(N) =1/m                                                                     N=1
假设M1和M2是  最接近 (m+1)/e  的两个整数，M1<M2                    其中e为自然对数，=2.718281828……
那么    结论1：使得概率P最大的N值必等于M1或M2。
           结论2：m趋向于无穷大时，P(M1+1) 或P(M2+1)的极限等于1/e 。
                       也就是说m很大时，最优策略获取最大数的概率等于1/e。
---------------------------------------------------------------------------------------------------
11#已经证明：假设M1和M2是  最接近 m/e  的两个整数，M1<M2 ，结论1成立。
  所以   绿字部分 (m+1)/e 修改为m/e为妥当。   若不改的话是否成立还有待证明。
                            M1或M2 应该为  M1+1或M2+1 即 int(m/e)+1 或 int(m/e)+2
             或者   用n表示放过的数，即n=N-1，     结论1也可表示为：     使得概率P最大的n值必等于M1或M2。
------------------------------------------------------------------------------
最终结论应该是如下：
假设M2是  比 m/e  大的第一个整数，即M2 =int(m/e)  +1                 其中e为自然对数，=2.718281828……
那么    结论1：使得概率P最大的N值必等于M2或M2+1。
                  或者表示为  使得概率P最大的n值必等于M2或M2-1。          n=N-1 表示放过的数
           结论2：m趋向于无穷大时，P(M2) 或P(M2+1)的极限等于1/e 。
                       也就是说m很大时，最优策略获取最大数的概率等于1/e。
----------------------------------------------------------------------------------------------
         上述有些乱，我把题目，求证的结论，以及证明的过程，全部一起集中发在14楼中。


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

R'cube

沙发没人要我先拿下了~~~~~~~

lulijie

使得概率P最大的N值可以用公式计算：
     N=int[(m+1)/e] +1                   公式算出的结果与正确值大部分都一致，偶尔有少数比正确值大1。

从m=3至10000中，公式与正确值不一致的总数有519个：只占5%左右。
        以下为公式与正确值不一致的m值
10，29，48，67，86，97，116，135，154，173，192，203，222，241，260，279，309，328，347，366，
385，396，415，434，453，472，502，521，540，559，578，589，608，627，646，665，695，714，733，
752，771，782，801，820，839，858，888，907，926，945，964，975，994，1013，1032，1051，1081，
1100，1119，1138，1157，1168，1187，1206，1225，1244，1274，1293，1312，1331，1350，1361，1380，
1399，1418，1437，1456，1467，1486，1505，1524，1543，1573，1592，1611，1630，1649，1660，1679，
1698，1717，1736，1766，1785，1804，1823，1842，1853，1872，1891，1910，1929，1959，1978，1997，
2016，2035，2046，2065，2084，2103，2122，2152，2171，2190，2209，2228，2239，2258，2277，2296，
2315，2345，2364，2383，2402，2421，2432，2451，2470，2489，2508，2538，2557，2576，2595，2614，
2625，2644，2663，2682，2701，2731，2750，2769，2788，2807，2837，2856，2875，2894，2913，2924，
2943，2962，2981，3000，3030，3049，3068，3087，3106，3117，3136，3155，3174，3193，3223，3242，
3261，3280，3299，3310，3329，3348，3367，3386，3416，3435，3454，3473，3492，3503，3522，3541，
3560，3579，3609，3628，3647，3666，3685，3696，3715，3734，3753，3772，3802，3821，3840，3859，
3878，3889，3908，3927，3946，3965，3995，4014，4033，4052，4071，4082，4101，4120，4139，4158，
4177，4188，4207，4226，4245，4264，4294，4313，4332，4351，4370，4381，4400，4419，4438，4457，
4487，4506，4525，4544，4563，4574，4593，4612，4631，4650，4680，4699，4718，4737，4756，4767，
4786，4805，4824，4843，4873，4892，4911，4930，4949，4960，4979，4998，5017，5036，5066，5085，
5104，5123，5142，5153，5172，5191，5210，5229，5259，5278，5297，5316，5335，5346，5365，5384，
5403，5422，5452，5471，5490，5509，5528，5558，5577，5596，5615，5634，5645，5664，5683，5702，
5721，5751，5770，5789，5808，5827，5838，5857，5876，5895，5914，5944，5963，5982，6001，6020，
6031，6050，6069，6088，6107，6137，6156，6175，6194，6213，6224，6243，6262，6281，6300，6330，
6349，6368，6387，6406，6417，6436，6455，6474，6493，6523，6542，6561，6580，6599，6610，6629，
6648，6667，6686，6716，6735，6754，6773，6792，6803，6822，6841，6860，6879，6898，6909，6928，
6947，6966，6985，7015，7034，7053，7072，7091，7102，7121，7140，7159，7178，7208，7227，7246，
7265，7284，7295，7314，7333，7352，7371，7401，7420，7439，7458，7477，7488，7507，7526，7545，
7564，7594，7613，7632，7651，7670，7681，7700，7719，7738，7757，7787，7806，7825，7844，7863，
7874，7893，7912，7931，7950，7980，7999，8018，8037，8056，8067，8086，8105，8124，8143，8173，
8192，8211，8230，8249，8279，8298，8317，8336，8355，8366，8385，8404，8423，8442，8472，8491，
8510，8529，8548，8559，8578，8597，8616，8635，8665，8684，8703，8722，8741，8752，8771，8790，
8809，8828，8858，8877，8896，8915，8934，8945，8964，8983，9002，9021，9051，9070，9089，9108，
9127，9138，9157，9176，9195，9214，9244，9263，9282，9301，9320，9331，9350，9369，9388，9407，
9437，9456，9475，9494，9513，9524，9543，9562，9581，9600，9619，9630，9649，9668，9687，9706，
9736，9755，9774，9793，9812，9823，9842，9861，9880，9899，9929，9948，9967，9986，
---------------------------------------------
对于上述不一致的m值，将公式算出的N值减去1就可得到正确值。

lulijie

策略（N) 获取最大数的概率P(N) =(N-1)/m   *    ∑ 1/i    （ ∑中的 i 从N-1到 m-1）  
金眼睛在http://bbs.mf8-china.com/viewthread.php?tid=22652&amp;extra=page%3D1&page=9    的83楼中：
提出   但m和N较大时，              ∑ 1/i    （ ∑中的 i 从N-1到 m-1）
                          可以用          ln  m/(N-1)    近似代替。
      P(N) =(N-1)/m   *    ∑ 1/i        就相当于  P(N) =(N-1)/m   *  ln  m/(N-1)
    然后求导，获得    m/(N-1)=e  时P(N)  最大。
   得到  N=int(m/e) +1    或附近得到最大值。
--------------------------------------------------------------
妙妙妙，确实妙。给理论上的证明，给出了很好的方向，对于m，N较大时基本上能证明。
但是我1#的结论1却是与m的大小无关，就算m很小，也成立，金眼睛的上述证明方法就不成立了。m很小又如何证明结论1成立呢？
------------------------------------------------------------------------------------
还有金眼睛给出的N计算公式 N=int(m/e) +1  与本人的计算公式 N=int[(m+1)/e] +1    有所区别：
m从3到10000，用公式计算N，金兄算出的N值与正确值相比，有3159个不相符；正确率69%。
                        本人的公式算出的N值与正确值相比，只有519个不相符；正确率95%。
所以本人的公式远远优于金兄的。

lulijie

假设策略（N) 获取最大数的概率最高：
   那么N的计算公式  N=int[(m+△)/e] +1        int为取整函数。
金眼睛的计算公式  △=0，正确率68.4%
我的计算公式   △=1    ，正确率94.8%
经过计算，当 △=0.8591时算出的结果，正确率最高：
     N=int[(m+△)/e] +1              △=0.8591
   m<=30000，   仅m=97时，有偏差，其余均正确，正确率9999.6%。
    ----------------------------------------------------------------------
红字部分出错了，应该为99.996%，谢谢骰迷和 tonylmd批评指出。

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

juventus66

学习了

lulijie

最新的正确率最高的N值计算公式：
    N=int[(m+△)/e] +1        int为取整函数。 △为修正值，e为自然对数。e=2.71828182845905
△=0.859135，      10万以内的m值，只有m=97是有偏差。
-----------------------------------------------------------------------------
以下计算公式，对于m<=100000结果均正确。
    m=97， N=int[(m+△)/e]
    其他的m，N=int[(m+△)/e] +1

kexin_xiao

太深奥了,来学习一下,加分鼓励!

骰迷

正确率9999.6%?比率怎可能比100%大？

tonylmd

哈哈~笔误了