自己对于欧几里得算法的讲解，希望能帮到大家。讲解的可能不是很准确，如有存在错误还请见谅
工具/原料
Codeblocks或其他C++编译器
证明
gcd(a,b)=gcd(b,a%b)证明不妨假设 a>b则a=k*b+r①因为gcd是a、b的最大公约数，所以可以设a=gcd(a,b)*m②，b=gcd(a,b)*n③联立上面的三个式子得gcd(a,b)*m=k*gcd(a,b)*n+r,整理得r=k*gcd(a,b)*n-gcd(a,b)*m,提取公因式得r=gcd(a,b)(n*k+m)又因为r=a-k*b=a%b,所以gcd(a,b)=gcd(a,a%b)=gcd(b,a%b)END
程序实现依据
因此程序实现的依据就是gcd(a1,b1)=gcd(b1,a1%b1)=gcd(a2,b2)=................=gcd(an-1,bn-1)=bn-1 (an-1%bn-1=0时) [或=gcd(an,bn)=an (bn=0时)]END
具体实现
1
递归实现int gcd(int a, int b) { if (b == 0) {//b=0的时候上个调用中的a%b等于零，那么对于上一个调用gcd(a,b)的最大公约数就是b，也就是下一个循环的a，直接返回即可 return a; } return gcd(b, a % b);}
2
非递归调用实现int Gcd(int a, int b) { while (b != 0) { int r = b; b = a % b; a = r; } return a;}
上一篇：怎么判断磁场方向是点还是叉
下一篇：构图和曝光的几种方法