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

nnd

我写了一个很简单很粗糙的大数库，用shshsh_0510的方法计算大概需要55秒钟。
不过如果完全按照他的算法，要占差不多1G内存。简化的算法占差不多50M内存。
再简化一下运算时间可以控制在40秒以内。

nnd

53# halfcard

这种方法最好，3秒搞定。

sir_chen

记号码总数为n,从中任取k个,连续号码不小于r个的概率是
$p={(n-r+1)*C(n-r,k-r)}/{C(n,k)}={(n-k+1)*k!*(n-r)!}/{n!*(k-r)!}$
将n=1138,k=514,r=14代人得到
$p={625*514!*1124!}/{1138!*500!}=0.0083304338896595428237333323169778$

sir_chen

通过程序模拟也可以得到相同的结果,以下是用Java编写的程序
public class SeriesTest
{
        private int n;
        private int k;
        private int r;
        private int a[];
        private int C[];
        public SeriesTest(int n,int k,int r)
        {
                this.n=n;
                this.k=k;
                this.r=r;
                initial();
        }
        public void initial()
        {
                int i;
                a=new int[n];
                C=new int[n];
                for(i=0;i<n;i++)
                        a[i]=i;
        }
        public int random(int min,int max)//create a number between min and max included both
        {
                return (int)Math.round(Math.random()*(max-min))+min;
        }
        public void randomSort()
        {
                int i,j,temp;
                for(i=0;i<n-1;i++)
                {
                        j=random(i,n-1);
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;
                }
        }
        public void randomSort(int k)
        {
                int i,j,temp;
                for(i=0;i<k;i++)
                {
                        j=random(i,n-1);
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;
                }
        }
        public void countSort(int k)
        {
                int i,j;
                for(i=0;i<n;i++)
                        C[i]=0;
                for(i=0;i<k;i++)
                        C[a[i]]=1;
                for(i=0,j=0;j<k;i++)
                        if(C[i]!=0)
                                a[j++]=i;
        }
        public boolean isSeriesOfLength(int k)
        {
                int i;
                countSort(k);
                for(i=r-1;i<k;i++)
                        if(a[i]-a[i-r+1]==r-1)
                                return true;
                return false;
        }
        public double pr(int loop)
        {
                int i,j;
                for(i=0,j=0;i<loop;i++)
                {
                        randomSort(k);
                        if(isSeriesOfLength(k))
                                j++;
                }
                return (double)j/loop;
        }
        public static double lnGamma(double n)
        {
                return 0.5*Math.log(2*Math.PI*n)+n*(Math.log(n)-1)+1.0/12/n;
        }
        public static void main(String[] args)
        {
                SeriesTest st;
                int n=1138,k=514,r=14;
                long t1,t2;
                int loop=1<<18;
                double p,p1,p2;
                st=new SeriesTest(n,k,r);
                t1=System.nanoTime();
                p=st.pr(loop);
                t2=System.nanoTime();
                System.out.printf("time=%.9f seconds\nTest Pr=%f%%\n",(t2-t1)/1e9,p1=p*100);
                System.out.printf("Real Pr=%f%%\n",p2=62500*Math.exp(lnGamma(k)+lnGamma(n-r)-lnGamma(n)-lnGamma(k-r)));
                System.out.printf("Error of Pr=%f%%\n",p2-p1);
        }
}


运行结果:
time=29.041681275 seconds
Test Pr=0.827408%
Real Pr=0.833043%
Error of Pr=0.005636%

wiley

记号码总数为n,从中任取k个,连续号码不小于r个的概率是
$p={(n-r+1)*C(n-r,k-r)}/{C(n,k)}$
sir_chen 发表于 2009-10-2 15:09

这个有重复的, 不过是个很好的上限.  正确的答案可以参考: #16 或者 #53

给一个母函数的解法.  从n个号码取k个, 不存在r个或r个以上连续号码 [即连续号码至多是r-1个] 的选择的总数是将

$(1+x+x^2+...+x^{r-1})^{n-k+1}=(1-x^r)^{n-k+1}(1-x)^{-(n-k+1)}$

展开后, $x^k$ 这项的系数:

$N(n,k,r)=sum_{i=0}^{|__k/r__|} (-1)^i\ C_{n-k+1}^i\ C_{n-k+k-ri}^{k-ri}$

所以从n个号码中取k个,连续号码不小于r个的概率是 $1-{N(n,k,r)}/C_n^k$. 代入$n=1138,\ k=514,\ r=14$ 即可.

不需要递推, 用Mathematica是很快的(计算二项式系数).

liupinghaiyan

7# mathe


正解

liupinghaiyan

7# mathe


正解

Buffalo

0.00830260841825337.....