斯特林公式

斯特林公式

科技前沿 • 2025-02-20 09:50 • 阅读 176

大家好，我是讯享网，很高兴认识大家。

定义：

斯特林公式是用来求N的阶乘近似值的公式：
公式为：
$n!=\sqrt{2\pi n}(\frac{n}{e})^n$

公式的应用：求n！的位数
大家都知道，求一个十进制数n的位数，可以对10取对数然后加一，即：
$l o g 10 (n) + 1$
假设ans代表n！的位数，则
$ans=log10(n!)+1=log10(\sqrt{2\pi n}(\frac{n}{e})^n)+1=log10(\sqrt{2\pi n})+log10(\frac{n}{e})^n+1---(1)$
或者：
$a n s = l o g 10 (n!) + 1 = l o g 10 (1) + l o g 10 (2) + . . . . . . + l o g 10 (n - 1) + l o g 10 (n) + 1 - - - (2)$

案例：

1.求N！的位数：

在这里插入图片描述
讯享网
解题：直接运用斯特林公式(2)

#include <iostream> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long using namespace std; int main(){ 
    int m; cin>>m; double sum=0; for(int i=1;i<=m;i++){ 
    sum+=(double)log10(i);//以浮点数加  //c++支持log2(),ln()即log(),log10()  } sum+=1; cout<<(int)sum<<endl;//sum向下取整  return 0; }

讯享网

2. N!的位数（n更大，n<=10^9）

解题：直接运用斯特林公式(1）

讯享网#include <iostream> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long using namespace std; double pi=acos(-1.0); double e=exp(1.0); int main() { 
    int t; cin>>t; while(t--) { 
    ll n; cin>>n; ll len=log10(sqrt(2*pi*n))+n*log10(n/e)+1; cout<<len<<endl; } }

3.求N的阶乘的准确值

在这里插入图片描述
解题：由于n最大到10000，即使用long long也无法表示，所以计算结果需要保存在数组中。

#include <iostream> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long using namespace std; int main() { 
    int ans[50000],n;//ans数组用于存储结果  int cnt=1,carry=0,res;//cnt表示计算结果位数，carry表示进位，res中间变量  while(cin>>n) { 
    for(int i=0; i<50000; i++) ans[i]=0;//初始化赋0  ans[0]=1; for(int i=2; i<=n; i++) { 
    for(int j=0; j<cnt; j++) { 
    res=ans[j]*i+carry;//i与ans数组的每一位相乘  ans[j]=res%10;//存储个位数字  carry=res/10; } while(carry>0) { 
   //处理最高位的进位  ans[cnt++]=carry%10; carry/=10; } } for(int i=cnt-1; i>=0; i--) cout<<ans[i];//从高到低位输出  cout<<endl; } return 0; }

4.N的阶乘同余P

在这里插入图片描述
解题：每做一次乘法，将结果mod P

讯享网#include <iostream> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long using namespace std; int main(){ 
    ll N,P; cin>>N>>P; ll ans=1; for(int i=1;i<=N;i++){ 
    ans=ans*i%P; } cout<<ans<<endl; return 0; }

说明：在c++中 pi=acos(-1.0),因为 cos(pi)=-1.0,利用反三角函数,自然对数e=exp(1.0)

斯特林公式