（二）c语言百题趣味题之--欧几里德算法

（二）c语言百题趣味题之–欧几里德算法

---

背景：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数，应用领域有数学和计算机两个方面。

---

算法：

E:设两个正整数m,n，且已知m>n

E1:令r=m%n(’%'代表取余)

E2:若r=0(即n整除m)，结束运算，n即为结果

E3:否则令m=n，n=r，并返回步骤E1

---

代码：

非递归方法：

#include<stdio.h> unsigned int Gcd(unsigned int M,unsigned int N) { unsigned int Rem; while(N > 0) { Rem = M % N; M = N; N = Rem; } return M; } int main(void) { int a,b; scanf("%d %d",&a,&b); printf("the greatest common factor of %d and %d is ",a,b); printf("%d\n",Gcd(a,b)); return 0; }

---

递归方法：

#include<stdio.h> int Gcd(int a, int b) { if (a%b==0) return b; else return Gcd(b, a%b); } int main() { int a, b; scanf_s("%d %d", &a, &b); printf("the greatest common factor of %d and %d is ", a, b); printf("%d\n", Gcd(a, b)); return 0; }

---

结束语：

以上代码都特别简单并且实现起来也不复杂，但是如果使用递归的方法可以大大简化代码量，关于使用递归的思路解决问题需要多多练习。