大數階乘

求大數階乘前要計算下最大數階乘的位數

以便于知道需要開多大的數組 .

第一種求法 ： 

lg(N!)=[lg(N*(N-1)*(N-2)*......*3*2*1)]+1

          =[lgN+lg(N-1)+lg(N-2)+......+lg3+lg2+lg1]+1

+1是為了向上取整，因為結果可能是小數

#include<cstdio>
#include<cmath>
int main()
{
  double sum=0;
  for(int i=1;i<=10000;i++)  // n是10000的情況下 
    sum+=log10(i);
  printf("%d\n",(int)sum+1);
  return 0;
}      

第二種求法：運用斯特林公式來計算 n! 的位數

斯特林公式（Stirling's approximation）是一條用來取n的​​階乘​​​的​​近似值​​的數學公式。一般來說，當n很大的時候，n階乘的計算量十分大，是以斯特林公式十分好用，而且，即使在n很小的時候，斯特林公式的取值已經十分準确。

用Stirling公式計算n!結果的位數時，可以兩邊取對數，

得： log10(n!) = log10(2*PI*n)/2+n*log10(n/E); 

故n!的位數= log10(2*PI*n)/2+n*log10(n/E)+1（注意：當n=1時，算得的結果為0）

#include<cstdio>
#include<cmath>
#define PI 3.141592654
#define E 2.71828182846   
int main()
{
  int n,sum=1;
  scanf("%d",&n);
  if(n>3)
    sum=log10(2*PI*n)/2+n*log10(n/E)+1;
  printf("%d\n",sum);
  return 0;
}      

求大數階乘運用的是模拟，也是用一個數組來儲存這個階乘的每一位數

練習題目:​​http://acm.hdu.edu.cn/showproblem.php?pid=1042​​

#include<cstdio>
#include<cmath>
#include<cstring> 
int a[35660+5];//儲存每一位所得得數 
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    memset(a,0,sizeof(a));
    int temp,dight=1;
    a[0]=1;
    dight=1;//dight是階乘的位數 
    for(int i=1;i<=n;i++)
    {
      int num=0;//儲存需要進位的數 
      for(int j=0;j<dight;j++)
      {
        temp=a[j]*i+num;//temp是每次相乘的結果 
        a[j]=temp%10;
        num=temp/10;//儲存需要進位的數
      }
      while(num)
      {
        a[dight]=num%10;//繼續儲存 
        num/=10;
        dight++;
      }
    }
    for(int i=dight-1;i>=0;i--)//逆序輸出每一位 
      printf("%d",a[i]);
    printf("\n");
  }  
  return 0;
}      

上邊的那一段代碼在51nod裡​​https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1057​​這一道題會TLE

我送出了好多次，才在有一次以 1000ms 通過....

看了别人寫的代碼，有的100ms内就通過了，簡直是我速度的十倍

他們的代碼不是讓a[i]隻儲存一位數，而是儲存多位，見過一位大佬的，一個a[i]儲存了14位數，我也寫了一下，140ms過了這道題

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
#define ll long long    
const ll c=1e14;  
ll a[10000000];  
int main()  
{  
    ll n;  
    while(~scanf("%lld",&n))   
    {  
        ll temp;  
        ll dight=1;  
        a[0]=1;  
        for(ll i=1;i<=n;i++)  
        {  
            ll num=0;  
            for(ll j=0;j<dight;j++)  
            {  
                temp=a[j]*i+num;  
                a[j]=temp%c;  
                num=temp/c;  
            }  
            if(num!=0)  
            {  
                a[dight++]=num;  
            }  
        }  
        printf("%lld",a[dight-1]);  
        for(ll i=dight-2;i>=0;i--)  
            printf("%014lld",a[i]);//這樣也可以   
//            printf("%0.14lld",a[i]);//這裡想不明白為什麼要加個.   
        printf("\n");  
    }  
    return 0;  
}  
//這個代碼可以計算1e4以内的數，超過這個範圍的話資料會溢出，需要在修改一下a[i]的最大儲存位數 
//就這段代碼而言，a[i]最多儲存1e14大小的數，要是在乘個1e5的數，結果是1e19大小，肯定會溢出
//是以測試99999!的時候前邊出現了負号。。。      

em.....

Python大法好...一次通過

n=eval(input())
sum=int(1)
for i in range(1,n+1):
    sum=sum*i
print(sum)      

當然還有更強的，直接引用函數，78ms過的

import math
n = int(input())
print(math.factorial(n))      

看了衆多大佬的代碼，受益匪淺。共勉之

參考：https://baike.baidu.com/item/%E6%96%AF%E7%89%B9%E6%9E%97%E5%85%AC%E5%BC%8F/9583086