詹艷艷

（紹興市城市建設檔案館 浙江 紹興 312000）

多元一次不定方程具有無窮多解，但其非負整數(shù)解集卻是確定的，且更具有現(xiàn)實意義。著名的“百錢買百雞”問題便是求解多元一次不定方程非負整數(shù)解的一個典型應用。再如，手持50元錢去超市購物，得知蘋果1元一斤，橘子1.5元一斤，葡萄2.6元一斤，如何購買這幾種水果使50元錢剛好花完，亦是該問題的一個特解。多年來，已經(jīng)有很多學者對這個古老的命題做了研究[1-6]，這些研究大多從數(shù)學理論的角度入手，關注的是其通解[2-3]、特解[3]及解的個數(shù)[1，6]求法，但對如何遍歷其解集的算法卻提及不多。筆者從算法角度入手，基于利用循環(huán)算法解決此類問題的傳統(tǒng)思維加以改進，提出了一種可變式循環(huán)遍歷算法（VCE），該算法可以在較短的時間內(nèi)給出多元一次不定方程的非負整數(shù)解集及解的個數(shù)。

1 相關定義

為了更好地對可變式循環(huán)遍歷算法（VCE）的算法思想及其在求解多元一次不定方程過程中的算法流程進行解釋分析，先將本文涉及到的相關定義約定如下：

定義1 多元一次不定方程

a1x1+a2x2+…+anxn=M

其中，a1，a2，…，an，M 為正數(shù)，x1，x2，…，xn為非負整數(shù)。定義2 多元一次不定方程的非負整數(shù)解集

其中，xij=1，2，…，n（i，j為正整數(shù)，且 1≤i≤m，1≤j≤n）；

xi1，xi2，…，xin為非負整數(shù)，且 a1xi1+a2xi2+…+anxin=M（1≤i≤m）。

定義3 循環(huán)界值

設有循環(huán) for（i=A，i＜=B，i++），則 A，B 即為該循環(huán)的循環(huán)界值，其中A為最小循環(huán)界值，B為最大循環(huán)界值。

2 可變式循環(huán)遍歷算法（VCE算法）

2.1 算法思想

求解多元一次不定方程的非負整數(shù)解集及其解的個數(shù)，首先想到的即是循環(huán)遍歷算法。但是傳統(tǒng)的循環(huán)遍歷算法，其循環(huán)界值是固定的（如圖1所示）。這種算法雖然可以準確得到所有的解，但運算的時間復雜度較長，且由于本問題中，多元一次不定方程a1x1+a2x2+…+anxn=M的值M是固定的，因此，利用傳統(tǒng)循環(huán)算法會在求解過程中進行大量不必要的運算，降低運算效率。充分考慮到這一問題，對傳統(tǒng)循環(huán)算法進行改進，提出了一種可變式循環(huán)遍歷算法（以下簡稱VCE算法）。該算法在每次循環(huán)開始之前，都會修改本輪循環(huán)的最大循環(huán)界值（如圖2中表達式（1）所示），從而縮減每一輪循環(huán)的循環(huán)次數(shù)，達到減少整個算法時間復雜度的目的。

圖1 傳統(tǒng)循環(huán)遍歷算法示意圖Fig.1 Schematic diagram of traditional cyclic ergodic arithmetic

圖2 VCE算法示意圖Fig.2 Schematic diagram of Variable Cyclic Ergodic arithmetic

2.2 關鍵算法

算法名稱：VCE

輸入：多元一次不定方程a1x1+a2x2+…+anxn=M的元數(shù)n，系數(shù) a1，a2，…，an及值 M

輸出：多元一次不定方程a1x1+a2x2+…+anxn=M的非負整數(shù)解集及解的個數(shù)

算法步驟：

1）int j=0；//用以控制循環(huán)個數(shù)，一般n元方程有n個循環(huán)

2）VCEArithmetic （a，x， N， M， j）；//計算給定 n 元一次不定方程的解集，其中數(shù)組a，x，數(shù)N，M分別用以存儲該方程的系數(shù)、解、元數(shù)和值

3）static void VCEArithmetic （double[]a， int[]x， int N，double M，int j）

{int i， B；

double M1；

if（j＜ N-1）

{B=Convert.ToInt32（M/a[j]）； ………… （剪枝 1）j=j+1；

for（i=0； i＜=B； i++）

{x[j-1]=i；

M1=M-a[j-1]× x[j-1]；

if（M ＞=0）

{VCEArithmetic（a， x， N， M1， j）； }}}//調(diào)用循環(huán)計算下一個x的取值

else if（j==N-1）

{x[j]=Convert.ToInt32（M/a[j]）；

if（a[j]×x[j]==M） ……………………… （剪枝2）

{Num=Num+1；//用于統(tǒng)計n元一次不定方程的解的個數(shù)

string Result=""；

for（int k=0；k＜ N；k++）

{Result=Result+x[k]+""；}

SWOutput.WriteLine（Result）；//輸出該方程的其中一組解}}}

4）SWOutput.WriteLine（Num）；//輸出該方程的解的個數(shù)

3 結束語

筆者在傳統(tǒng)循環(huán)算法的基礎上，采用了兩個剪枝策略（如本文2.2關鍵算法的算法步驟中所標識）。其中，剪枝1通過修改每一輪循環(huán)的最大循環(huán)界值達到縮減循環(huán)的效果，而剪枝2則通過計算本輪循環(huán)中是否有符合方程要求的解，直接將該輪循環(huán)的算法復雜度降為線性。因此，筆者提出的可變式循環(huán)遍歷算法（VCE），不僅能夠達到預期效果，準確地運算出n元一次不定方程的解集及解的個數(shù)，而且通過兩個剪枝策略，大大減小了算法的時間復雜度，提高了運算效率，達到了事半功倍的效果，且本算法每次運算的一次不定方程的元數(shù)和系數(shù)由用戶自由輸入，因而具有較強的通用性。

[1]楊梅.一類多元一次不定方程的正整數(shù)解的組數(shù)問題[J].鄖陽師范高等?？茖W校學報，2009，29（3）：39-40.YANG Mei.On the class number of positive integer solution of multi-head linear diophantine equation[J].Journal of Tunyang Teachers College，2009，29（3）：39-40.

[2]晏林.整數(shù)多元一次不定方程的矩陣解法與程序設計[J].云南師范大學學報，2003，23（6）：8-11.YAN Lin.Matrix solution of integral indefinite equation of first degree and its program composition[J].Journal of Yunnan Normal University，2003，23（6）：8-11.

[3]王凱成.n元一次不定方程解法新論[J].數(shù)學通報，2002（2）：38-39.WANG Kai-cheng.The new solution of N-variables linear indefinite equation[J].Math General Report，2002（2）：38-39.

[4]李汝垣.解多元一次不定方程組的減小系數(shù)法及其在程序設計上的應用[J].中國教育導刊，2005（11）：75-76.LI Ru-yuan.Solve linear multivariate indefinite equation set by decrease modulus and it’s apply of program design[J].China Education Lead Publish，2005（11）：75-76.

[5]郭秀瓊.不定方程整解的幾個借用[J].攀枝花學院學報，2005，22（6）：81-83.GUO Xiu-qiong.Several borrow of indefinite equation integers solution[J].Journal of Panzhihua University，2005，22（6）：81-83.

[6]張炳漢.關于不定方程整數(shù)解計數(shù)問題的討論[J].天中學刊，2001，16（5）：1-3.ZHANG Bing-han.The discussion on the enumeration question of the integer solution for the indeterminate equation[J].Journal of Tianzhong，2001，16（5）： 1-3.