辗转相除法又名广义欧几里得除法,是用来求解两个数的最大公约数的最佳算法之一。
算法原理:若a除以b的余数为r , 则有 (a , b) = ( b ,r ) ((a,b)表示a和b的最大公约数)
例:169与48的最大公约数求解过程
169 = 48 * 3 + 25 —— (169 , 48) = (48 , 25)
48 = 25 * 1 + 13——(48 , 25) = (25 , 13)
25 = 13 * 1 + 12
13 = 12 * 1 + 1
12 = 1 * 12 + 0——(12 , 1 ) = 1
故最大公约数为 1
下面是C++实现的算法,使用的递归算法
#include <iostream>#include <conio.h>using namespace std;int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}int main(){cout << gcd(169, 48) << endl;_getch();return 0;}
,旁观者的姓名永远爬不到比赛的计分板上。