魔方吧·中文魔方俱乐部

标题: 求概率(大家讨论讨论) [打印本页]

作者: superacid 时间: 2009-7-6 18:20:00 标题: 求概率(大家讨论讨论)

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

题目看清楚了！！！

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

作者: 今夜微凉 时间: 2009-7-6 18:25:31

又见超级强悍的楼主~~~先占个位置，再看题~~~呵呵
题目很容易看懂~~但是难度挺大~~因为条件是奇数次~~~
三楼谈论的应该是最少步数吧~~条件是奇数次~~难道是用完全归纳法，假设从是1，看策略能否奇数次猜中，一直到2009~~~求整体概率？好像计算量很恐怖~~

[ 本帖最后由今夜微凉于 2009-7-6 18:29 编辑 ]

作者: 604222420 时间: 2009-7-6 18:25:51

1005、503、252、126、63、32、16、8、4、2、1（假设是1）一直从中间劈就可以，如果到最后剩下三个数你取中，这时你告诉你比它大，但如果你直接选大数就是偶数次，所以可以再选一个错误答案。
概率就不会了，这是最佳策略。
如果剩下2个，靠运气了。

作者: superacid 时间: 2009-7-6 18:28:32

原帖由 superacid 于 2009-7-6 18:20 发表
你必须要猜测在已知的条件下n的一个可能值

就是说如果你猜了一个1000，别人告诉你n>1000，那么你以后猜的数必须大于1000，大家注意一下。

作者: q376997368 时间: 2009-7-6 18:29:23

log[sub]2[/sub]2009
??多少啊

作者: 604222420 时间: 2009-7-6 18:33:11

那就惨了。。。劈到最后的话剩下三个或两个，两个靠运气，三个看前面的共有几次。。。

作者: lulijie 时间: 2009-7-6 18:39:06

S个数从小到大排列，N次猜数，猜中的概率为P（N)
那么 P（N）=(2^N-1)/S （猜的数非边界值）
参见本版的帖子
http://bbs.mf8-china.com/viewthread.php?tid=19454&extra=page%3D8&page=1
对于本题目，S等于2009，当N>=11，概率就等于1，也就是说一定能在11次内100%猜中。

作者: aben306 时间: 2009-7-6 18:39:56

这个可能是初二下学期的知识吧...数学没学好.

作者: lulijie 时间: 2009-7-6 18:44:28

楼主如果一定要求奇数次猜中，那么在偶数次猜的时候，你报的数就有可能无意中撞上正确答案，如果这算失败的话，那么概率就要把这些情况减去。

作者: 604222420 时间: 2009-7-6 18:44:42 标题: 回复 7# 的帖子

LZ求奇数次的概率（天哪多少次了就差一字节）

作者: 墨迹 时间: 2009-7-6 18:49:31

我刚学完概率高一呵呵这个用不到概率多少知识用二分法是最佳策略了三楼就是二分法是正解了如果是这样这题似乎有点简单了高一就能解决了理解能力强的中学可能就会但是是不是另有玄机呢等LZ 点评

作者: lulijie 时间: 2009-7-6 19:09:01

M个数从小到大排列，N次猜数，N次之内猜中的概率为S(N)
那么 S(N)=(2^N-1)/M
那么刚好第N次猜中的概率为P(N).
那么P(N)=S(N)-S(N-1)=(2^N-1)/M-(2^(N-1)-1)/M=2^(N-1)/M
楼主的题M=2009
所求的概率=P(1)+P(3)+P(5)+P(7)+P(9)+P(11)=1/2009(1+4+16+64+256+1024)=1365/2009
-------------------------------
P(11)应该=S(11)-S(10)=1-1023/2009=986/2009 1024-986=38
所以上述结果应为（1365-38）/2009=1327/2009

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

作者: superacid 时间: 2009-7-6 19:09:32

大家不要以为这道题很简单啊！

作者: 墨迹 时间: 2009-7-6 19:39:34

我算了一个1/341 LZ 对吗

作者: superacid 时间: 2009-7-6 19:47:14

我也不知道答案，所以让大家讨论讨论。

作者: superacid 时间: 2009-7-6 19:51:18

好像1,2,3,...一个一个猜下去，概率也有1005/2009了吧

作者: 357433865 时间: 2009-7-6 19:57:31

三楼的是最佳猜测路线，概率的问题有点忘记了呀……

作者: lulijie 时间: 2009-7-6 20:06:25

也可以这样计算：
偶数次猜中的概率=(2+8+32+128+512)/2009=682/2009
那么奇数次猜中的概率=1-682/2009=1327/2009

作者: JAVE 时间: 2009-7-6 20:32:02

饿。我下学期初二。大家顺便帮我补补知识。呵呵

作者: 墨迹 时间: 2009-7-6 20:36:26

改了好几次终于定下来了三楼肯定是最佳方案当我们从中间取一个数1005如果N=1005那么这就是一个可能数值当然也可能大于或小于1005也就是说在1005前后各有1004个数字还有可能是N 那么我们继续取中位数大家会发现偶数是没有整数中位数的但是我们又要取整数那么我们就取最靠近中位数的整数例如1004的中位数我们可以取 502 也可以取503 如果取502那么此时小于N的可能数字个数就是501个大于N的数字可能个数就是 502个如果取503那么此时小于N的数字个数就是502个则大于N的数字个数就是501个照这个规律算下去通过最简单的画树状图地方法可看出总抽取次数应该在 11次也就是向楼上所说的 11次之内一定能抽到但是奇数次就只有6次这就是最佳方案至于获胜的概率没办法确实是1 因为 LZ 没有限制抽取次数只是说一直抽下去那么到最后一定能抽出来的所以概率只能是1

[ 本帖最后由墨迹于 2009-7-6 20:57 编辑 ]

作者: lulijie 时间: 2009-7-6 20:58:07

最优方案不只一个，
第一次取数，取在985和1024之间的任何数，概率都一样。

作者: 墨迹 时间: 2009-7-6 21:01:31

原帖由 lulijie 于 2009/7/6 18:39 发表
S个数从小到大排列，N次猜数，猜中的概率为P（N)
那么 P（N）=(2^N-1)/S （猜的数非边界值）
参见本版的帖子
http://bbs.mf8-china.com/viewthread.php?tid=19454&extra=page%3D8&page=1
对于本题目，S等于2009，当 ...

请问一下这位大哥多大了？好厉害啊我琢磨了半天呢啊原来你早就给出答案了还比我更深奥看来不好好学习就是不行啊呵呵

作者: lulijie 时间: 2009-7-6 21:05:48

我女儿就要读小学3年纪了。

作者: 墨迹 时间: 2009-7-6 21:09:26

我的天啊吓死咯~~~~呵呵

作者: superacid 时间: 2009-7-6 21:38:45

回复墨迹：
1.你在20楼的帖子涉嫌钻牛角尖

，题目写得很清楚：必须要猜测在已知的条件下n的一个可能值
我在4楼解释了，你好好看看。
2.概率显然不为1，如果你不巧在第2次猜测是直接命中答案怎么办？不久是偶数次了吗？

作者: 墨迹 时间: 2009-7-6 21:44:19

不行了还是复习去了高手解吧有难度啊 LZ 真绝找这么个题

作者: lulijie 时间: 2009-7-6 22:28:11

先研究一下只有三个数的情况：
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。

作者: lulijie 时间: 2009-7-6 22:40:50

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

作者: lulijie 时间: 2009-7-6 23:10:16

按照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 时间: 2009-7-7 00:44:33

用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 时间: 2009-7-7 01:03:42

具体取数过程如下：逗号前面的数表示奇数次取的数（所有可能数值第几小的数，或第几大的数）
                           逗号后面的数表示偶数次取的数（所有可能数值第几小的数，或第几大的数）
   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)
这样最优方案就是第一次取 4，
若大了，那么剩3个数可选，因为是偶数次，查上表，第二次选2
若小了，还剩2005个数可选，因为是偶数次，查上表得2，即第二次选第2小的数，即4+2=6。
。。。。。。
最大概率 A(2009)=0.666500746640127 = 1339/2009
当然最优方案不只一种，但最大概率不会超过上面的值。

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

附件: [所有数据] 取数奇数次胜.rar (2009-7-7 01:03:42, 2.93 KB) / 下载次数 4
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTgyNzd8N2JiM2QzYTV8MTcxNTcxMjE3MXwwfDA%3D

作者: superacid 时间: 2009-7-7 08:03:08

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

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

作者: Osullivan 时间: 2009-7-7 13:22:10

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

作者: Osullivan 时间: 2009-7-8 20:02:03

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

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

作者: lulijie 时间: 2009-7-8 20:45:12

详细计算：关于第一次取数到底可以取那些数，其实很多很多数都可以取。
对于达到奇数次胜最大概率的第一次取数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（因为可选任意数），这样因为两侧对称，数字又减小得快，工作量明显下降。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)