欧几里得——最大公约数 GCD

自己对于欧几里得算法的讲解，希望能帮到大家。讲解的可能不是很准确，如有存在错误还请见谅

工具/原料

Codeblocks或其他C++编译器

证明

1、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)

程序实现依据

1、因此程序实现的依据就是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时)]

具体实现

1、递归实现intgcd(inta,int水瑞侮瑜b){if(b==0){//b=0的时候上个调用中的a%b等于零，那么对于上一个调用gcd(a,b)的最大公约数就是b，也就是下一个循环的a，直接返回即可returna;}returngcd(b,a%b);}

2、非递归调用实现intGcd(inta,intb){while(b!=0){　　intr=b;　　b=a%b;　　a=r;}returna;}