夏清歡，應沈靜，陶駿，龔勇，宋衛(wèi)衛(wèi)

摘要：文章首先介紹了楊輝三角和二項式的基本原理，提出了三種求楊輝三角的程序算法，這三種算法分別是：組合數法、遞歸法和隊列法，使用Java語言在Eclipse平臺上實現了這三種算法，并對這三種算法的運行效率和時間復雜度進行了測試分析，得出了隊列法最優(yōu)的結論。

關鍵詞：楊輝三角；二項式；遞歸；隊列

中圖分類號：TP391? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）33-0034-04

1 引言

楊輝三角本質上是一組數的集合，是二項式系數呈三角形一種幾何排列，其通過圖形直觀地顯示了二項式系數，把組合數內在的一些代數性質直觀地從圖形中體現出來，是把一系列離散型的正整數與圖形相結合后所形成的一個特殊的三角形。楊輝三角是由我國南宋數學家楊輝發(fā)現的，是中國古代數學一項優(yōu)秀的研究成果，法國科學家帕斯卡在390多年后也發(fā)現了此成果，所以楊輝三角有時候也稱為帕斯卡三角。

Java是一種面向對象高級編程語言，不僅具有面向對象語言的繼承、封裝和多態(tài)優(yōu)點，還揚棄了難以理解的一些理論，比如多繼承，所以Java語言具有功能強勁和簡單實用兩個特點，允許程序員快速高效地進行復雜編程。Java語言還具有分布式、平臺獨立與可移植性、多線程和動態(tài)性等特點。Java語言可以實現桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序等[1]。

本文運用Java語言中的桌面應用程序實現了楊輝三角的形成和顯示，而且使用組合數、遞歸和隊列三種不同的方法進行了實現，并對這三種方法的優(yōu)劣進行了對比和分析。

2 楊輝三角

一個二項式如下表示：

[（x+y）n=C0n*xn+C1n*xn-1*y+C2n*xn-2*y2]+...+[Cnn*yn]? ? ?（1）

楊輝三角是由一系列二項式中的系數（組合數）構成的，一個楊輝三角的顯示圖如圖1所示。

<E：＼2022知網文件＼33＼2xs202233＼Image＼image2.png>

圖1? ?楊輝三角

第一行為k=0的二項式的系數，第二行是k=1的二項式的系數，以此類推，第n+1行是k=n的二項式的系數，楊輝三角所對應的圖形是一個等腰三角形，兩條腰上的數值都是1，其余的一般項的數值滿足：

[Crk=Crk-1]+[Cr-1k-1]? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

一般項的數值等于上一行相鄰的兩個項的數值之和[2]。

3 程序設計

由于楊輝三角中數值具有規(guī)律性，所以可以通過計算機編程實現，本研究采用了三種不同的方法實現了楊輝三角，所采用的編程語言是Java語言，具體Java版本號為JDK1.9，開發(fā)平臺使用是Eclipse 4.11，項目結構如圖2所示。

<E：＼2022知網文件＼33＼2xs202233＼Image＼image3_1.png>

圖2? ?項目結構圖

項目名稱為Pyanghui，然后在此項目中建立了5個類，Cmain是主函數入口類，Cyang1是通過求組合數實現楊輝三角的類，Cyang2是通過遞歸實現楊輝三角的類，Cyanghui是通過隊列實現楊輝三角的類，queue為隊列類[3]。

3.1 組合數法

組合數法的思想是：先求排列值[Pnn]=n！，再求組合值[Cmn]=n！/（m！*（n-m）?。?，然后再分行顯示，每行先打印相應的空格數，再顯示一系列組合的值，其對應的流程圖如圖3所示。

<E：＼2022知網文件＼33＼2xs202233＼Image＼image4_1.png>

圖3? ?方法1流程圖

具體的java程序代碼如下：

publicclass Cyang1 {

//求階乘n！函數

publicint mul（int n）

{

int m;

if（n==0）

m=1;

else

{m=1;

for（int i=1;i<=n;i++）

m=m*i; }

return（m）;}

//求組合數[Cmn]函數

publicint zuhe（int n，int m）

{if（n<m） //不合法情況

{System.out.println（"不合法?。?！"）;

System.exit（0）;

return（0）;}

else

{return（mul（n）/（mul（m）*mul（n-m））） ;}

}

//打印組合數[Cmn]函數

publicvoid ydisplay（int n，int m）

{System.out.println（zuhe（n，m））;}

//求n行楊輝三角函數

publicvoid calyang（int n）

{//j控制行數

for（int j=0;j<=n;j++）

{//打印相關空格

for（int m=0;m<=n-j;m++）

System.out.print（""）;

//顯示一行中的所有組合數

for（int k=0;k<=j;k++）

{

System.out.print（zuhe（j，k））;//換行

System.out.print（""）;//兩個數之間打印空格

}

System.out.println（）;//換行

}}

}

顯然ydisplay函數是通過二重循環(huán)實現，而且最里層循環(huán)調用了zuhe函數，zuhe函數又調用了mul函數，mul函數使用一重循環(huán)實現，其問題規(guī)模為n，所以mul函數和zuhe函數的算法時間復雜度為O（n），ydisplay函數的時間復雜度為O（[n3]）。

Java語言里int值占用4個字節(jié)，其取值范圍為（-2147483648到2147483647），13！>2147483647，所以當用mul函數求13的階乘時會溢出，calyang函數只能求0到12的楊輝三角[4]。

<E：＼2022知網文件＼33＼2xs202233＼Image＼image5.png>

圖4? ?求組合數遞歸過程圖

3.2 遞歸法

楊輝三角中的組合數[Cmn]有一定規(guī)律，其規(guī)律為：如果m=0或者m等于n，則此組合數為1，否則[Cmn]=[Cmn-1]+[Cm-1n-1]，例如求[C35]的過程如圖4所示。

此方法對應算法思想和流程圖除了求組合數有差異外，其余的均類似，具體的Java代碼為：

public class Cyang2 {

//求組合數函數，n為上標，m為下標

public int caly（int n，int m）

{

//判斷合法情況，上下標都是非零整數，上標大于等于下標

if（n>=0&&m>=0&&n>=m）

{ if（m==0）

//遞歸基1：第一列為1

return（1）;

else

if（n==m）

//遞歸基2：行等于列時返回1

return（1）;

Else

//遞歸調用

return（caly（n-1，m）+caly（n-1，m-1））;}

Else

//不合法時返回-1

return（-1）;}

//顯示楊輝三角函數，n為楊輝三角行數

public void ydisplay2（int n）

{//i控制楊輝三角行數

for（int i=0;i<=n;i++）

{//顯示每行的空格

for（int m=0;m<=n-i;m++）

System.out.print（""）;

//打印每行的組合數，j控制每行的具體數目

for（int j=0;j<=i;j++）

System.out.print（caly（i，j）+""）;

//換行

System.out.println（）;

}}}

此方法也是通過二重循環(huán)實現，其中內層循環(huán)調用遞歸函數caly，遞歸函數的時間復雜度為O（n），所以此方法的時間復雜度也為O（[n3]）。通過此方法求組合數不涉及乘法，只使用了加法，當n=30時才會發(fā)生溢出，所以此方法能求從n=0到n=29的楊輝三角。遞歸法也有其相應的缺陷，很多組合數被重復運算多次，降低了算法的效率，例如在圖4中，[C12]被計算了3次[5]。

3.3 隊列法

隊列法的基本思想為：（1）當楊輝三角只有一行時，打印相應空格和1；（2）當楊輝三角有n行時，先執(zhí)行（1），然后0進隊列，0是第一行和第兩行楊輝三角組合數的分隔值，然后連續(xù)兩個1進隊列，此時隊列有隊尾到隊首的元素，分別為1、1、0，一個0再進隊列，這個0是第二行和第三行楊輝三角組合數的分隔值，此時隊首值poll值出，因為如果當前楊輝三角組合值不在邊界，其等于上一行相鄰元素之和，要顯示的值evs等于出隊值poll加當前隊首值first，如果evs＞0，則顯示相關空格和evs，如果firstl等于0，不再對隊列進行操作，換行顯示下一行的楊輝三角值；（3）反復進行第二步，直到第n行的楊輝三角值顯示完畢。具體的求三行楊輝三角的例子如圖5所示。

<E：＼2022知網文件＼33＼2xs202233＼Image＼image6.png>

圖5? ? 求組合數遞歸過程圖

左邊三個虛線方框代表求三行楊輝三角組合值的過程，右部三個三角形圖形表示顯示楊輝三角組合值的過程。初始隊列為空，顯示1，對應第一行的楊輝三角值；0、1、1、0按順序進隊列，0出隊列，0不顯示，0加1等于1進隊列，1出隊列，顯示空格和1，1加1等于2進隊列，1出隊列，1加0等于1進隊列，0不再出隊列，此時第二行顯示完畢，進行換行；0進隊列，此時隊列為0、1、2、1、0，0出隊列不顯示，0加1等于1進隊列，然后1出隊列，顯示空格和1，1加2等于3進隊列，2出隊列，2加1等于3進隊列，1出隊列，0加1等于1進隊列，顯示1和空格，0不再出隊列，此時第三行顯示完畢，進行換行，隊列中的值為1，3，3，1，0，這是為第四行顯示做準備的，顯然在顯示第n行楊輝三角值的過程中，第n+1行的楊輝三角值已經求好存儲在隊列中[6]。

具體的Java代碼為：

public class Cyanghui {

//楊輝三角從0到n總共n+1行

public void fyang（int n）

//處理第一行情況

{if （n==0）

{for（int i=1;i<=n;i++）

System.out.print（""）;

System.out.println（'1'）;}

else

//其余情況

{for（int i=1;i<=n;i++）

System.out.print（""）;

System.out.println（'1'）;

//創(chuàng)建隊列

queue Q=new queue（）;

Q.offer（0）;

Q.offer（1）;

Q.offer（1）;

int xfir=0;

int evs=0;

for（int k=1;k<n;k++）

//處理空格

{for（int i=1;i<=n-k;i++）

System.out.print（""）;

//換行標志0進隊列

Q.offer（0）;

do

{

xfir=Q.poll（）;

//大于0才顯示

if（xfir>0）

System.out.print（xfir+""）;

evs=xfir+Q.first（）;

Q.offer（evs）;

xfir=Q.first（）;

} while（xfir>0）;//只有隊首值大于0才繼續(xù)執(zhí)行

System.out.println（）;

}}}}

隊列類 queue可以通過自己編寫實現，也可以使用Java語言中隊列類進行實現。

此方法是通過三重循環(huán)實現，所以此方法的時間復雜度也為O（[n3]）。通過此方法求組合數不涉及乘法，同樣只使用了加法，當n=30時才會發(fā)生溢出，所以此方法能求從n=0到n=29的楊輝三角。此方法沒有重復計算組合數，所以算法的效率高于方法二。

3.4 算法實驗分析

在Cmain類中使用如下代碼對這三種算法進行運行時間計算：

long Tbegin=System.nanoTime（）;? ?//獲取算法開始時間，單位為納秒

分別運行三種方法；

long Tend=System.nanoTime（）; //獲取算法結束時間

System.out.println（"算法運行時間： "+（endTime-startTime）+"ns"）;

在CPU為酷睿5（CORE5）和操作系統為Win10的工作站上分別運行三種算法，三種算法的運行時間和對應行數的關系如表1所示。

表1? ?算法運行時間和行數對照圖

[算法

時間（納秒）

行數 5行 10行 15行 20行 25行 組合數 2465400 3962150 不支持 不支持 不支持 遞歸 2520000 3989950 8245200 12647200 17567900 隊列 2149900 3679900 7388300 10290100 14602600 ]

通過表1可以得出隊列法最優(yōu)，遞歸法的算法效率次之，而組合數法因為溢出的緣故，其只能支持0到12行的楊輝三角的計算[7]。

4 結論

本研究闡述了二項式的基本原理，二項式的值是楊輝三角的基本組成元素，使用Java語言和Eclipse平臺通過組合數、遞歸和隊列三種算法實現了楊輝三角的運算和顯示，并對這三種算法的時間復雜度和效率進行了分析，得出了遞歸算法最優(yōu)，其運行時間和算法效率都高于其余兩種算法。

本文所介紹的三種算法的運行范圍因為整數溢出的緣故有限，組合數算法只能求行數從0到12的楊輝三角，遞歸法和隊列法只能求行數從0到29的楊輝三角，運行范圍可以考慮通過字符隊列和大數加法進行擴大，這也是下一步的研究方向[8]。

參考文獻：

[1] 王先東.楊輝三角中的奇數與偶數[J].數學通報，2009，48（5）：62-63，66.

[2] 楊明順.楊輝三角的若干性質研究[J].渭南師范學院學報，2016，31（4）：9-12.

[3] 李旭東.再探“楊輝三角”中的行列式[J].數學學習與研究，2013（23）：111.

[4] 馮潔，吳芳.探討C語言中輸出楊輝三角的教學方法[J].電腦知識與技術（學術交流），2007，3（13）：113-113，115.

[5] 宋鈺.經典數據結構隊列的研究和實現[J].電腦編程技巧與維護，2019（12）：14-15.

[6] 陳竹云，葉雯.數據結構中隊列的應用研究[J].電腦知識與技術，2017，13（3）：5-7.

[7] 沈華.數據結構課程中棧和隊列實驗教學方案設計[J].教育教學論壇，2016（24）：274-276.

[8] 耿國華.數據結構[M].北京：高等教育出版社，2005.

【通聯編輯：代影】