- 最后登录
- 2013-11-11
- 在线时间
- 873 小时
- 阅读权限
- 40
- 注册时间
- 2008-9-15
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
|
用数学归纳法来证明
S个数从小到大排列,N次猜数,猜中的概率为P(N)
那么 P(N)=(2^N-1)/S (猜的数非边界值)
N=1 P(1)=1/S 显然成立。
假设N=k时 P(k)=(2^k-1)/S 成立
那么,对于N=k+1时,证明如下:
第一次猜后,3种可能性的概率(第一次猜第X个数)
猜中的可能性为 1/S
大了的可能性为 (S-X)/S
这种情况剩下的数共有(S-X)个,还有k次猜的机会
那么猜中的机会为 (2^k-1)/(S-X)
小了的可能性为 (X-1)/S
这种情况剩下的数共有(X-1)个,还有k次猜的机会
那么猜中的机会为 (2^k-1)/(X-1)
总的猜中概率为
1/S + (S-X)/S * (2^k-1)/(S-X) + (X-1)/S * (2^k-1)/(X-1)
=1/S + (2^k-1)/S + (2^k-1)/S
=(2^(k+1)-1)/S
故N=k+1时,公式也成立。
所以上述通项公式成立。 |
|