-
階乘
鎖定
階乘是基斯頓·卡曼（Christian Kramp，1760～1826）於 1808 年發明的運算符號，是數學術語。
亦即n!=1×2×3×...×(n-1)×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。
- 中文名
- 階乘
- 外文名
- factorial
- 分 類
- 數學
- 提出者
- 基斯頓卡曼
- 特 點
- 小於及等於該數的正整數的積
- 發明時間
- 1808年
階乘概念
階乘是基斯頓·卡曼（Christian Kramp，1760～1826）於 1808 年發明的運算符號，是數學術語。
一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且0的階乘為1。自然數n的階乘寫作n!。1808年，基斯頓·卡曼引進這個表示法。
階乘計算方法
大於等於1
任何大於等於1 的自然數n 階乘表示方法：
或
0的階乘
1！=1×0！
0！=1！÷1=1
定義的必要性
由於正整數的階乘是一種連乘運算，而0與任何實數相乘的結果都是0。所以用正整數階乘的定義是無法推廣或推導出0！=1的。即在連乘意義下也無法解釋“0！=1”。
給“0！”下定義只是為了相關公式的表述及運算更方便。
使用的廣泛性
當
是大於1的正整數時，有公式
，當0的階乘被定義為0！=1後，公式
對任意正整數
就都成立了。
階乘定義範圍
通常我們所説的階乘是定義在自然數範圍裏的（大多科學計算器只能計算 0～69 的階乘），小數科學計算器沒有階乘功能，如 0.5！，0.65！，0.777！都是錯誤的。但是，有時候我們會將Gamma 函數定義為非整數的階乘，因為當 x 是正整數 n 的時候，Gamma 函數的值是 n－1 的階乘。
伽瑪函數（Gamma Function）
定義伽馬函數：
運用積分的知識，我們可以證明Γ（s）=（s-1）× Γ（s-1）
所以，當 x 是整數 n 時，
這樣 Gamma 函數實際上就是階乘的延拓。
計算機科學
用Ruby求 365 的階乘。
def AskFactorial(num) factorial=1;
step(num,1){|i| factorial*=i}
return factorial end factorial=AskFactorial(365)
puts factorial
階乘有關公式
該公式常用來計算與階乘有關的各種極限。
此為斯特林公式的簡化公式。
階乘雙階乘
雙階乘用“m！！”表示。
當 m 是自然數時，表示不超過 m 且與 m 有相同奇偶性的所有正整數的乘積。如：
當 m 是負偶數時，m！！不存在。
自然數雙階乘比的極限
階乘的逼近函數公式
對於正整數
此逼近函數把近1 數處理到最小，函數指數誤差如圖1所示
圖1
對於帶小數大於1的正實數的階乘計算公式為
（1）
對於0.5到1之間的小數擬合公式如下：
對於0到0.5之間的小數階乘，先計算（1-n）!,再按一下公式計算：
如圖2所示是擬合公式與實際值的對比圖
圖2
此處按（1）式拓展到負數區間，(-n)!的階乘如下，但與詞條定義衝突
如此進一步計算為：
（2）
對於負小數-1
此處有待商榷，如此，階乘的原定義就發生了改變。如圖3所示是按（1）.（2）式拓展到正負數區間的階乘倒數圖像
圖3
階乘拓展與再定義
一直以來，由於階乘定義的不科學，導致以後的階乘拓展以後存在一些理解上得困擾，和數理邏輯的不順。
階乘從正整數一直拓展到複數。傳統的定義不明朗。所以必須科學再定義它的概念
真正嚴謹的階乘定義應該為：對於數n，所有絕對值小於或等於n的同餘數之積。稱之為n的階乘，即n!
對於複數應該是指所有模n小於或等於│n│的同餘數之積。。。對於任意實數n的規範表達式為：
正數 n=m+x,m為其正數部，x為其小數部
負數n=-m-x,-m為其正數部，-x為其小數部
對於純複數
n=(m+x)i,或n=-(m+x)i
我們再拓展階乘到純複數：
正實數階乘: n!=│n│!=n(n-1)(n-2)....(1+x).x!=(i^4m).│n│!
負實數階乘: （-n）!=cos(m
)│n│!=(i^2m)..n(n-1)(n-2)....(1+x).x!
(ni)!=(i^m)│n│!=(i^m)..n(n-1)(n-2)....(1+x).x!
(-ni)!=(i^3m)│n│!=(i^3m)..n(n-1)(n-2)....(1+x).x!
階乘廣義複數階乘
對於一般的複數而言， 所有模n小於或等於│n│的同餘數之積，意味着其實部與虛部必須滿足一定條件，條件如下
複數z=ak+ibk
當z的幅角a 相等時zk=（n-k）(cosa+isina),它的階乘為：
説明：複數階乘存在路徑問題，路徑不同階乘的結果就不相同，幅角a相等是指按直線從0點附近到z,不等時是按曲線取階乘。複數階乘存在方向問題，就是説它是有方向的量。。。廣義階乘涵括正負實數階乘。。。
階乘應用
求n!的位數
方法一
可以將n!表示成10的次冪,即n!=10^M(10的M次方)則不小於M的最小整數就是 n!的位數，對該式兩邊取對數，有 M =log10^n!
即：
M = log10^1+log10^2+log10^3...+log10^n
循環求和,就能算得M值，該M是n!的精確位數
代碼：
#include "iostream"
#include "math.h"
using namespace std;
int main()
{
int n,
i;
double d;
while (scanf("%d",&n)!=EOF)
{
d=0;
for (i=1;i<=n;i++)
d+=(double)log10(i);
printf("%d\n",(int)d+1);
}r
eturn 0;
}
方法二
利用斯特林（Stirling）公式的進行求解。下面是推導得到的公式：
res=(long)( (log10(sqrt(4.0*acos(0.0)*n)) + n*(log10(n)-log10(exp(1.0)))) + 1 );
當n=1的時候，上面的公式不適用，所以要單獨處理n=1的情況！
有關斯特林（Stirling）公式及其相關推導，這裏就不進行詳細描述，
這種方法速度很快就可以得到結果。
求n!末尾0的個數
思路：
一個數 n 的階乘末尾有多少個 0 取決於從 1 到 n 的各個數的因子中 2 和 5 的個數
而 2 的個數是遠遠多餘 5 的個數的, 因此求出 5 的個數即可
題解中給出的求解因子 5 的個數的方法是用 n 不斷除以 5, 直到結果為 0
然後把中間得到的結果累加. 例如, 100/5 = 20, 20/5 = 4, 4/5 = 0
則 1 到 100 中因子 5 的個數為 (20 + 4 + 0) = 24 個
即 100 的階乘末尾有 24 個 0. 其實不斷除以 5
是因為每間隔 5 個數有一個數可以被 5 整除, 然後在這些可被 5 整除的數中
每間隔 5 個數又有一個可以被 25 整除, 故要再除一次, ... 直到結果為 0, 表示沒有能繼續被 5 整除的數了.
代碼：
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int N,i,mod5,d5,count0=0;
scanf("%d",&N);
for (i=1;i<=N;i++)
{
mod5=i%5;
d5=i/5;
while(mod5==0)
{
count0++;
mod5=d5%5;
d5=d5/5;
}
}
printf("%d的個數 %d\n",N,count0);
}
階乘計算機階乘
Logo 語言
Logo 語言因為是少兒的學習語言，階乘方法要複雜一些，而且時間較慢，下面是低精度、高精度、統計位數的階乘算法：
TO DJDJC :N ;低精度階乘
MAKE "S 1;累乘器開始的值是1
FOR "I 1 :N[MAKE "S :S * :I]
(PR :N [！=] :S)
END
TO GJDJC :N;高精度階乘
IF :N>=1000 THEN PR "請輸入不大於999的數！ STOP
MAKE "PRECISION 6;計算顯示位數設定為六位
MAKE "A ARRAY 860;定義數組空間0-859組
ASET :A 1 1;乘法數組第1空間賦值為1
FOR "I 2 859[ASET :A :I 0] ;其他數組空間賦值為0
FOR "I 1 :N [JC :I];調用階乘過程
MAKE "K 0;數組空間是0的標記
MAKE "Z 0;總共有多少組數字的標記
MAKE "WS 0;累加總共有多少位的計數器
TYPE :N TYPE[！=];從高位到低位顯示計算結果
FOR "M 1 859[XXS 860-:M]
PR[ ] TYPE[這是一個]TYPE :WS TYPE[位數]PR[]
END
TO JC :I;計算階乘的過程
FOR "J 1 858[CF :I :J] ;對所有數組空間逐一計算乘法
FOR "J 1 858[CLJW :J];處理乘法過程中的進位
END
TO CF :I :J ;計算乘法的過程
MAKE "ZJ AGET :A :J
MAKE "ZJ :ZJ * :I;I是階乘中需要累乘的數
ASET :A :J :ZJ
END
TO CLJW :J;處理進位的過程
MAKE "X AGET :A :J
IF :X<1000 THEN GO "XXX;處理沒有進位的數組
MAKE "JINWEI INT (:X / 1000);截取小於1000的尾數
MAKE "WEISHU :X - :JINWEI * 1000 ;截取進位的數字
ASET :A :J :WEISHU;存儲尾數
MAKE "Y AGET :A :J+1
MAKE "Y :Y + :JINWEI
ASET :A :J+1 :Y;向上進位
LABEL "XXX
END
TO XXS :P;顯示計算結果的過程
MAKE "NN AGET :A :P
IF (AND :NN=0 :K=0) THEN[GO "END_]ELSE[MAKE "K 1 MAKE "Z :Z+1] ;避開無效數組
IF :Z=1 THEN MAKE "WS :WS+(COUNT :NN) GO "UP;計算頭一個有效數組的位數
IF :Z>1 THEN MAKE "WS :WS+3;累計數值的總位數
IF :NN < 10 THEN TYPE [0];填充空位0
IF :NN < 100 THEN TYPE [0]
LABEL "UP
TYPE :NN
LABEL "END_ ;越過開頭的空數組
END
TO JC :N ;求解任意數的階乘是多少位數
MAKE "S 0;先賦值位數為0
FOR "I 1 :N[MAKE "S :S+LOG10 :I]
TYPE[:S=]PR :S
END
Common Lisp 語言
在 Common Lisp 中， 可以很方便的使用更為簡潔的使用遞歸實現階乘：
(defun factorial (n) (cond ((> n 0) (* (factorial (- n 1)) n)) ((= n 0) 1) (t (error "N is smaller than 0."))))
注意：因為百度不提供任何Lisp語言的代碼框，此處使用的是Python的代碼框，所以關鍵字可能無法高亮顯示
Python 語言
在 Python 中， 同樣可以使用這種簡潔方式實現階乘的計算：
def factorial(n)： if(n<=1): return 1 else: return factorial(n-1) * n
C語言
【計算出“ 10！”的值是多少？】
#include<stdio.h>
int main()
{
int n, x;
for(n = x = 1; n <= 10; ++n) {
x *= n;
printf("%d\t%d\n", n, x);
}
return 0;
}
/*10!：3628800*/
Pascal中
program test; varn:longint; function jc(n:longint):qword; begin if n=0 then jc:=1 else jc:=n*jc(n-1)end; begin readln (n); writeln (jc(n))end.
C++ 中
#include<iostream>
using namespace std;
long long f(int n)
{
long long e=1;
if(n>0)
e=n*f(n-1);
cout<<n<<"！="<<e<<endl;
return e;
}
int main()
{
int m=20;
f(m);
return 0;
}
以上使用 C++ 11 標準
也可以利用積分求浮點數階乘：
#include<cstdio>
#include<cmath>
double s;
const double e=exp(1.0);
double F(double t)
{
return pow(t,s)*pow(e,-t);
}
double simpson(double a,double b)
{
double c=a+(b-a)/2;
return (F(a)+4*F(c)+F(b))*(b-a)/6;
}
double asr(double a,double b,double eps,double A)
{
double c=a+(b-a)/2;
double L=simpson(a,c),R=simpson(c,b);
if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0;
return asr(a,c,eps/2,L)+asr(c,b,eps/2,R);
}
double asr(double a,double b,double eps)
{
return asr(a,b,eps,simpson(a,b));
}
int main()
{
scanf("%lf",&s);
printf("%lf\n",asr(0,1e2,1e-10));
return 0;
}
JAVA 中
public class Main{
final static int MAX=20;// 可以替換 MAX 的值。
public static void main(String[] args)
{
int i=1;
long result=1;
long[] n=new long[MAX];
do{
result*=(i+1);
System.out.println(i+1+"！="+result);
n[i]=result;
i++;
}while(i<MAX);
n[0]=1;
//階乘end
}
}使用for循環更簡單易懂:
public static void main(String[] args) {
long result = 1;
for (int j = 0; j < 10; j++) {
result *= (j + 1);
System.out.println(j + 1 + "！=" + result);
}
}
php中
function jc($n){
if($n>1){
return $n*jc($n-1);
}else{
return 1;
}
}
echo jc(3);
JavaScript 階乘
function factorial(num){
if (num <= 1)
return 1;
else
return num * arguments.callee(num - 1);
};
彙編中的階乘算法
.286 .model small,stdcall Factorial PROTO :WORD .stack 200h .data f_n WORD 6 result WORD ? .CODE START: mov ax,@data mov ds,ax mov es,ax invoke Factorial,f_n mov result,ax mov ah,4ch int 21h ;計算階乘 ;輸入參數:[ebp+8] = n, 需要計算的數字 ;返回參數:eax = n的階乘 Factorial PROC near uses bx,fn mov ax,fn cmp ax,0 ja L1 mov ax,1 jmp L2 L1: dec ax invoke Factorial,ax ReturnFact: mov bx,fn mul bx L2: ret Factorial ENDP END START
階乘高精度求階乘
Visual Basic NET
'本代碼使用了斯特林（Stirling）逼近的方式計算較大數值的階乘和有小數位數的數值的階乘。詳細過程請參見《用Stirling逼近近似計算階乘的探討與應用》一書。
'根據驗算，結果與Windows 7的計算器結果有出入，但是還能忍受。特別是可以計算較大數值的階乘，例如 36000，Windows計算器溢出。當然無法考證我的結果與真實結果的差距，沒有比較……^.^
Private Sub 計算按鈕_Click(sender As Object, e As EventArgs) Handles 計算按鈕.Click
Dim 階乘數 As Decimal = CDec(InputBox("請輸入一個數值，將得到它的階乘結果。"))
' 因為要計算比較大的數值，因此將較小的整數值按照階乘的定義來計算得到準確值，但 VBULong整數的最大範圍能計算到 20的階乘，21將溢出；較大的數值或者小數按照 Stirling 逼近的方式計算。
If 階乘數 >= 0 And 階乘數 <= 20 And Fix(階乘數) = 階乘數 Then
MsgBox(階乘數 & " 的階乘結果是：" & 小階乘(CInt(階乘數)))
Else
MsgBox(階乘數 & " 的階乘結果是：" & 大數階乘(CDbl(階乘數)) & " E " & 大數階乘指數(階乘數))
End If
End Sub
'這是小數值階乘的過程，標準計算方式，結果精確。
Private Function 小階乘(階乘數 As Integer) As ULong
If 階乘數 = 0 Or 階乘數 = 1 Then'如果數值是 0或者 1，直接返回 1。
Return 1
Else
小階乘 = 1
For 階乘次數 As Integer = 1 To CInt(階乘數)
小階乘 *= CULng(階乘次數)
Next
Return 小階乘
End If
End Function
'''
''' 這個過程用 Stirling 逼近的方式計算較大數值和有小數點的值的階乘結果的前 15 位。詳細過程見《用 Stirling 逼近近似計算階乘的探討與應用》一書。
'''
'''
'''
'''
Private Function 大數階乘(階乘數 As Double) As Double
Dim X As Double = 0.5 * Math.Log(2 * 階乘數 * Math.PI) / Math.Log(10) + 階乘數 * Math.Log(階乘數 / Math.Exp(1)) / Math.Log(10)
Dim XDouble As Double = X - Math.Truncate(X)
Dim Y As Double = Math.Exp(XDouble * Math.Log(10))
Dim Z As Double = Math.Exp(1 / 12 / 階乘數 - 1 / 360 / 階乘數 / 階乘數)
Return Y * Z
End Function
'''
''' 這個過程用 Stirling 逼近的方式計算較大數值和有小數點的值的階乘結果的小數點位數。詳細過程見《用 Stirling 逼近近似計算階乘的探討與應用》一書。
'''
'''
'''
'''
Private Function 大數階乘指數(階乘數 As Double) As ULong
Dim X As Double = 2 * Math.PI * 階乘數
Dim Y As Double = 0.5 * Math.Log10(X)
Dim A As Double = 階乘數 * Math.Log10(階乘數 / Math.E)
Return CULng(Math.Truncate(Y + A))
End Function
C語言
#include<stdio.h>
#define N 5000//modify it to hold larger number
//to avoid stack overflow, define it as global varible
int f[N];//do not need to be assigned as 0 because it has already been assigned 0 by the system
int main()
{
int n,i,j,s,up;
scanf("%d",&n);
for(i=2,f[0]=1;i<=n;i++)
{
for(j=up=0;j<N;j++)
{
s=f[j]*i+up;
f[j]=s%10;
up=s/10;
}
}
for(i=N-1;f[i]==0;i--);
for(;i>=0;i--)
printf("%d",f[i]);
printf("\n");
return 0;
}
Pascal 語言(可計算到3251!)
var a:array[1..10000] of integer;
b,c,d,t,x:integer;
begin
readln (x);
if (x<0) then begin writeln ('error!'); readln; halt; end;
for t:=1 to 10000 do a[t]:=0;
d:=1; a[1]:=1;
for c:=1 to x do {一直乘到x}
begin
t:=1; b:=0; {t:第幾位數 b:進位 d:總位數}
repeat
a[t]:=a[t]*c+b; {數組每位均乘上c,同時加上進位}
b:=a[t] div 10; {分離出進位}
if a[t]>=10 then if (t=d) then d:=d+1; {假如最後一位乘時有}
{進位,則總位數加1}
a[t]:=a[t] mod 10;
inc (t); {數組下一位}
until (t>d); {直到乘完數組的每一位數字}
end;
for t:=d downto 1 do write (a[t]); {輸出}
end.
- 參考資料
-
- 1. 蔣李軍.高精度計算大數階乘的C語言源代碼和解釋[J].電腦編程技巧與維護,2015,(15):51-57. ．萬方數據庫[引用日期2017-08-29]
