用Stirling近似公式改进程序设计语言中的阶乘问题
开篇：润墨网以专业的文秘视角，为您筛选了一篇用Stirling近似公式改进程序设计语言中的阶乘问题范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:大学计算机语言教材中解决阶乘(n!)问题,都是通过循环来实现;本文提出用stirling近似公式改进传统的阶乘(n!)问题,简化了程序,加快了速度,节省了空间。
Abstract: Solving factorial Problem (n!) usually was achieved by the cyclic in university computer language textbook. Writer proposed to improve the traditional factorial (n!) Problem by Stirling approximate formula. It makes procedure simplified,speed fast, space saved. It has practical significance in the calculation and theoretical analysis.
关键词: Stirling近似公式;循环;阶乘
Key words: Stirling approximate formula;cyclic;factorial
中图分类号:TP312 文献标识码:A文章编号:1006-4311(2010)08-0011-02
0引言
大学计算机语言教材,如《C程序设计》[1,7]、《visual basic程序设计》[2],《java技术及其应用》[3],所有的n!的求解都是采用传统的方法,即,用各种循环方法来实现的[1、2、3],若n值很大时,就需要多次循环多次计算。
1采用Stirling近似公式来解决阶乘问题
组合数学中,Stirling近似公式[4,5,6]可以用一个表达式,一次就能计算出一个数的阶乘,而不需要采用循环多次计算。
Stirling近似公式为:n!~()
现将公式证明如下:
lnxdx=(xlnx-x)=nlnn-n-n+(1)
把积分区间分成以x=1、2、3、 … n为中心,长度为1的子区间,在这些区间上分别以ln1,ln2,…,lnn为高度作矩形,以这种矩形面积的综合来近似(1)式左端的积分。
令ak=(lnk-lnx)dx=lndx
bk=(lnx-lnk)dx=lndx
ak-bk=lnk-lnxdx(2)
但ak=lndxlndy
=lndt=lndt=-ln(1-)dt(3)
同理:bk=lndx=ln(1+)dt(4)
因:ln(1-)+ln(1+)=ln(1-)
ak-bk=-ln(1-)dt>0(5)
即ak>bk>0
又因在(0,)上,(-)t->0
bk-ak+1=ln(1+)dt+ln(1-)dt=ln(1+(-)t-)dt>0
故bk>ak+1
a1>b1>a2>b2>…>0(6)
根据(2)可得:
(a1-b1)+(a2-b2)+…+(an-1-bn-1)+an
=(ak-bk)+bn=ln(n!)-lnxdx+lnxdx=ln(n!)-lnxdx+lnxdx-lnn=ln(n!)-lnn-lntdt(7)
公式(7)左端是交替级数,由于(6)成立,故当n∞时:
ln(n!)-lnn-lnxdx收敛
另一方面:
ak-bk=-ln(1-)dt-ln(1+)dt=ln(1-)dt
ln(n!)-lnn-lntdt=ln(n!)-lnn-nlnn+n+lntdt
ln(n!)-lnn-nlnn+n=-lnt1-dt(8)
但t1-=sinπt
ln(n!)-lnn-nlnn+n=-lndt
=lnπ-lnsinπtdt(9)
lnsinπtdt-lncosπt′dt′=lncosπtdt
=ln2+lnsinπtdt+lncosπtdt
=ln2+2lnsinπtdt(10)
但:lnsin2πtdtlnsinπt′dt′=lnsinπtdt
代入(10)lnsinπtdt=-ln2
公式(9)便成为:ln(n!)-(n+)lnn+lnen=ln(2π)
即ln(n!)(ne=ln
n!≈() [4,5,6]
2两种方法的程序比较
用传统的方法,一个通用化的C程序如下:
main()
{int i, n;
double sum=1;
scanf(“%d”,&n);
for(i=2;i
sum=sum*i;
printf((“%d”,sum); }[1,2,3,7] }
而用Stirling近似公式,程序如下:
#definePI3.1415926
#defineE 2.71828183
#include “math.h”
main()
{floatsum;
int n;
scanf(“%d”,&n);
sum=sqrt(2*PI*n)*pow(n/E,n);
printf(“%f”, sum);}
部分实验结果如表1。
(1)采用的结构不同:当求阶乘时,传统方法采用循环结构;Stirling方法采用简单的顺序结构,也即只需要一个表达式即可。
(2)运行时间不同:传统的方法需要多次循环,多次累积,运行时间长;Stirling方法不需要循环,不需多次计算,运行时间短。
(3)使用变量数量不同:传统方法至少用3个变量,占用存储空间大;Stirling方法用两个变量,占用空间小。
(4)理解难易程度不同:传统的方法完全与阶乘的概念一至,容易理解;不了解Stirling者不易理解。
(5)程序复杂度不同:传统的方法复杂;Stirling方法简单。
(6)精确性:传统方法运行结果为精确,Stirling方法是个近似值,但随着n值的增大,逐渐趋于实际值。
3结论
从表1见,当n值较小时,误差较大,随n值的增加,误差逐渐减小,当n趋于无限大时,误差无限接近于0。因此,n值很大的情况下可以使用stirling近似公式法求解阶乘的值;在精确度要求不是很严格的情况下,可使用stirling近似公式,使求解过程快速简单。
参考文献:
[1]谭浩强.C程序设计[M].清华大学出版社,2004.3,110.
[2]沈祥玖、郑有增等.visual basic程序设计[M].中国水利水电出版社,2005.1,116.
[3]王克宏.java技术及其应用[M].高等教育出版社,2007.1,27.
[4]卢开澄.组合数学――算法与分析[M].清华大学出版社,1983.9, 48-52.
[5]Richard A.Brualdi著,冯舜玺、罗平、裴伟东译.组合数学(原书第3版)[M].机械工业出版社,2001.11,180-183.
[6]卢开澄、卢华明.组合数学(第3版)[M].清华大学出版社,2002.7,60-62.
[7]黄维通.鲁明羽.C程序设计教程[M].清华大学出版社,2005.11,47.