-
階乘
鎖定
階乘是基斯頓·卡曼(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)
對於0.5到1之間的小數擬合公式如下:
對於0到0.5之間的小數階乘,先計算(1-n)!,再按一下公式計算:
如圖2所示是擬合公式與實際值的對比圖
此處按(1)式拓展到負數區間,(-n)!的階乘如下,但與詞條定義衝突
如此進一步計算為:
(2)
對於負小數-1
此處有待商榷,如此,階乘的原定義就發生了改變。如圖3所示是按(1).(2)式拓展到正負數區間的階乘倒數圖像
階乘拓展與再定義
一直以來,由於階乘定義的不科學,導致以後的階乘拓展以後存在一些理解上得困擾,和數理邏輯的不順。
階乘從正整數一直拓展到複數。傳統的定義不明朗。所以必須科學再定義它的概念
真正嚴謹的階乘定義應該為:對於數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]