求概率(大家讨论讨论)

superacid

在区间[1,2009]中等可能性地选取一个整数n，此数对你是未知，你的任务是通过奇数次的猜测把n找出来。
在每一次猜测中，你必须要猜测在已知的条件下n的一个可能值，在每次猜错之后，你会被告知你猜的数与n的大小关系。
在你采取最佳策略的情况下，你获胜的概率是多少？


题目看清楚了！！！

[ 本帖最后由 superacid 于 2009-7-6 19:10 编辑 ]

lulijie

详细计算：关于第一次取数到底可以取那些数，其实很多很多数都可以取。
对于达到 奇数次胜最大概率的第一次取数C(N)：
     N除以3的余数为1，  可以取形如3k+1的所有数。
     N除以3的余数为2，  可以取任何数。
     N是3的倍数，可以取形如3k或3k+1的所有数。
对于达到偶数次胜最大概率的第一次取数D(N)：
     N除以3的余数为1，  可以取任何数。
     N除以3的余数为2，  可以取形如3k+1或3k+2的所有数。
     N是3的倍数，可以取形如3k+2的所有数。
------------------------------------------------------
对于N=2009，奇数次胜。
     因为2009 mod 3=2，所以第一次取任何数都可以，那么取1，
    剩下2008个数，因为2008 mod 3=1，因为是偶数次，也可以取任意数，不妨取1，即1+1=2
    剩下2007个数，因为2007 mod 3=0，因为是奇数次，可以取形如3k或3k+1的所有数。不妨也取1，即2+1=3
    剩下2006个数，因为2006 mod 3=2，因为是偶数次，可以取形如3k+1或3k+2的所有数。不妨也取1，即3+1=4
    剩下2005个数，因为2005 mod 3=1，因为是奇数次， 可以取形如3k+1的所有数。不妨也取1，即4+1=5
     剩下2004个数，因为2004 mod 3=0，因为是偶数次，可以取形如3k+2的所有数。可取2，即5+2=7。
   这样开始分两条路，若大了，只能取6，若小了，还剩2002个数，2002 mod 3 =1，可取1，即7+1=8.
    .......
----------------------------------------
N=2009，当然，第一次可以选1005（因为可选任意数），这样因为两侧对称，数字又减小得快，工作量明显下降。

Osullivan

原帖由 lulijie 于 2009-7-7 01:03 发表
具体取数过程如下：   逗号前面的数表示奇数次取的数（所有可能数值第几小的数，或第几大的数）      
                             逗号后面的数表示偶数次取的数（所有可能数值第几小的数，或第几大的数）
    ...

其实可以证明当N无限大时，概率为2/3的~~~~~~~~~~~~~

Osullivan

我来晚啦~~~~~~~~~
大家都解决的差不多了~~~~~~~~~
我也只想到二分法哦~~~~~~~~
lulijie做法很严密正确~~~~~~~

superacid

看上去挺有道理的，方法就应该是这样的。

我各方面就组合比较差，所以请大家多多指教。

lulijie

具体取数过程如下：   逗号前面的数表示奇数次取的数（所有可能数值第几小的数，或第几大的数）      
                             逗号后面的数表示偶数次取的数（所有可能数值第几小的数，或第几大的数）
       C()，D()
N=2：1，1
N=3：1，2
N=4：1，1
N=5：1，1
N=6：1，2
N=7：1，1
N=8：1，1
N=9：1，2
N=10：1，1
..........
N=2000：4，2
N=2001：1，2
N=2002：1，2
N=2003：1，2
N=2004：1，2
N=2005：1，2
N=2006：1，2
N=2007：1，2
N=2008：1，2
N=2009：4，2
---------------
所有数据    取数奇数次胜.rar (2.93 KB, 下载次数: 4)

2009-7-7 01:03:42 上传

下载次数: 4
所有数据

这样最优方案就是第一次取 4，
    若大了，那么剩3个数可选，因为是偶数次，查上表，第二次选2
    若小了，还剩2005个数可选，因为是偶数次，查上表得2，即第二次选第2小的数，即4+2=6。
  。。。。。。
最大概率  A(2009)=0.666500746640127  = 1339/2009
当然最优方案不只一种，但最大概率不会超过上面的值。

[ 本帖最后由 lulijie 于 2009-7-7 18:17 编辑 ]

lulijie

用A(N)表示 N个数，奇数次猜中的最大概率，C(N)表示奇数次猜中最大概率时第一次取的数，
   B(N)表示 N个数，偶数次猜中的最大概率。D(N)表示偶数次猜中最大概率时第一次取的数，
那么获得递推公式：
  A(1)=1
  B(1)=0
  A(N)= 以下数的最大值
                   1 /N + (N- 1) /N * B(N- 1)   (第一次取最边数得出的最大概率）
                   1 /N + (X - 1) / N* B(X - 1) + (N - X) / N * B(N- X)      (第一次取X得出的最大概率，2<X<N-1）
  B(N)= 以下数的最大值
                    (N- 1) /N * A(N- 1)   (第一次取最边数得出的最大概率）
                    (X - 1) / N*A(X - 1) + (N - X) / N * A(N- X)      (第一次取X得出的最大概率，2<X<N-1）
-------------------------------------------------------------------------
利用电脑，算出
    A(2009)=0.666500746640127

lulijie

按照28#的方案，第一次猜中概率  1/2009,第二次猜中概率  1/2009，第三次猜中概率 2/2009......
    第N次猜中概率P(N)
   那么P(1)=1/2009
          P(N)  =P(N-1)           N为偶数
          P(N)     =2* P(N-1)      N为奇数
推出通项  P(N)=2 ^  (N/2-1)   * 1/2009                  N为偶数
                P(N)=2 ^  (N-1)/2   * 1/2009                  N为奇数

那么当N=18时，前N项的和等于1022/2009,
          P(19)=512/2009
         那么P(20)=475/2009
所以奇数次猜中的概率=511/2009+512/2009=1023/2009
概率没有优于每次猜中间数的方案。
-------------------
刚才算错了，重新算了一下。

[ 本帖最后由 lulijie 于 2009-7-6 23:31 编辑 ]

lulijie

我觉得对于任意N个数，最优方案应该是：
   奇数次猜，取边数，偶数次猜取中间数。
比如2009个数，
       2009，1004（大了），1003（小了），502。。。。。。
---------------------------
概率是否大于每次都取中间数的方案，有待检验。

lulijie

先研究一下只有三个数的情况：
1，2，3
第一次选1，第一次命中概率1/3，
                   第一次猜不中概率2/3，那么第二次猜a（无论2还是3)，猜中概率1/2,结束
                                                       第二次猜不中概率1/2,那么第三次猜中概率1.
              奇数次猜中的概率=1/3+2/3*1/2*1=2/3。
第一次选3，结果同第一次选1。
第一次选2，第一次命中概率1/3，
                   第一次猜不中概率2/3，第二次猜中概率1.
              奇数次猜中的概率=1/3。
-------------------------------------
所以3个数的情况：最佳方案是先选最边的数，第二次任选一数，奇数次猜中概率有2/3。