階乘

階乘

階乘是基斯頓·卡曼(Christian Kramp,1760~1826)於 1808 年發明的運算符號,是數學術語。

一個正整數的階乘factorial)是所有小於及等於該數的正整數,並且0的階乘為1。自然數n的階乘寫作n!。1808年,基斯頓·卡曼引進這個表示法。

亦即n!=1×2×3×...×n。階乘亦可以遞歸方式定義:0!=1,n!=(n-1)!×n。

基本介紹

  • 中文名:階乘
  • 外文名:factorial
  • 分類:數學
  • 提出者:基斯頓卡曼
  • 時間:1808年
  • 特點:小於及等於該數的正整數的積
概念,計算方法,定義範圍,雙階乘,拓展與再定義,廣義複數階乘,套用,計算機階乘,高精度求階乘,

概念

階乘是基斯頓·卡曼(Christian Kramp,1760~1826)於 1808 年發明的運算符號,是數學術語。
一個正整數的階乘(factorial)是所有小於及等於該數的正整數的積,並且0的階乘為1。自然數n的階乘寫作n!。1808年,基斯頓·卡曼引進這個表示法。

計算方法

大於等於1
任何大於等於1 的自然數n 階乘表示方法:
0的階乘
0!=1。
定義的必要性
由於正整數的階乘是一種連乘運算,而0與任何實數相乘的結果都是0。所以用正整數階乘的定義是無法推廣或推導出0!=1的。即在連乘意義下無法解釋“0!=1”。
給“0!”下定義只是為了相關公式的表述及運算更方便。
離散數學組合數定義中,對於正整數
滿足條件
的任一非負整數
都是有意義的,特別地在
時,有
。 但是對於組合數公式
來說,在
時,都由於遇到0的階乘沒有定義而發生巨大尷尬。
對照結論
和公式
,我們順勢而為地定義“0!=1”就顯得非常必要了。這樣,組合數公式在
時也通行無阻,不會有任何尷尬了。
使用的廣泛性
(1)在函式
麥克勞林級數展開式中
明確地用到了“0!=1”的定義,沒有這個定義就只能麻煩地表示為
(2)作為階乘延拓的伽瑪函式是定義在複數範圍內的亞純函式,與之有密切聯繫的函式還有貝塔函式(他們分別被稱為歐拉第二積分與歐拉第一積分)。
伽瑪函式
來說,顯然有
是大於1的正整數時,有公式
,當0的階乘被定義為0!=1後,公式
對任意正整數
就都成立了。
為什麼0!=1?
必須再次清楚地說明:
只是一種定義出來的特殊的“形式”上的階乘記號。它無法用演繹方法來論證。
為什麼0!=1”這個問題是偽問題,而初學者總要追問這個偽問題。這就說明了我們在教材和教學實踐中都沒有把“有關‘0!=1’只是一種‘定義’的概念”講清楚。
有教輔材料上把上述必要性及合理性視作為推導的過程,那當然是大錯特錯了。必要性及合理性只是有限幾個例子,“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 是負偶數時,m!!不存在。
自然數雙階乘比的極限
階乘的逼近函式公式
對於正整數
此逼近函式把近1 數處理到最小,函式指數誤差詳右側圖片
階乘
對於帶小數大於1的正實數的階乘計算公式為
(1)
對於0.5到1之間的小數擬合公式如下:
對於0到0.5之間的小數階乘,先計算(1-n)!,再按一下公式計算:
計算時不要把先後順序弄反,否則誤差會增加,以上公式通過了伽馬函式的校驗,誤差極小。
以下是擬合公式與實際值的對比圖
階乘
此處按(1)式拓展到負數區間,(-n)!的階乘如下,但與詞條定義衝突
如此進一步計算為:
(2)
這樣把階乘拓展到負數區間,形成了負數區間的周期震盪階乘函式。
對於負小數-1<n<0區間,的階乘其值就等於其決定值的階乘了
此處有待商榷,如此,階乘的原定義就發生了改變。。。以下是按(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);      }return 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語言
在 C 語言中,使用循環語句可以很方便的求出階乘的值,下面介紹一個很簡單的階乘例子。(因為網上多數是比較麻煩的方法)
【計算出“ 1!+ 2!+ 3!+ …… + 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,stdcallFactorial PROTO :WORD.stack 200h.data    f_n WORD 6    result WORD ?.CODESTART:    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:    retFactorial ENDPEND 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
''' <summary>
''' 這個過程用 Stirling 逼近的方式計算較大數值和有小數點的值的階乘結果的前 15 位。詳細過程見《用 Stirling 逼近近似計算階乘的探討與套用》一書。
''' </summary>
''' <param name="階乘數"></param>
''' <returns></returns>
''' <remarks></remarks>
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
''' <summary>
''' 這個過程用 Stirling 逼近的方式計算較大數值和有小數點的值的階乘結果的小數點位數。詳細過程見《用 Stirling 逼近近似計算階乘的探討與套用》一書。
''' </summary>
''' <param name="階乘數"></param>
''' <returns></returns>
''' <remarks></remarks>
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 varibleint f[N];//do not need to be assigned as 0 because it has already been assigned 0 by the systemint 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.

相關詞條

熱門詞條

聯絡我們