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

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

關(guān)鍵詞：楊輝三角；二項(xiàng)式；遞歸；隊(duì)列

中圖分類號(hào)：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）33-0034-04

1 引言

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

Java是一種面向?qū)ο蟾呒?jí)編程語(yǔ)言，不僅具有面向?qū)ο笳Z(yǔ)言的繼承、封裝和多態(tài)優(yōu)點(diǎn)，還揚(yáng)棄了難以理解的一些理論，比如多繼承，所以Java語(yǔ)言具有功能強(qiáng)勁和簡(jiǎn)單實(shí)用兩個(gè)特點(diǎn)，允許程序員快速高效地進(jìn)行復(fù)雜編程。Java語(yǔ)言還具有分布式、平臺(tái)獨(dú)立與可移植性、多線程和動(dòng)態(tài)性等特點(diǎn)。Java語(yǔ)言可以實(shí)現(xiàn)桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等[1]。

本文運(yùn)用Java語(yǔ)言中的桌面應(yīng)用程序?qū)崿F(xiàn)了楊輝三角的形成和顯示，而且使用組合數(shù)、遞歸和隊(duì)列三種不同的方法進(jìn)行了實(shí)現(xiàn)，并對(duì)這三種方法的優(yōu)劣進(jìn)行了對(duì)比和分析。

2 楊輝三角

一個(gè)二項(xiàng)式如下表示：

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

楊輝三角是由一系列二項(xiàng)式中的系數(shù)（組合數(shù)）構(gòu)成的，一個(gè)楊輝三角的顯示圖如圖1所示。

<E：＼2022知網(wǎng)文件＼33＼2xs202233＼Image＼image2.png>

圖1? ?楊輝三角

第一行為k=0的二項(xiàng)式的系數(shù)，第二行是k=1的二項(xiàng)式的系數(shù)，以此類推，第n+1行是k=n的二項(xiàng)式的系數(shù)，楊輝三角所對(duì)應(yīng)的圖形是一個(gè)等腰三角形，兩條腰上的數(shù)值都是1，其余的一般項(xiàng)的數(shù)值滿足：

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

一般項(xiàng)的數(shù)值等于上一行相鄰的兩個(gè)項(xiàng)的數(shù)值之和[2]。

3 程序設(shè)計(jì)

由于楊輝三角中數(shù)值具有規(guī)律性，所以可以通過(guò)計(jì)算機(jī)編程實(shí)現(xiàn)，本研究采用了三種不同的方法實(shí)現(xiàn)了楊輝三角，所采用的編程語(yǔ)言是Java語(yǔ)言，具體Java版本號(hào)為JDK1.9，開(kāi)發(fā)平臺(tái)使用是Eclipse 4.11，項(xiàng)目結(jié)構(gòu)如圖2所示。

<E：＼2022知網(wǎng)文件＼33＼2xs202233＼Image＼image3_1.png>

圖2? ?項(xiàng)目結(jié)構(gòu)圖

項(xiàng)目名稱為Pyanghui，然后在此項(xiàng)目中建立了5個(gè)類，Cmain是主函數(shù)入口類，Cyang1是通過(guò)求組合數(shù)實(shí)現(xiàn)楊輝三角的類，Cyang2是通過(guò)遞歸實(shí)現(xiàn)楊輝三角的類，Cyanghui是通過(guò)隊(duì)列實(shí)現(xiàn)楊輝三角的類，queue為隊(duì)列類[3]。

3.1 組合數(shù)法

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

<E：＼2022知網(wǎng)文件＼33＼2xs202233＼Image＼image4_1.png>

圖3? ?方法1流程圖

具體的java程序代碼如下：

publicclass Cyang1 {

//求階乘n！函數(shù)

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）;}

//求組合數(shù)[Cmn]函數(shù)

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））） ;}

}

//打印組合數(shù)[Cmn]函數(shù)

publicvoid ydisplay（int n，int m）

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

//求n行楊輝三角函數(shù)

publicvoid calyang（int n）

{//j控制行數(shù)

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

{//打印相關(guān)空格

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

System.out.print（""）;

//顯示一行中的所有組合數(shù)

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

{

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

System.out.print（""）;//兩個(gè)數(shù)之間打印空格

}

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

}}

}

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

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

<E：＼2022知網(wǎng)文件＼33＼2xs202233＼Image＼image5.png>

圖4? ?求組合數(shù)遞歸過(guò)程圖

3.2 遞歸法

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

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

public class Cyang2 {

//求組合數(shù)函數(shù)，n為上標(biāo)，m為下標(biāo)

public int caly（int n，int m）

{

//判斷合法情況，上下標(biāo)都是非零整數(shù)，上標(biāo)大于等于下標(biāo)

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

{ if（m==0）

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

return（1）;

else

if（n==m）

//遞歸基2：行等于列時(shí)返回1

return（1）;

Else

//遞歸調(diào)用

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

Else

//不合法時(shí)返回-1

return（-1）;}

//顯示楊輝三角函數(shù)，n為楊輝三角行數(shù)

public void ydisplay2（int n）

{//i控制楊輝三角行數(shù)

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

{//顯示每行的空格

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

System.out.print（""）;

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

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

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

//換行

System.out.println（）;

}}}

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

3.3 隊(duì)列法

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

<E：＼2022知網(wǎng)文件＼33＼2xs202233＼Image＼image6.png>

圖5? ? 求組合數(shù)遞歸過(guò)程圖

左邊三個(gè)虛線方框代表求三行楊輝三角組合值的過(guò)程，右部三個(gè)三角形圖形表示顯示楊輝三角組合值的過(guò)程。初始隊(duì)列為空，顯示1，對(duì)應(yīng)第一行的楊輝三角值；0、1、1、0按順序進(jìn)隊(duì)列，0出隊(duì)列，0不顯示，0加1等于1進(jìn)隊(duì)列，1出隊(duì)列，顯示空格和1，1加1等于2進(jìn)隊(duì)列，1出隊(duì)列，1加0等于1進(jìn)隊(duì)列，0不再出隊(duì)列，此時(shí)第二行顯示完畢，進(jìn)行換行；0進(jìn)隊(duì)列，此時(shí)隊(duì)列為0、1、2、1、0，0出隊(duì)列不顯示，0加1等于1進(jìn)隊(duì)列，然后1出隊(duì)列，顯示空格和1，1加2等于3進(jìn)隊(duì)列，2出隊(duì)列，2加1等于3進(jìn)隊(duì)列，1出隊(duì)列，0加1等于1進(jìn)隊(duì)列，顯示1和空格，0不再出隊(duì)列，此時(shí)第三行顯示完畢，進(jìn)行換行，隊(duì)列中的值為1，3，3，1，0，這是為第四行顯示做準(zhǔn)備的，顯然在顯示第n行楊輝三角值的過(guò)程中，第n+1行的楊輝三角值已經(jīng)求好存儲(chǔ)在隊(duì)列中[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)建隊(duì)列

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（""）;

//換行標(biāo)志0進(jìn)隊(duì)列

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）;//只有隊(duì)首值大于0才繼續(xù)執(zhí)行

System.out.println（）;

}}}}

隊(duì)列類 queue可以通過(guò)自己編寫實(shí)現(xiàn)，也可以使用Java語(yǔ)言中隊(duì)列類進(jìn)行實(shí)現(xiàn)。

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

3.4 算法實(shí)驗(yàn)分析

在Cmain類中使用如下代碼對(duì)這三種算法進(jìn)行運(yùn)行時(shí)間計(jì)算：

long Tbegin=System.nanoTime（）;? ?//獲取算法開(kāi)始時(shí)間，單位為納秒

分別運(yùn)行三種方法；

long Tend=System.nanoTime（）; //獲取算法結(jié)束時(shí)間

System.out.println（"算法運(yùn)行時(shí)間： "+（endTime-startTime）+"ns"）;

在CPU為酷睿5（CORE5）和操作系統(tǒng)為Win10的工作站上分別運(yùn)行三種算法，三種算法的運(yùn)行時(shí)間和對(duì)應(yīng)行數(shù)的關(guān)系如表1所示。

表1? ?算法運(yùn)行時(shí)間和行數(shù)對(duì)照?qǐng)D

[算法

時(shí)間（納秒）

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

通過(guò)表1可以得出隊(duì)列法最優(yōu)，遞歸法的算法效率次之，而組合數(shù)法因?yàn)橐绯龅木壒?，其只能支?到12行的楊輝三角的計(jì)算[7]。

4 結(jié)論

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

本文所介紹的三種算法的運(yùn)行范圍因?yàn)檎麛?shù)溢出的緣故有限，組合數(shù)算法只能求行數(shù)從0到12的楊輝三角，遞歸法和隊(duì)列法只能求行數(shù)從0到29的楊輝三角，運(yùn)行范圍可以考慮通過(guò)字符隊(duì)列和大數(shù)加法進(jìn)行擴(kuò)大，這也是下一步的研究方向[8]。

參考文獻(xiàn)：

[1] 王先東.楊輝三角中的奇數(shù)與偶數(shù)[J].數(shù)學(xué)通報(bào)，2009，48（5）：62-63，66.

[2] 楊明順.楊輝三角的若干性質(zhì)研究[J].渭南師范學(xué)院學(xué)報(bào)，2016，31（4）：9-12.

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

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

[5] 宋鈺.經(jīng)典數(shù)據(jù)結(jié)構(gòu)隊(duì)列的研究和實(shí)現(xiàn)[J].電腦編程技巧與維護(hù)，2019（12）：14-15.

[6] 陳竹云，葉雯.數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2017，13（3）：5-7.

[7] 沈華.數(shù)據(jù)結(jié)構(gòu)課程中棧和隊(duì)列實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)[J].教育教學(xué)論壇，2016（24）：274-276.

[8] 耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，2005.

【通聯(lián)編輯：代影】