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(使用前将#替换为@)