韩信点兵问题的神算法.doc

韩信点兵问题的神解法定理1：一个数除以a余数x，除以b余数y，a、b互质且ab，求这个数的最小值。设这个数为z，则z=b(an+x-y)/(b-a)+y (1)或z=a(bn+x-y)/(b-a)+x (2)其中n为使(bn+x-y)/(b-a)为正整数的最小值。证明：设z=al+x=bm+y 则：al+x-y-am=(b-a)m 所以m=(a(l-m)+x-y)/(b-a)将变量l-m用独立变量n代替：m= (an+x-y)/(b-a)将m代入以上等式得到：z=b(an+x-y)/(b-a)+y同理可以证明等式2定理2：在定理1等式中，0=n=b-a。证明：从定理1等式中可知n=l-m，因为a=m，故n=0假设n=h(b-a)+k，k=b-a 代入以上算式z=b(ah(b-a)+ak+x-y)/(b-a)+y=ahb+b(ak+x-y)/(b-a)，由此可知，n可以取值为k。根据以上两个定理来计算韩信点兵问题，具有两个方面的优点：1、 将两个变量合并成了一个变量，从而只需要尝试一个变量即可。2、 这一个变量的范围被两个除数的值界定，需要尝试的最多次数是确定的。例1：一个数除以9余5，除以13余4，求这个数的最小值列出算式：13*(9n+5-4)/(13-9)+4=13*(9n+1)/4+4 显然能让相除结果为整数的n的最小值为3，代入则得：13*(9*3+1)/4+4=95。例2：一个数除以13余10，除以17余5，求这个数的最小值列出算式：17*(13n+10-5)/(17-13)+5=17*(13n+5)/4+5显然能让相除结果为整数的n的最小值也为3，代入则得：17*(13*3+5)/4+5=192以上算法比传统算法更简便，但依然有缺陷，即如果除数的值比较大时，要获得满足条件的n的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。以下介绍一种即使对大数计算也非常有效的方法，无论多大的数，计算量都增加很少。首先证明两个定理：定理3：在定理1中，z=b(an+x-y)/(b-a)+y，必存在一个m，使得z= b(am+(x-y)mod(a)/(b-a)+y。证明：设x-y=ak+(x-y)mod(a)则：z=b(a(m+k)+(x-y)mod(a)/(b-a)+y，故m=n-k即可。定理4：在算式(an+x)/b中，必存在一个m，使得(am+x)/(b)mod(a)= (an+x)/b。证明：设k=(an+x)/b，b=al+(b)mod(a)则：an+x=bk=alk+k(b)mod(a)所以k=(a(n-lk)+x)/(b)mod(a)= (an+x)/b，只要n=n-lk即可。定理5：算式(an+x)/b，当ab时，必存在一个m使得(an+x)/b=(am+xmod(a)/(bmod(a)。证明：根据定理3(an+x)/b=(al+xmod(a)/b根据定理4(al+xmod(a)/b=(am+xmod(a)/(bmod(a)所以(an+x)/b=(am+xmod(a)/(bmod(a)设m=(an+x)/b，则可以假设z=an+x=bm，则问题转化为：z除以a余x，除以b余0，求z的值。而根据定理5，则可以将算式中的b的值不断递归取余，直至其值为1，而此时n的值则为0。由此实现的算法，最终不需要计算n的值，只需要分母的值递归至1即可，此时满足条件的n的最小值必定是0。以下举例说明算法：例3：一个数z除以347余159，除以362余181，求其值。z=362*(347n+159-181)/(362-347)+181=362*(347n+(-22)mod(347)/15+181=362*(347n+325)/15+181 以下求347n+325的最小值z1，满足：除以347余325，除以15余0，所以其值为：347*(15n-325)/(347-15)+325=347*(15n+(-325)mod(15)/332mod(15)+325=347*(15n+5)/2+325以下求15n+5的最小值z2，满足：除以15余5，除以2余0，所以其值为：15*(2n-5)/(15-2)+5=15*(2n+(-5)mod(2)/13mod(2)+5=15*(2n+1)/1+5分母为1，令n=0，则z2=20，所以z1=347*(z2)/2+325=347*20/2+325=3795所以z=362*z1/15+181=362*3795/15+181=91767经过2次递归计算出结果。共进行3次乘法，三次除法，三次加法，6次减法，6次求余。例4：一个数z除以385余251，除以793余563，求其值。z=793*(385n+251-563)/(793-385)+563=793*(385n+(251-563)mod(385)/408mod(385)+563=793*(385n+73)/23+563以下求385n+73的最小值z1，满足：除以385余73，除以23余0，所以其值为：385*(23n-73)/(385-23)+73=385*(23n+(-73)mod(23)/362mod(23)+73=385*(23n+19)/17+73以下求23n+19的最小值z2，满足：除以23余19，除以17余0，所以其值为：23*(17n-19)/(23-17)+19=23*(17n+(-19)mod(17)/6+19=23*(17n+15)/6+19以下求17n+15的最小值z3，满足：除以17余15，除以6余0，所以其值为：17*(6n-15)/(17-6)+15=17*(6n+(-15)mod(6)/11mod(6)+15=17*(6n+3)/5+15以下求6n+3的最小值z4，满足：除以6余3，除以5余0，所以其值为：6*(5n-3)/(6-5)+3=6*(5n+(-3)mod(5)/1mod(5)+3=6*(5n+2)/1+3分母为1，所以令n=0，则z4=6*2+3=15，所以z3=17*z4/5+15=17*15/5+15=66,所以z2=23*66/6+19=272所以z1=385*z2/17+73=385*272/17+73=6233所以z=793*z1/23+563=793*6233/23+563=215466共经过四次递归计算出结果。共进行5次乘法，5次除法，5次加法，10次减法，10次求余。由此可知，计算量由递归次数决定。设递归次数为n，则乘法、除法和加法的次数为n+1，减法和求余的次数为2(n+1)。从以上两例可以看出，与传统计算方法相比，大大简化。其递归模式可以非常容易用程序实现，而且当除数比较大时，只要最终结果值不大于数据类型的最大值，用程序计算就不会发生溢出。以下给出javascript代码，将以下代码拷贝到一个空白文档，并以.html为后缀名保存文件后，用浏览器打开该文件即可运行（其中：a1为第一个除数，a2为第一个余数，b1为第二个除数，b2为第二个余数）：韩信点兵神器，无论多大的数都能算var count=0;function doCalculate()var a1=parseInt(document.getElementById(devider1).value);var a2=parseInt(document.getElementById(rest1).value);var b1=parseInt(document.getElementById(devider2).value);var b2=parseInt(document.getElementById(rest2).value);var result=calculate(a1,a2,b1,b2);if(result0)document.getElementById(result).value=result;alert(共进行了+count + 次乘法、除法和加法，+count*2 + 次减法和求余);count=0;elsewindow.alert(两个除数不是互质);return;function calculate(a1,a2,b1,b2)if(isRelativelyPrime(a1,b1)=false) return 0;count += 1;var temp=a1;if(a1b1)a1=b1;b1=temp;temp=a2;a2=b2;b2=temp;var newA1=a1;var newA2=getMod(a2-b2,a1);/保证余数大于0var newB2=0;var newB1=(b1-a1)%a1;if(newB1=1)return b1*newA2+b2;return b1*(calculate(newA1,newA2,newB1,newB2)/newB1)+b2;function getMod(x,