韩信点兵问题的神算法

《韩信点兵问题的神算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、韩信点兵问题的神解法定理1：一个数除以a余数x，除以b余数y，a、b互质且a

2、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+

3、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的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。以下介绍一种即使对大数计算也非常有效的方

4、法，无论多大的数，计算量都增加很少。首先证明两个定理：定理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

5、-lk)+x)/((b)mod(a))=(an+x)/b，只要n=n-lk即可。定理5：算式(an+x)/b，当a

6、值不断递归取余，直至其值为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=34

7、7*(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次乘法，三次除法，三次加法，

8、6次减法，6次求余。例4：一个数z除以385余251，除以793余563，求其值。z=793*(385n+251-563)/(793-3