ZKX's LAB

更相减损法的C语言相关程序 更相减损法的读音

2021-03-18知识155

更相减损法 为什么可以用于求最大公约数呢?即它的原理是什么? 我认为更相减损法的原理就是同余啊.两数X=AP,Y=BPP是最大公约数,A>;B且互素,则BP、(A-B)P同样必有最大公约数P,更相减损,最后必求得1P.

更相减损法为什么可以求出两个数的最大公约数你?数学原理是什么? 举个例子,比如 98和63的最大公约数是7.98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 这样之所以能求出来,是因为假定98和63最大公约数是M 那么98=a*M,63=b*M,a b都是正整数.98-63=35 所以这个差应该是(a-b)M 接下来M就可以看作是求63和35的公约数.那么M为什么又是63和35最大的公约数呢?假设有个数N是63和35最大的公约数而且N大于M,使得63=A*N,35=B*N.那么98=63+35=(A+B)N,也就是说98和63的最大公约数变成了N,这就与一开始矛盾了.于是这样循序渐进地减下去,M一直是2个数的最大公约数,最后可以得出M的值.还有另一种比较容易懂的理解方式.如果要求两个数X,Y的最大公约数T 把X,Y看成由若干个T组成的数.X:T T T T T T T T T…Y:T T T T T…因为那么X-Y是啥意思呢?意思就是X比Y多的T构成的数,这样减的话这个差永远是整数个T,于是一直这样互相减下去,最后减出来肯定是只有一个T(遇到偶数除个2就行了),所以T是多少就浮出水面了.

更相减损法的C语言相关程序 已知两正整数数,求其最大公约数。int GCD(int a,int b){ while(a。b){ if(a>;b)a-=b;else b-=a;} return a;}

#更相减损术的读音#更相减损法的读音

随机阅读

qrcode
访问手机版