求大数阶乘的位数

2022-09-10 16:08:48 文档大全网 [ 字体：小中大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《求大数阶乘的位数》，欢迎阅读！
阶乘,大数,位数
如何求阶乘的位数

一般有三种方法：

1. log10(1)+log10(2)+···+long10(n)取整后加1

这个是我做的AC过的。

2. #include 3. #include 4. int main(){ 5. intN,j = 1;

6. intnumber,temp = 0;

7. long double member = 0; 8. scanf("%d",&N); 9. while(N> 0){ 10. N--;

11. scanf("%d",&number); 12. member = 0 ;

13. for(inti = 1,temp = 0;i<= number ;i++){ 14. member += log10(i * 1.0); 15. }

16. temp = floor(member) + 1; 17. printf("%d\n",temp); 18. }

19. return 0; 20. }

2.Stirling公式

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

这就是说，对于足够大的整数n，这两个数互为近似值。更加精确地：

或

用Stirling公式计算n!结果的位数时，可以两边取对数，得： log10(n!) = log10(2*PI*n)/2+n*log10(n/E);

故n!的位数为 log10(2*PI*n)/2+n*log10(n/E)+1（注意：当n=1时，算得的结果为0）

n的位数为[lg10(n)]+1 n!的位数为

[lg10(n*(n-1)*(n-2)*…..*1)]+1=[lg10(n)+lg10(n-1)+lg10(n-2)+….+lg10(1)]+1

#include using namespace std; #include

const double PI=acos(double(-1)); const double e=exp(double(1)); int main() {

intN,num; cin>>num ; while(num--) {

cin>> N ; intlen = 0 ;

len = int((N*log(N) - N + 0.5 * log(2*N*PI) ) / log(10)) + 1; // len = int(log10(sqrt(2*PI*N))+N*log10(N/e))+1; printf("%d\n",len); }

return 0; }

3.Knuth的算法，这个见到的比较少。