精华内容
下载资源
问答
  • Stirling公式的应用
    2020-02-21 15:03:43

    Stirling公式也叫做斯特林公式,是用来取N! 的近似值。
    在编程中,也用到了Stirling数的思想来解决以下问题。

    第一类Stirling公式

    题目

    把n个物体排成k个非空循环的方法数目。
    S(n,0)=0(n>=1)

    n个物体不可能不形成环,因为一个物体就能形成环

    S(1,1)=1(n>=1)

    一个物体能形成一个环

    S[i][j]=S(i-1,j-1)+(i-1)S(i-1,j) (1<=j<=i<=n)

    具体看例子

    对于第一类stirling公式递推关系的理解
    第n个物体单独占一个环时其他元素的情况:S(n-1,k-1);第n个物体加入其他环时的情况,(n-1)S(n-1,k),这个物体可以加到第i个物体的左边,所以有n-1种可能。

    代码(递归算法)

    #include<stdio.h>
    long long arr[25][25];
    long long Stirling1(int n,int k)
    {
    	if(k==0 || k>n)
    		return 0;
    	if(n==1 && k==1)
    		return 1;
    	return Stirling1(n-1,k-1)+(n-1)*Stirling1(n-1,k);
    }
    int main()
    {
    	int n,k;
    	scanf("%d%d",&n,&k);
    	long long ans=Stirling1(n,k);
    	printf("%lld",ans);
    	return 0;
    } 
    

    代码(非递归算法)

    #include<stdio.h>
    long long S[25][25];
    int main()
    {
    	int n,k;
    	scanf("%d%d",&n,&k);
    	S[1][1]=1;
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    			S[i][j]=S[i-1][j-1]+(i-1)*S[i-1][j];
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(j<n)	printf("%lld ",S[i][j]);
    			else	printf("%lld\n",S[i][j]);
    		}
    	}
    	printf("%lld",S[n][k]);
    	return 0;
    }
    

    第二类Stirling公式

    题目

    把n个苹果放入m个相同的盘子中,不允许盘子为空,请问总共有多少种方法?
    S(n,k)=0 (k>n or k=0)

    可以想到,将10个苹果放入100个盘是不现实的(k>n),没有盘子也是不现实的(k=0)

    S(n,1)=S(n,n)=1

    将所有苹果放入一个盘子只有一种情况(k=1),将2个苹果放入2个盘子只有一种情况(n=k)

    S(n,k)=S(n-1,k-1)+kS(n-1,k)

    这个递推方程下面有解释。

    对于第二类stirling公式递推关系的理解:
    第n个元素单独占一个子集时其他元素的情况:S(n-1,k-1);第n个元素和其他元素呆在同一个子集时有kS(n-1,k)种情况。所以结果就是S(n-1,k-1)+kS(n-1,k)

    举个例子来说,当n=4,m=3时,S(4,3)=?。
    根据Stirling数公式得S(4,3)=S(3,2)+3*S(3,3)。
    (1).分析拿3个苹果放到2个盘子的可能,
    {1,{2,3}}————{1,{2,3},4}在将苹果4放入一个盘中
    {{1,3},2}————{{1,3},2,4}在将苹果4放入一个盘中
    {{1,2},3}————{{1,2},3,4}在将苹果4放入一个盘中

    (2).分析拿3个苹果放入3个盘子的可能,
    {1,2,3}————{{1,4},2,3}现在是三个盘子都装满,还有一个苹果放入三个盘中的情况
    ————{1,{2,4},3}
    ————{1,2,{3,4}}
    注意:这里是用Stirling数来模拟N!算法,当然数字不能超过25,如果超过25,题目都会说要对结果进行取模处理

    代码(分治递归法)

    #include<stdio.h>
    long long Stirling(int n,int m)
    {
    	if(m==0 || n<m)//不符合题意 
    		return 0;
    	if(m==1 || n==m)//只有一种方法.
    		return 1;
    	return Stirling(n-1,m-1)+m*Stirling(n-1,m); //递归分治 
    }
    int main()
    {
    	int n,m;//n表示苹果数,m表示盘子数。 
    	scanf("%d%d",&n,&m);
    	long long ans=Stirling(n,m);
    	printf("%lld",ans);
    	return 0;
    }
     
    

    时间复杂度为2的n次方

    代码(空间换时间的算法)

    #include<stdio.h>
    long long s[50][50];//表示s[n][m] 
    int main()
    {
    	int n,m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    	{
    		s[i][1]=1;
    		s[i][i]=1;
    		for(int j=1;j<i;j++)
    			s[i][j]=s[i-1][j-1]+(long long)j*s[i-1][j];//这里的n不能超过25,由于这里算的是一个组合 
    	}
    	printf("%lld\n",s[n][m]);
    	return 0;
    } 
    

    时间复杂度为n²

    更多相关内容
  • Stirling公式

    千次阅读 2019-01-21 22:43:38
    Stirling 公式 1.阶乘 ...=n(n−1)(n−2)⋯×3×2×1(n≥1) n! = n(n-1)(n-2)\cdots\times3\times2\times1\quad(n\geq1)n!...Stirling公式 n!≈2πn(ne)n n! \approx \sqrt{2\pi n}(\fr...

    Stirling 公式


    Stirling公式

    • 1.阶乘

      n ! = n ( n − 1 ) ( n − 2 ) ⋯ × 3 × 2 × 1 ( n ≥ 1 ) n! = n(n-1)(n-2)\cdots\times3\times2\times1\quad(n\geq1) n!=n(n1)(n2)×3×2×1(n1) 0 ! = 1 0!= 1 0=1

    • Stirling公式

      n ! ≈ 2 π n ( n e ) n n! \approx \sqrt{2\pi n}(\frac{n}{e})^n n!2πn (en)n

      当n足够大的时候,n!的计算量很大,Stirling公式这个时候就很好用,公式也可以变形为

      lim ⁡ n   + ∞ n ! 2 π n ( n e ) n = 1 \lim_{n \ +\infty} \frac{n!}{\sqrt{2\pi n}(\frac{n}{e})^n}=1 n +lim2πn (en)nn!=1

      或者也等价于

      lim ⁡ n   + ∞ e n n ! n n n = 2 π \lim_{n \ +\infty}\frac{e^nn!}{n^n\sqrt{n}}=\sqrt{2\pi} n +limnnn enn!=2π

      在Wikipedia上看到,Stirling公式是由 A b r r ′ m a h a m d e M o i v r e {\rm Abrr&#x27;maham de Moivre} AbrrmahamdeMoivre发现的,不过没有那么精确

      n ! = c n n + 1 2 e − n n! = cn^{n+\frac{1}{2}}e^{-n} n!=cnn+21en 其中c为常数,后来Stirling证明了 c = 2 π n c=\sqrt{2\pi n} c=2πn ,约为2.506628274631.更加精确的形式是由雅克·比内发现的。

    推导

    这个公式的误差的估计,可以推导如下。首先不直接估计 n ! n! n!,而是考虑它的自然对数:

    l n ( n ! ) = l n 1 + l n 2 + l n 3 + ⋯ + l n n . \mathsf {ln}(n!) = \mathsf {ln}1+\mathsf {ln}2+\mathsf {ln}3+\cdots+\mathsf {ln}n. ln(n!)=ln1+ln2+ln3++lnn.

    即:

    l n ( n ! ) − 1 2 l n n = l n 1 + l n 2 + ⋯ + l n n − 1 2 l n n l n \mathsf {ln}(n!)-\frac{1}{2}\mathsf {ln}n=\mathsf {ln}1+\mathsf {ln}2+\cdots+lnn-\frac{1}{2}\mathsf {ln}n \mathsf {ln} ln(n!)21lnn=ln1+ln2++lnn21lnnln

    这个方程的右边是积分 ∫ 1 n l n ( x ) d x = n l n n − n + 1 \int_1^n\mathsf {ln}(x)dx=n\mathsf {ln}n-n+1 1nln(x)dx=nlnnn+1的近似值(利用梯形法则),而他的误差由欧拉-麦克劳林公式给出:

    l n ( n ! ) − l n n 2 = l n 1 + l n 2 + l n 3 ⋯ + l n ( n − 1 ) + l n n 2 = n l n n − n + 1 + ∑ k = 2 m B k ( − 1 ) k k ( k − 1 ) ( 1 n k − 1 − 1 ) + R m , n \mathsf {ln}(n!)-\frac{\mathsf {ln}n}{2}=\mathsf {ln}1+\mathsf {ln}2+\mathsf {ln}3\cdots+\mathsf {ln}(n-1)+\frac{\mathsf {ln}n}{2}=n\mathsf {ln}n-n+1+\sum_{k=2}^m\frac{B_k(-1)^k}{k(k-1)}(\frac{1}{n^{k-1}}-1)+R_{m,n} ln(n!)2lnn=ln1+ln2+ln3+ln(n1)+2lnn=nlnnn+1+k=2mk(k1)Bk(1)k(nk111)+Rm,n

    其中 B k B_k Bk是伯努利数, R m , n R_{m,n} Rm,n是欧拉麦克劳林中的余项。取极限,可得:

    lim ⁡ n → ∞ ( l n n ! − n l n n + n − l n n 2 ) = 1 − ∑ k = 2 m B k ( − 1 ) k k ( k − 1 ) + lim ⁡ n → ∞ R m , n . \lim_{n\to\infty} (\mathsf {ln}n!-n\mathsf {ln}n+n-\frac{\mathsf {ln}n}{2})=1-\sum_{k=2}^m\frac{B_k(-1)^k}{k(k-1)}+\lim_{n\to \infty} R_{m,n}. nlim(lnn!nlnn+n2lnn)=1k=2mk(k1)Bk(1)k+nlimRm,n.

    把这个极限记为 y \mathsf y y .由于欧拉-麦克劳林公式中的余项 R m , n R_{m,n} Rm,n满足:

    R m , n = lim ⁡ n → ∞ + O ( 1 n 2 m − 1 ) R_{m,n} = \lim_{n\to \infty}+\Omicron(\frac{1}{n^{2m-1}}) Rm,n=nlim+O(n2m11)

    其中用到了大 O \Omicron O符号,与以上的方程结合,便得出对数形式的近似公式:

    l n n ! = n l n ( n e ) + l n n 2 + y + ∑ k = 2 m B k ( − 1 ) k k ( k − 1 ) n k − 1 + O ( 1 n 2 m − 1 ) \mathsf {ln}n! = n\mathsf {ln}(\frac{n}{e})+\frac{\mathsf {ln}n}{2}+y+\sum_{k=2}^m\frac{B_k(-1)^k}{k(k-1)n^{k-1}}+\Omicron(\frac{1}{n^{2m-1}}) lnn!=nln(en)+2lnn+y+k=2mk(k1)nk1Bk(1)k+O(n2m11)

    两边取质数,并选择任何正整数 m m m,便得到了一个含有未知数 e y e^y ey的公式。当 m = 1 m=1 m=1时,公式为:

    n ! = e y n ( n e ) n [ 1 + O ( 1 n ) ] n!=e^y\sqrt n(\frac{n}{e})^n[1+\Omicron(\frac1n)] n!=eyn (en)n[1+O(n1)]

    这个上述表达式带入沃利斯乘积公式,并令 n n n趋于无穷,便可以得出

    e y ( e y = 2 π ) e ^y(e^y=\sqrt {2\pi}) ey(ey=2π )

    因此,我们便得出斯特林公式:

    n ! = 2 π n ( n e ) n [ 1 + O ( 1 n ) ] n!=\sqrt {2\pi n}(\frac ne)^n[1+\Omicron(\frac 1n)] n!=2πn (en)n[1+O(n1)]

    这个公式也可以反复使用分部积分法来得出,首相可以通过最速下降法得到。把以下的和:

    l n ( n ! ) = ∑ j = 1 n l n j \mathsf {ln}(n!)=\sum_{j=1}^n\mathsf {ln}j ln(n!)=j=1nlnj

    用积分近似代替,可以得出不含 2 π n \sqrt {2\pi n} 2πn 的因子的Stirling公式(这个因子通常在实际应用中无关):

    ∑ j = 1 n l n j ≈ ∫ 1 n l n x d x = n l n n − n + 1 \sum_{j=1}^n\mathsf {ln}j\approx \int_1^n\mathsf {ln}xdx=n\mathsf {ln}n-n+1 j=1nlnj1nlnxdx=nlnnn+1

    收敛速率和误差分析

    更加精确的近似公式为:

    n ! = 2 π n ( n e ) n e λ n n!=\sqrt{2\pi n}(\frac ne)^ne^{\lambda_n} n!=2πn (en)neλn

    其中:

    1 12 n + 1 &lt; λ n &lt; 1 12 n \frac1{12n+1}&lt;\lambda_n&lt;\frac 1{12n} 12n+11<λn<12n1

    Stirling公式实际上是一下级数(现在成为Stirling级数)的第一个近似值:

    n ! = 2 π n ( n e ) n ( 1 + 1 288 n 2 − 139 51840 n 3 − 517 2488320 n 4 + ⋯ &ThinSpace; ) n!=\sqrt{2\pi n}(\frac ne)^n(1+\frac 1{288n^2}-\frac {139}{51840n^3}-\frac{517}{2488320n^4}+\cdots) n!=2πn (en)n(1+288n2151840n31392488320n4517+)

    n → ∞ n \to \infty n时,截断级数的误差等于第一个省略掉的项。这是渐进展开式的一个例子。他不是一个收敛级数,对于任何特殊值n,级数的准确性只在取有限个项时达到最大,如果取更多的项,则准确性将变得越来越差。
    阶乘的对数的渐近展开式也称为Stirling级数:

    l n n ! = n l n n − n + 1 2 l n ( 2 π n ) + 1 12 n − 1 360 n 3 + 1 1260 n 5 − 1 1680 n 7 + ⋯ \mathsf {ln}n!=n\mathsf {ln}n-n+\frac 12 \mathsf {ln}(2\pi n)+\frac 1{12n}-\frac 1{360n^3}+\frac 1{1260n^5}-\frac 1{1680n^7}+\cdots lnn!=nlnnn+21ln(2πn)+12n1360n31+1260n511680n71+

    这种情况下,级数的误差总是与第一个省略掉的异号,且最多同大小。

    Gamma函数的Stirling公式

    对于所有正整数,有:

    n ! = Π ( n ) = Γ ( n + 1 ) . n!= \Pi (n)=\Gamma(n+1). n!=Π(n)=Γ(n+1).

    然而,Gamma函数与阶乘不一样,他对于所有复数都有定义。尽管如此,Stirling公式仍然适用。如果 R ( z ) &gt; 0 R(z)&gt;0 R(z)>0,那么:

    l n Γ ( z ) = ( z − 1 2 ) l n z − z + l n 2 π 2 + 2 ∫ o ∞ a r c t a n t 2 e 2 π t − 1 d t \mathsf {ln}\Gamma(z)=(z-\frac 12)\mathsf {ln}z-z+\frac{\mathsf {ln}2\pi}2+2\int_o^\infty\frac{arctan\frac t2}{e^{2\pi t}-1}dt lnΓ(z)=(z21)lnzz+2ln2π+2oe2πt1arctan2tdt

    反复使用分部积分法,可得一下渐近展开式:

    l n Γ ( z ) = ( z − 1 2 ) l n z − z + l n 2 π 2 + ∑ n = 1 ∞ ( − 1 ) n − 1 B n 2 n ( 2 n − 1 ) z 2 n − 1 \mathsf {ln}\Gamma (z)=(z-\frac 12)\mathsf {ln}z-z+\frac {\mathsf {ln} 2\pi}2 +\sum_{n=1}^\infty\frac{(-1)^{n-1}B_n}{2n(2n-1)z^{2n-1}} lnΓ(z)=(z21)lnzz+2ln2π+n=12n(2n1)z2n1(1)n1Bn

    其中 B n B_n Bn是第n个伯努利数。当 ∣ a r g z ∣ &lt; π − ϵ |arg z|&lt;\pi-\epsilon argz<πϵ,其中 ϵ \epsilon ϵ 是正数时,这个公式对于绝对值足够大的 z z z是适用的,当使用了最初 m m m个项时,误差为 O ( z − m − 1 2 ) \Omicron(z^{-m-\frac 12}) O(zm21)。对应的近似值可以写为:

    Γ ( z ) = 2 π z ( z e ) z [ 1 + O ( 1 z ) ] \Gamma (z)=\sqrt{\frac {2\pi}{z}}(\frac ze)^z[1+\Omicron(\frac 1z)] Γ(z)=z2π (ez)z[1+O(z1)]

    Stirling公式的收敛公式

    欲得出Stirling公式的一个收敛形式,我们必须计算:

    ∫ 0 ∞ 2 a r c t a n t 2 e 2 π t − 1 d t = l n Γ ( z ) − ( z − 1 2 ) l n z + z − 1 2 l n ( 2 π ) \int_0^\infty \frac {2arctan\frac t2 }{e^{2\pi t}-1}dt=\mathsf {ln}\Gamma(z)-(z-\frac 12)\mathsf {ln}z+z-\frac 12 \mathsf {ln}(2\pi) 0e2πt12arctan2tdt=lnΓ(z)(z21)lnz+z21ln(2π)

    一种方法是利用含有上升阶乘幂的级数。如果

    z n ‾ = z ( z + 1 ) ⋯ ( z + n − 1 ) z^{\overline n}=z(z+1)\cdots(z+n-1) zn=z(z+1)(z+n1)

    那么:

    ∫ 0 ∞ 2 a r c t a n t 2 e 2 π t − 1 d t = ∑ n = 1 ∞ c n ( z + 1 ) n ‾ \int_0^\infty \frac {2arctan\frac t2 }{e^{2\pi t}-1}dt=\sum_{n=1}^\infty \frac {c_n}{(z+1)^{\overline n}} 0e2πt12arctan2tdt=n=1(z+1)ncn

    其中:

    c n = 1 n ∫ 0 1 x n ‾ ( x − 1 2 ) d x c_n=\frac 1n\int_0^1x^{\overline n}(x-\frac 12)dx cn=n101xn(x21)dx

    从中可以得出Stirling级数的一个收敛形式:

    l n Γ ( z ) = ( z − 1 2 ) l n z − z + l n 2 π 2 + 1 12 ( z + 1 ) + 1 12 ( z + 1 ) ( z + 2 ) + 59 360 ( z + 1 ) ( z + 2 ) ( z + 3 ) + 29 60 ( z + 1 ) ( z + 2 ) ( z + 3 ) ( z + 4 ) + ⋯ \mathsf {ln}\Gamma(z)=(z-\frac 12)\mathsf {ln}z-z+\frac {\mathsf {ln}2\pi}{2}+\frac 1{12(z+1)}+\frac 1{12(z+1)(z+2)}+\frac{59}{360(z+1)(z+2)(z+3)}+\frac {29}{60(z+1)(z+2)(z+3)(z+4)}+\cdots lnΓ(z)=(z21)lnzz+2ln2π+12(z+1)1+12(z+1)(z+2)1+360(z+1)(z+2)(z+3)59+60(z+1)(z+2)(z+3)(z+4)29+
    他在R(z)>0时收敛

    适用于计算器的形式

    以下的近似值

    Γ ≈ 2 π z ( z e z s i n h 1 z + 1 810 z 6 ) z \Gamma\approx\sqrt{\frac{2\pi}{z}}(\frac ze\sqrt{zsinh\frac1z+\frac 1{810z^6}})^z Γz2π (ezzsinhz1+810z61 )z

    或:

    2 l n Γ ( z ) ≈ l n ( 2 π ) − l n z + z [ 2 l n z + l n ( z s i n h 1 z + 1 810 z 6 ) − 2 ] 2\mathsf {ln}\Gamma(z)\approx\mathsf {ln}(2\pi)-\mathsf {ln}z+z[2\mathsf {ln}z+\mathsf {ln}(zsinh\frac 1z+\frac 1{810z^6})-2] 2lnΓ(z)ln(2π)lnz+z[2lnz+ln(zsinhz1+810z61)2]

    可以通过把Stirling公式整理,并注意到它的幂级数与双曲正弦函数的泰勒级数展开式的相似性来得出。当 z z z的实数部分大于8时,这个近似值精确到小数点后8位。2002年,Robert H. Windschitl建议计算 Γ ( z ) \Gamma(z) Γ(z)函数Gergo Nemes在2007年提出了一个近似公式,它的精确度与Windschitl的公式相等,但更加简单:

    Γ ( z ) ≈ 2 π z [ 1 e ( z + 1 12 z − 1 10 z ) ] z \Gamma (z)\approx \sqrt{\frac {2\pi}{z}}[\frac 1e(z+\frac 1{12z-\frac 1{10z}})]^z Γ(z)z2π [e1(z+12z10z11)]z

    或:

    l n Γ ( z ) ≈ 1 2 [ l n ( 2 π ) − l n z ] + z [ l n ( z + + 1 12 z − 1 10 z ) − 1 ] \mathsf {ln}\Gamma (z)\approx\frac 12 [\mathsf {ln}(2\pi)-\mathsf {ln}z]+z[\mathsf {ln}(z++\frac 1{12z-\frac 1{10z}})-1] lnΓ(z)21[ln(2π)lnz]+z[ln(z++12z10z11)1]

    这个到后面全部都是Wikipedia上抄的了,因为不知道怎么总结了,就选择直接把他手打了一份,就当练习Markdown编辑器了,立个flag,把这里面的一些 名词都手打一遍,看一遍。今天就这样了吧,有点醉or β \beta β

    展开全文
  • 斯特灵公式是一条用来取n阶乘近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特灵公式十分好用。从图中可以看出,即使在n很小的时候,斯特灵公式的取值已经十分准确。 公式为: 从图...

    斯特灵公式是一条用来取n阶乘近似值数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特灵公式十分好用。从图中可以看出,即使在n很小的时候,斯特灵公式的取值已经十分准确。

                 

    公式为:   n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}.

     从图中看出,对于足够大的整数n,这两个数互为近似值。更加精确地:   

    \lim_{n \rightarrow \infty} {\frac{e^n\, n!}{n^n \sqrt{n}}} = \sqrt{2 \pi}.       或者        \lim_{n \rightarrow \infty} {\frac{n!}{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}} = 1

    这个公式,以及误差的估计,可以推导如下。我们不直接估计n!,而是考虑它的自然对数

       \ln(n!) = \ln 1 + \ln 2 + \cdots + \ln n.

    按一般方法计算N的阶乘,其时间复杂度为O(N):    N!= 1 * 2 * 3 * 4 * 5 * ............ * N;

    如果要计算N后得到的数字为几位数,则我们可以知道其位数等于lgN!+1;

    则: \ln(n!) = \ln 1 + \ln 2 + \cdots + \ln n.

    但是当N很大的时候,我们可以通过斯特林公式进行优化:(即Stirling公式)

    n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}.(e = 2.718)

    斯特林公式可以用来估算某数的大小,结合lg可以估算某数的位数,或者可以估算某数的阶乘是另一个数的倍数。

     

    例题:  http://acm.hdu.edu.cn/showproblem.php?pid=1018

    题目给出的N的范围是: 1<= N <= 107  

    用普通方法肯定算不出N的阶乘后的出的数字位数,但运用斯特林公式则很好解决.

    Stirling 公式

            

    即:

                 

        Stirling公式的意义在于:当n足够大时,n!计算起来十分困难,虽然有很多关于n!的等式,但并不能很好地对阶乘结果进行估计,尤其是n很大之后,误差将会非常大。但利用Stirling公式可以将阶乘转化成幂函数,使得阶乘的结果得以更好的估计。而且n越大,估计得越准确。

    利用Stirling公式求解n!的位数:易知整数n的位数为[lgn]+1。利用Stirling公式计算n!结果的位数时,可以两边取对数,得:

     

    故n!的位数为:

    展开全文
  • 斯特林公式 (Stirling公式

    千次阅读 2018-08-19 22:51:35
    斯特林公式是一条用来求n的阶乘的近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,...易知整数n的位数为[lgn]+1,因此对Stirling公式两边取10的对数得 为此N!的位数为 C语言代码实现 //运...

    斯特林公式是一条用来求n的阶乘的近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特林公式十分好用,而且,即使在n很小的时候,斯特林公式的取值已经十分准确。

    数学表达式:

    https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D112/sign=4aec460be7cd7b89ed6c3e823d264291/4bed2e738bd4b31c19ead27a86d6277f9f2ff819.jpg

    或更精确的

    https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D149/sign=61f142202e2eb938e86d7ef6ec6385fe/9d82d158ccbf6c81b51c6d29bd3eb13532fa40c3.jpg

    https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D128/sign=b9538622562c11dfdad1bb215b266255/500fd9f9d72a6059fea7a0db2934349b023bbab8.jpg

    作用:当N较大时计算N!的位数

    易知整数n的位数为[lgn]+1,因此对Stirling公式两边取10的对数得

    为此N!的位数为

    C语言代码实现

    //运用换底公式
    
    res=(long long)((0.5*log(2*PI*n)+n*log(n)-n)/log(10))+1;
    
    //注:C语言中函数log10()  log()分别是以10和e为底 

     

    展开全文
  • 本文证明了有关记的一个便于应用的双边不等式,它对一切自然数都成立,且当n变大时,上界不等式能给出误差界为O(IL)的Stirling渐近公式,从一定意义上说,文中的上界不等式具有最优形式,因为其中的常数0.5已作了最佳选择...
  • 普通计算时: N!=1*2*3*4*5*............*N; 如果要计算N!后得到的数字,则我们可以知道...但是当N很大的时候,我们可以通过数学公式进行优化:(即Stirling公式) N!=sqrt(2*pi*N)*(N/e)^N;(pi=3.141...
  • 如图,题目出处51nod,... 自然数n的位数为1+lg n舍去小数所得结果(以1234为例,lg 1234=3,1+3=4,4即是位数,其它类比),所以n!的位数为1+lg n! 对于lg n!有: ...=lg1+lg2+lg3+……+l...
  • 一、定义 斯特林公式(Stirling’s approximation)是一条用来取n的阶乘的近似值的数学公式。...Stirling公式.: n!≈sqrt(2∗pi∗n)∗[(n/e)n]n!≈sqrt(2*pi*n)*[(n/e)^n]n!≈sqrt(2∗pi∗n)∗[...
  • 斯特灵公式是一条用来取n阶乘近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特灵公式十分好用。从图中可以看出,即使在n很小的时候,斯特灵公式的取值已经十分准确。  ...
  • 第一类斯特林数可以处理下面的问题:把N个不同元素分为k个环,每个环非空,问有多少分法,记为S(p,k),S(p,p)=1S(p,0)=0递推公式为:S(p,k)=(p-1)*S(p-1,k)+S(p-1.k-1)。p个人排k个圈,第一种方法是,第k个圈只有...
  • 复习高等数学时候又遇到了sin(x)的高次幂问题,上网搜查偶然的机会遇到了Wallis公式,又由此见到了Stirling公式。 原链接在此 Wallis公式 Stirling公式 */ Wallis公式以及Stirling公式在程序中的应用 Wallis...
  • Stirling 公式 ...但利用Stirling公式可以将阶乘转化成幂函数,使得阶乘的结果得以更好的估计。而且n越大,估计得越准确。 利用Stirling公式求解n!的位数:易知整数n的位数为[lgn]+1。利用St...
  • 输入N求N的阶乘的10进制表示的长度。...= 10^6)Output输出N的阶乘的长度Input示例6Output示例3 公式 log10(sqrt(2*acos(-1.0)*n))+n*(log10(n/exp(1.0)))+1 注意精度 或者 π和e acos(-1.0)和exp(1.0) 注意当n=...
  • 斯特灵公式是一条用来取n阶乘近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特灵公式十分好用。从图中可以看出,即使在n很小的时候,斯特灵公式的取值已经十分准确。   公式为:   从...
  • Stirling公式的应用

    2017-03-29 10:25:18
    使用Stirling公式进行求解 n!~~~~~~(n/e)^n(2*pi*n)^(1/2) */ #include #include using namespace std; const double e=2.7182818284590452354,pi=3.141592653589793239; double str_ling(int n)
  • Wallis公式&Stirling公式

    2021-03-06 11:15:34
    Wallis公式&Stirling公式
  • 本文用简易的分析工具,对n!给出了一个精确等式,从而导出Stirling渐近公式(2)的一个新的简短证明。
  • Stirling公式:n!与sqrt(2πn) * n^n * e^(-n)的值十分接近 所以log10(n!) = log(n!) / log(10) = ( n*log(n) - n + 0.5*log(2*π*n))/log(n); 代码: #include #include #include #include #include #...
  • Stirling公式(pku1423)

    2015-06-23 21:31:05
     Stirling公式的意义在于:当n足够大时,n!计算起来十分困难,虽然有很多关于n!的等式,但并不能很好地对阶乘结果进行估计,尤其是n很大之后,误差将会非常大。但利用Stirling公式可以将阶乘转化成幂函数,使得阶乘...
  • #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define Maxn #define MOD typedef long long ll;...#define FOR(i,j,n) for
  • Stirling(斯特林)公式

    千次阅读 2018-06-11 21:56:12
    斯特林公式Stirling's approximation)是一条用来取n的阶乘的近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特林公式十分好用,而且,即使在n很小的时候,斯特林公式的取值已经十分准确...
  • 上次写题用到了斯特灵公式,然后就被老师喷了 …\dots… (高等数学真的烦,这也不讲那也不讲 …\dots… ) u1s1活该被喷,虽然斯特灵公式我一直在用,但是从来没有证过 为了以后更有底气使用斯特灵公式,这里简单写...
  •  Stirling公式的意义在于:当n足够大之后n!计算起来十分困难,虽然有很多关于n!的不等式,但并不能很好的对阶乘结果进行估计,尤其是n很大之后,误差将会非常大.但利用Stirling公式可以将阶乘转化成幂函数,使得阶乘的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,742
精华内容 696
关键字:

stirling公式

友情链接: chyu.zip