分类: C/C++
2006-06-08 10:58:15
1.更相减损法 更相减损法是我国古代数学家求两个正整数的最大公约数的算法。我们以求16和12两个数的最大公约数为例加以说明。用两个较大的数减去较小的数,即:(16,12)--(4,12)--(8,4)--(4,4)。4就是最大的公约数。 2.展转相除法 在我们编程中用的最多方法就是展转相除法了,展转相除法是古希腊求两个正整数的最大公约数的也叫欧几里德算法,用较大的数除以较小的数,结果的余数和被除数构成新的一对数,继续做上面的除法,直到大数被小数求尽,这个较小的数就是最大公约数.以求288和123的最大公约数为例,操作如下: (288,123)--(42,123)--(42,39)--(3,39)则3就是他们的最大公约数。 |