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

利用可变循环求多元一次不定方程非负整数解 利用可变循环求多元一次不定方程非负整 数解 第19卷 V01.19 第11期 No.11 电子设计 ElectronicDesignEngineering 2011年6月 Jun.2011 利用可变循环求多元一次不定方程非负整数解 詹艳艳 (绍兴市城市建设档案馆浙江绍兴312000) 摘要:为快速,有效地求解多元一次不定方程的非负整数解集,通过反复实验,对传统求解进行了改进,提出了 一 种可变式循环遍历算法(VCE算法).该算法在传统循环算法的基础上,运用两个剪枝策略,大大提高了算法的运算 效率.可以在较短时间内正确给出多元一次不定方程的非负整数解集.实验结果明,该算法通用性较强,可用于求 解任意元一次不定方程. ;循环界值 关键词:可变式循环;不定方程;解集 中图分类号:TP39文献标识码:A文章编号:1674—6236(2011)Il一0ll0-02 Solvingthenon-nagativeintegerssolutionsetoflinearmultivariateindefinite equationbasedonVariableCyclic ZHANYah—yan (ShaoxingUrbanDevelopmentArchives,Shaoxing312000,China) Abstract:Inordertosolvethenon— nagativeintegerssolutionsetoflinearmultivariateindefiniteequationquicklyand effectively,throughrepeatedlyexperiment,allarithmeticnamedVariableCyclicErgodicArithmetic(VCEArithmetic)isput forward.Thisarithmeticisbasedontraditionalcyclicarithmetic,itusestwopruningstrategytoincreasetheefficiencyof calculationbyalargemarsin,itcansirethecorrectnon-nagativeintegerssolutionsetoflinearmultivariateindefinite equationinashortertime,andtheexperimentalresultindicatesthatthisarithmetichasastronguniversality,itcanbeused tosolvethelinearindefiniteequationwithanymoreunknows. Keywords:VariableCyclic;indefiniteequation;solutionset;loopcriticalvalue 多元一次不定方程具有无穷多解.但其非负整数解集却 是确定的.且更具有现实意义.着名的"百钱买百鸡"问题便 是求解多元一次不定方程非负整数解的一个典型应用.再 如,手持50元钱去超市购物,得知苹果1元一斤,橘子1.5元 一 斤,葡萄2.6元一斤,如何购买这几种水果使5O元钱刚好 花完.亦是该问题的一个特解.多年来,已经有很多学者对这 个古老的命题做了研究【l-61,这些研究大多从数学理论的角 度人手,关注的是其通解[2-31,特解[31及解的个数It,6】求法,但对 如何遍历其解集的算法却提及不多.笔者从算法角度人 手,基于利用循环算法解决此类问题的传统思维加以改进, 提出了一种可变式循环遍历算法(VCE),该算法可以在较 短的时间内给出多元一次不定方程的非负整数解集及解 的个数. 1相关定义 为了更好地对可变式循环遍历算法(VCE)的算法思想 及其在求解多元一次不定方程过程中的算法流程进行解释 .先将本文涉及到的相关定义约定如下: 定义1多元一次不定方程 篓其中,1,2,…,n(i,j为正整数,且1??m.1??n); 2可变式循环遍历算法(VCE算法) 收稿日期:2011-03—16稿件编号:201103089 作者简介:詹艳艳(1981一),女,浙江绍兴人.硕士,工程师.研究方向:不定方程,模式 识别,人工智能,数据挖掘,计算机应用. - 110- 詹艳艳利用可变循环求多元一次不定方程非负整数解 多元一次不定方程0l+a2x2+…+=的值是固定的,因 此,利用传统循环算法会在求解过程中进行大量不必要的运 算,降低运算效率.充分考虑到这一问题,对传统循环算法进 行改进,提出了一种可变式循环遍历算法(以下简称VCE算 法).该算法在每次循环开始之前,都会修改本轮循环的最大 循环界值(如图2中表达式(1)所示),从而缩减每一轮循环 的循环次数.达到减少整个算法时间复杂度的目的. 图1传统循环遍历算法示意图 Fig.1Schematicdiagramof traditionalcyclicergodicarithmetic 图2VCE算法示意图 Fig.2Schematicdiagramof VariableCyclicErgodicarithmetic 2.2关键算法 算法名称:VCE 输入:多元一次不定方程alxl+;2+…+的元数n, 系数口1,o,2,…,%及值肘 输出:多元一次不定方程口l+口2+…+肘的非负整 数解集及解的个数 算法步骤: 1)intJ=O;,/用以控制循环个数,一般n元方程有n个 循环 2)VCEArithmetic(a,x,N,M,j);,,计算给定n元一次 不定方程的解集,其中数组a,x,数N,M分别用以存储该方 程的系数,解,元数和值 3)staticvoidVCEArithmetic(double口a,int【】x,intN, doubleM,intj) finti,B; doubleM1; if(j<N-1) {B=Convert.ToInt32(M,a嘲);…………(剪枝1) j=j+1; for(i=O;i<=B;i++) {x[j-1】=i; M1=M—a【j-1】×x[j-1】; if(M>=O) {VCEArithmetic(a,x,N,M1,j);}}}/,调用循环计算 下一个x的取值 elseif(j==N-1) {x,订=Convert.Toht32(M/】); if(aIj】×xlj】:=M)………………………(剪枝2) {Num=Num+1;,,用于统计,l元一次不定方程的解 的个数 stringResult="": for(intk=O;k<N;k++) {Result=Result+x[k]+"";} SWOutput.WriteLine(Result);,,输出该方程的其中一组 解}】} 4)SWOutput.WriteLine(Num);,/输出该方程的解的个数 3结束语 笔者在传统循环算法的基础上.采用了两个剪枝策略 (如本文2.2关键算法的算法步骤中所标识).其中,剪枝l通 过修改每一轮循环的最大循环界值达到缩减循环的效果.而 剪枝2则通过计算本轮循环中是否有符合方程的解.直 接将该轮循环的算法复杂度降为线性.因此,笔者提出的可 变式循环遍历算法(VCE),不仅能够达到预期效果,准确地 运算出元一次不定方程的解集及解的个数,而且通过两个 剪枝策略,大大减小了算法的时间复杂度,提高了运算效率, 达到了事半功倍的效果.且本算法每次运算的一次不定方程 的元数和系数由用户自由输入.因而具有较强的通用性. 参考文献: [1】杨梅.一类多元一次不定方程的正整数解的组数问题【J】. 郧阳师范高等专科学校,2009,29(3):39—40. YANGMei.Ontheclassnumberofpositiveintegersolution ofmulti-headlineardiophantineequation[J】.JournalofTun— yangTeachersCollege,2009,29(3):39-40. [2】晏林.整数多元一次不定方程的矩阵解法与程序设计【J】.云 南师范大学,2003,23(6):8-11. YANLin.Matrixsolutionofintegralindefiniteequationof firstdegreeanditsprogramcomposition[J].JournalofYunnan NormalUniversity,2003,23(6):8-11. 【3】王凯成.n元一次不定方程解法新论阴.数学通报,2002(2): 38-39. WANGKai??cheng.ThenewsolutionofN-variableslinearin-? definiteequation[J].MathGeneralReport,2002(2):38—39. f41李汝垣.解多元一次不定方程纽的减小系数法及其在程 序设计上的应用[J].中国教育导刊,2005(11):75_76. URu.yuan.Solvelinearmultivariateindefiniteequationset bydecreasemodulusandit'Sapplyofprogramdesign【J]. ChinaEducationLeadPublish,2005(11):75—76. 【5】郭秀琼.不定方程整解的几个借用【J】.攀枝花学院, 20o5,22(6):81—83. GUOXiu-qiong.Severalborrowofindefiniteequationintegers solution【J].JournalofPanzhihuaUniversity,2005,22(6): 81—83. [6]张炳汉.关于不定方程整数解计数问题的讨论【J].天中学 刊,2oo1,16(5):l一3. ZHANGBing—han.Thediscussionontheenumerationques— tionoftheintegersolutionfortheindeterminateequation【J】. JournalofTianzhong,2001,16(5):1-3. 一 1l1一