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

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的答案有效数字完全一样，但是小数点差了一位，应该是小数点点错了。