n!的位数
Time Limit:2000MS Memory Limit:65536K
Description:
针对每个非负整数n，计算其n!的位数。
Input:
输入数据中含有一些整数n（0≤n＜10^7）。
Output:
根据每个整数n，输出其n!的位数，每个数占独立一行。
Sample Input:
5
6
Sample Output:
3
3
源码：
#include<iostream>
#include<cmath>
using namespace std;
/**
一
针对每个非负整数n，计算其n!的位数,由于n的位数很大，我们不可能通过直接计算得到结果
1.设a=log10（n！） ，则n！=10^a,其中a是一个小数
2.设a=x+y，其中 x为整数，y为小数
3.因此 n！=10^x+10^y
4.10^x肯定为10的倍数,决定了n!的位数，10^y为（1～10，不取10），决定n！的各位数字
5.因此，只要知道了a就可以求出n!的位数
6.因为a= log10（n！）=log10(n)+ log10(n-1)+……log10(2)+log10(1)，所以a的值可以很容易求出
二
普通计算时：
N！=1*2*3*4*5*............*N；
如果要计算N！后得到的数字，则我们可以知道其等于lgN！+1
lgN！=lg1+lg2+lg3+lg4+lg5+....................+lgN;
但是当N很大的时候，我们可以通过数学公式进行优化：（即Stirling公式）
N！=sqrt（2*pi*N）*（N/e）^N；（pi=3.1415926=acos（-1.0），e=2.718）
lgN！=(lg(2*pi)+lgN)/2+N*(lgN-lge);
斯特林公式可以用来估算某数的大小结合lg可以估算某数的位数，或者可以估算某数的阶乘是另一个数的倍数。
**/
const double pi= M_PI;
const double e=M_E;
double counta(int n){
if(n==0) return 0;
double a=0;
a= (log10(2*pi)+log10(n))/2+n*(log10(n)-log10(e));
return a;
}
int main() {
int n,x,y;
double a;
while(cin>>n){
a=counta(n);
x=(int)a;
y=a-x;
cout<<x+1<<endl;
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
