poj1423---求一个大数的位数方法,我猜网站上统计输入字符少于多少位的那个算法

法一:对一个数求它的对数,+1取整为其位数

问题转化为int (log10(N!)+1),对数性质log10(N!)=log10(N)+log10(N-1)+...+log10(1)

/*用log10求位数*/

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

  当n偏大的时候,时间长,TLE

法二:Stirling公式

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

/*用斯特灵求位数*/

#include<stdio.h>
#include<math.h>
#define e 2.718281828459045
#define pi 3.141592653589793239
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&N);
double num_digit;
num_digit=log10(sqrt(2*pi*N)) + N*log10(N/e);
printf("%d\n",(int)num_digit+1);
}
return 0;
}

  WA两次原因:

 num_digit=log10(sqrt(2*pi*N)) + N*log10(N/e)+1;
printf("%d\n",(int)num_digit);

  当N=1,num_digit=0.几,因为当n=1时,

log10(sqrt(2*pi*N)) + N*log10(N/e)=-0.03

  最后值就为0

总结:用斯特林公式求位数时,考虑到N=1,加1放在取了整之后

(int)(log10(sqrt(2*pi*N)) + N*log10(N/e))=0
加1放在取了整之后 int(3.1+1)=4
int(3.1)+1=4
int(3)+1=4
int(3+1)=4
int(-0.03)+1=1
int(-0.03+1)=0
上一篇:关于iOS socket都在这里了


下一篇:iOS Burp suite CA证书 HTTPS