我写了一个很简单很粗糙的大数库，用shshsh_0510的方法计算大概需要55秒钟。
不过如果完全按照他的算法，要占差不多1G内存。简化的算法占差不多50M内存。
再简化一下运算时间可以控制在40秒以内。
53# halfcard
这种方法最好，3秒搞定。
记号码总数为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
通过程序模拟也可以得到相同的结果,以下是用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;
C=new int;
for(i=0;i<n;i++)
a=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;
a=a;
a=temp;
}
}
public void randomSort(int k)
{
int i,j,temp;
for(i=0;i<k;i++)
{
j=random(i,n-1);
temp=a;
a=a;
a=temp;
}
}
public void countSort(int k)
{
int i,j;
for(i=0;i<n;i++)
C=0;
for(i=0;i<k;i++)
C]=1;
for(i=0,j=0;j<k;i++)
if(C!=0)
a=i;
}
public boolean isSeriesOfLength(int k)
{
int i;
countSort(k);
for(i=r-1;i<k;i++)
if(a-a==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%
记号码总数为n,从中任取k个,连续号码不小于r个的概率是
p={(n-r+1)*C(n-r,k-r)}/{C(n,k)}
sir_chen 发表于 2009-10-2 15:09 http://bbs.emath.ac.cn/images/common/back.gif
这个有重复的, 不过是个很好的上限.正确的答案可以参考: #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是很快的(计算二项式系数).
7# mathe
正解
7# mathe
正解
0.00830260841825337.....