求N!的位数 三种不同方法

本文主要是介绍求N!的位数 三种不同方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

    N！阶乘是一个非常大的数，大家都知道计算公式是N!=N*(N-1）······*2*1.现在你的任务是计算出N！的位数有多少（十进制）？

输入

首行输入n，表示有多少组测试数据(n<10)
随后n行每行输入一组测试数据 N( 0 < N < 1000000 )

输出

对于每个数N，输出N!的（十进制）位数。

样例输入

3
1
3
32000

样例输出

1
1
130271

这个题有三种解法：

一、对数的方法：

   可设想n!的结果是不大于10的M次幂的数,即n!<=10^M(10的M次方),则不小于M的最小整数就是 n!的位数，对 该式两边取对数，有 M =log10^n! 即：M = log10^1+log10^2+log10^3...+log10^n 循环求和,就能算得M值，该M是n!的精确位数。当n比较大的时候，这种方法方法需要花费很多的时间。

#include<stdio.h>   
#include<math.h>   
int main()  
{  int i,j,k;  double sum;  int  n,N;  scanf("%d",&n);  while(n--)  {  sum=0;  scanf("%d",&N);  for(j=1;j<=N;j++)  sum+=log10(j);  k=(int)sum+1;  printf("%d\n",k);  }  return 0;  
}         

二、其实主要思想还是上边说的方法，只不过这里自己做了一个log函数，相当于库函数。
位数=1+  取整log10 ^N。
#include<iostream>
using namespace std;
int digitnum;
double t;
void turn(double &); 
int main()
{int N;cin>>N;for(int i=0;i<N;i++){int n;cin>>n;t=1.0;digitnum=0;for(int j=0;j<n;j++){t*=(n-j);// cout << 'j' << j << 't' << t << endl;if(t>=10)turn(t);}digitnum++;cout<<digitnum<<endl;}
}	

三、斯特林公式：

log(n!) = log10(sqrt(2*pi*n)) + n*log10(n/e);

其中pi是圆周率，e是自然对数。

1时 要特殊处理：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define e 2.718281828459045
#define pi 3.141592653589793239
using namespace std;
int main ()
{int cas,n;scanf("%d",&cas);while (cas --){scanf("%d",&n);double t = log10(sqrt(2*pi*n)) + n * log10(n/e);printf ("%d\n",(int)t + 1);}
return 0;
}

这篇关于求N!的位数 三种不同方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---