华中科技大学概率统计系副主任王湘君算对了吗？

gxqcn

gxqcn ,象本题的这种大数计算,只涉及到自然数的乘法和加法的话,用c/c++应该不难实现,而且计算速度应该也不会太慢吧?

有空的时候试试，领略一下大数计算的妙处。
nnd 发表于 2009-8-9 00:46

大数算法从无到有并不容易，里面涉及的东西非常复杂，尤其是数学方面的。
你可以自己试着调用比较成熟的算法库，比如 HugeCalc，很容易上手的。

nnd

51# gxqcn

不能注册。
还是自己写写看。反正是好玩。

halfcard

先列nnd的公式
$P(m,n)=\frac{m-n}{m}P(m-1,n)+\frac{n}{m}P(m-1,n-1)-\frac{n}{m}\frac{C_{m-15}^{n-14}}{C_{m-1}^{n-1}}P(m-15,n-14))$

这个公式是对的，对它简化，令f(m,n)表示m个数中有n个1和m-n个0，不含14+连号的个数，将下列公式代入上式
$p(m,n)=\frac{f(m,n)}{C_{m}^{n}}$
另外三个类似。

就可得到f(m,n)=f(m-1,n)+f(m-1,n-1)-f(m-15,n-14)
这个式子得到也可这样来考虑：将m个数分成两类，第一类是第一个数是0，则不含14+连号的个数为f(m-1,n);
第二类是第一个数是1，则不含14+连号的个数为f(m-1,n-1)，但前13个数为1，第14个数为0的个数f(m-15,n-14)要去掉。

这个公式的初始条件为
$(1)0\leq i=j\leq 13,f(i,j)=1;(2)14\leq i=j\leq 514,f(i,j)=0$

$(3)0\leq i< j\leq 514,f(i,j)=0;(4)j\leq 13,i>j,f(i,j)=C_{i}^{j}$

算法就用shshsh_0510的方法，建一个矩阵，将初始条件填好，再用循环算f(m,n)=f(m-1,n)+f(m-1,n-1)-f(m-15,n-14)

我用mathematica6算，得到
f(1138,514）=4284074396221510886275861026177997288725264485159302362978066655607478
                         2032658507566320945128720606753357196632016576372051645816236394422705
                         6561316392074446585309130262208581029387259788576843150181617698574122
                         4398022362115709600005522979455098441048656026253762518234417944625658
                         31631008360066615506863519397899985401299201968936033633750
这个数和shshsh_0510的公式得到的数加起来就是
$C_{1138}^{514}$

我用概率加法公式（容斥原理）也得到相应结果，计算过程也采用了shshsh_0510的矩阵方法。非常感谢shshsh_0510.
http://e.ys168.com/?halfcard   常规\14连号概率.pdf

056254628

对于该题大家可以看看其他人的解题思路。
http://bbs.mf8.com.cn/viewthread.php?tid=34955&extra=page%3D3  的7楼的递推公式的定义。
设  f(n, m, k) 表示从1到n 共n个数中取m个数，至多有k连号的所有可能数。    c(n,m)  表示从n个中取m个的组合数
那么从1到1138中取514个数  
          有14连号且没有15连号的概率=[  f(1138,514,14)-f(1138,514,13)  ] / c(1138,514)
            14连号及以上的概率为=1 -  f(1138,514,13) / c(1138,514)

winxos

由于种种原因，好久没来论坛看了，
好亲切又能看到这么热烈的讨论^_^
向mathe,GXQCN,无心人,sh等几位老大问好

mathe

多谢

gxqcn

55# winxos

记得常来啊。。。

winxos

55# winxos

记得常来啊。。。
gxqcn 发表于 2009-8-15 22:31

一定要经常来接受各位老大的熏陶哈.

nnd

54# 056254628

这种解法很黄很暴力。是赤裸裸的暴力穷举。
但是还是有重复计算，比如出现了前后两次14连号的情况。

shshsh_0510的算法算出结果用了多长时间？

056254628

回59#：
lulijie的解法应该没问题，跟shshsh_0510的解法实际上是相同的，但是shshsh_0510的简单些，lulijie的解法把第一个人没被选中的情况又分成了最小第二个被选中、最小第三个被选中等等很多情况，而shshsh_0510的算法中这些都记在一种情况中。
还有lulijie的答案跟shshsh_0510的答案有效数字完全一样，但是小数点差了一位，应该是小数点点错了。