算法分析的数学基础

1、写出求整数最大公因子的欧几里得算法。

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：gcd函数就是用来求(a,b)的最大公约数的。

gcd函数的基本性质：gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

公式：gcd(a,b)=gcd(b,a mod b)

1  // 递归形式
2  int Gcd(int a, int b)
3 {
4 if(b == 0)
5 return a;
6  return Gcd(b, a % b);
7 }

1 //简化形式
2 int gcd(int a, int b)
3 {
4 return b?gcd(b, a%b):a;
5 }
6 /*不能写成int gcd(int a, int b){
7 return b?gcd( a%b,b):a;
8 }*/

 1 // 非递归形式
 2  int Gcd(int a, int b)
 3  {
 4  while(b != 0)
 5  {
 6  int r = b;
 7  b = a % b;
 8  a = r;
 9 }
10 return a;
11  }