利用可变循环求多元一次不定方程非负整数解

詹艳艳

（绍兴市城市建设档案馆 浙江 绍兴 312000）

多元一次不定方程具有无穷多解，但其非负整数解集却是确定的，且更具有现实意义。著名的“百钱买百鸡”问题便是求解多元一次不定方程非负整数解的一个典型应用。再如，手持50元钱去超市购物，得知苹果1元一斤，橘子1.5元一斤，葡萄2.6元一斤，如何购买这几种水果使50元钱刚好花完，亦是该问题的一个特解。多年来，已经有很多学者对这个古老的命题做了研究[1-6]，这些研究大多从数学理论的角度入手，关注的是其通解[2-3]、特解[3]及解的个数[1，6]求法，但对如何遍历其解集的算法却提及不多。笔者从算法角度入手，基于利用循环算法解决此类问题的传统思维加以改进，提出了一种可变式循环遍历算法（VCE），该算法可以在较短的时间内给出多元一次不定方程的非负整数解集及解的个数。

1 相关定义

为了更好地对可变式循环遍历算法（VCE）的算法思想及其在求解多元一次不定方程过程中的算法流程进行解释分析，先将本文涉及到的相关定义约定如下：

定义1 多元一次不定方程

a1x1+a2x2+…+anxn=M

其中，a1，a2，…，an，M 为正数，x1，x2，…，xn为非负整数。定义2 多元一次不定方程的非负整数解集

其中，xij=1，2，…，n（i，j为正整数，且 1≤i≤m，1≤j≤n）；

xi1，xi2，…，xin为非负整数，且 a1xi1+a2xi2+…+anxin=M（1≤i≤m）。

定义3 循环界值

设有循环 for（i=A，i＜=B，i++），则 A，B 即为该循环的循环界值，其中A为最小循环界值，B为最大循环界值。

2 可变式循环遍历算法（VCE算法）

2.1 算法思想

求解多元一次不定方程的非负整数解集及其解的个数，首先想到的即是循环遍历算法。但是传统的循环遍历算法，其循环界值是固定的（如图1所示）。……