HDOJ1018 ( Big Number )【斯特林公式---处理阶乘及阶乘位数的问题】

1：把n！写成10^m次方的形式，如果m=2，就说明是三位数。

【维基百科】

【别处摘来的】可以将n!表示成10的次幂,即n!=10^M(10的M次方，10^2是3位M+1就代表位数)则不小于M的最小整数就是    n!的位数，对该式两边取对数，有M=log10^n!即：    M = log10^1+log10^2+log10^3...+log10^n    循环求和,就能算得M值

，该M是n!的精确位数。

Problem : 1018 ( Big Number )     Judge Status : AcceptedRunId : 6013028    Language : C    Author : qq1203456195Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta 1 #include <stdio.h> 2 #include <math.h> 3 int main() 4 { 5 int n,cas,i; 6 double sum; 7 scanf("%d",&cas); 8 while (cas--) 9 { 10 scanf("%d",&n); 11 sum=1; 12 for(i=1;i<=n;i++) sum+=log10((double)i); 13 printf("%d\n",(int)sum); 14 } 15 return 0; 16 }

2：斯特林公式的应用【没用这个，代码是别人的】

由斯特林[striling]公式可得：lnN!=NlnN－N+0.5ln(2N*pi)

而N的阶乘的位数等于：log10(N!)取整后加1

log10(N!)=lnN!/ln(10) 所以len=lnN!/ln(10)+1

1 #include<iostream> 2 #include<cmath> 3 const double PI=3.14159265; 4 using namespace std; 5 int main() 6 { 7 int t,n; 8 double sum; 9 cin>>t; 10 while(t--) 11 { 12 cin>>n; 13 sum=(n*log(n) - n + 0.5*log(2*n*PI))/log(10)+1; 14 printf("%d/n",(int)sum); 15 } 16 return 0; 17 }

 

转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/28/2522786.html

相关资源：数据结构—成绩单生成器