N！阶乘的高效算法

阶乘递归代码：（教材）

#include<stdio.h>
int f(int n);
void main()
{
  printf("%d\n",f(5));
}
int f(int n)
{
  if(n==0)return 1;
  return n*f(n-1);
}

============================================================
大数阶乘问题
10000以内的阶乘及位数：
============================================================
代码一：

#include <stdio.h>
int main()
{
    int carry,n,j;
    int a[40001];
    int digit;
    int temp,i;   
    while(scanf("%d",&n)!=EOF){
    a[0]=1;digit=1;
    for(i=2; i<=n; i++)
    {
        for(carry=0,j=1; j<=digit; ++j)
        {
            temp=a[j-1]*i+carry;
            a[j-1]=temp%10;
            carry=temp/10;
        }
        while(carry)
        {
            //digit++;
            a[++digit-1]=carry%10;
            carry/=10;
        }
    }
   
    for(int k=digit; k>=1; --k)
        printf("%d",a[k-1]);
    printf("\n");
 printf("length=%d\n",digit);
 }
    return 0;
}

代码二：

#include <iostream>  
using namespace std; 
void main()  
{  
  int result[40000]; //保存结算结果的数组   
  int height = 1;  //结果的最高位   
  int num;  //计算阶乘的数字   
  cin>>num;   
  result[0] = 1;  
  for (int i=1;i<=num;i++)  
  {  
    int res = 0; //进位   
    for (int j=0;j<height;j++)  
    {  
      int buf = result[j] * i + res; //计算结果   
      result[j] = buf % 10;  //取当前位   
      res = buf / 10;   //计算进位   
    }  
    while (res)  
    {  
      result[height++] = res % 10; //取当前位   
      res /= 10;   //计算进位   
    }    
  }    
  
  for (int k=height-1;k>=0;k--)  
  {  
     cout<<result[k];  
  }  
  cout<<endl;  
  cout<<"length="<<height<<endl;  
} 

============================================================
例如1000阶乘位数：
log10(1)+log10(2)+•••+log10(1000)取整后加1
============================================================

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

============================================================
高效算法
斯特林公式(stirling)求阶乘的位数：
============================================================

#include<stdio.h>
#include<math.h>
#define PI 3.1415926
int main()
{
int cases,n,ans;
scanf("%d",&cases);
while(cases--)
{
   scanf("%d",&n);
   if(n==1)
    printf("1\n");
   else
   {
     ans=ceil((n*log(n)-n+log(2*n*PI)/2)/log(10));
      printf("%d\n",ans);
   }
}
return 0;
}

============================================================
阶乘最后非零位：
============================================================

#include<stdio.h> 
#include<string.h> 
#define maxn 10000 
int lastdigit(char buf[]) 
{ 
	const int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; 
	int len=strlen(buf),a[maxn],i,c,ret=1; 
	if(len==1) 
		return mod[buf[0]-'0']; 
	for(i=0;i<len;i++) 
		a[i]=buf[len-1-i]-'0'; 
	for(;len;len-=!a[len-1]) 
	{ 
		ret=ret*mod[a[1]%2*10+a[0]]%5; 
		for(c=0,i=len-1;i>=0;i--) 
			c=c*10+a[i],a[i]=c/5,c%=5; 
	} 
	return ret+ret%2*5; 
} 
int main() 
{ 
	char n[maxn]; 
	int a; 
	while(scanf("%s",n)!=EOF) 
	{ 
		a=lastdigit(n); 
		printf("%d\n",a); 
	} 
	return 0; 
}