#include <stdio.h> //<<九章算术>>更相减损法: 可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。 //以等数约之。 ///第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 //第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。 //则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 //其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 //如98 63,98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 7-7=0 #include <math.h> main() { int a=98,b=63,c; scanf("%d%d",&a,&b); while(【1】) a=a/2,b=b/2; while(【2】) { c=【3】; a=b; b=c; } printf("%d",【4】); getchar(); }
#include <stdio.h> //<<九章算术>>更相减损法: 可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。 //以等数约之。 ///第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 //第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。 //则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 //其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 //如98 63,98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 7-7=0 #include <math.h> main() { int a=98,b=63,c; scanf("%d%d",&a,&b); while(a%2==0 && b%2==0) a=a/2,b=b/2; while((a-b)!=0) { c=abs(a-b); a=b; b=c; } printf("%d",a); getchar(); }
标签:更相,28,35,减损,最大公约数,63,填空,法求 From: https://www.cnblogs.com/xkdn/p/17108091.html