辗转相除法:
1 #include<iostream> 2 using namespace std; 3 int gcd(int a,int b) 4 { 5 return a%b==0 ? b : gcd(b,a%b); 6 } 7 int main() 8 { 9 int a,b; 10 cin>>a>>b; 11 cout<<gcd(a,b); 12 return 0; 13 }
1 int gcd(int a,int b) 2 { 3 return b==0?a:gcd(b,a%b); 4 }
等价于上面的
1 int gcd(int x, int y) 2 { 3 if(y == 0) return x; 4 if(x < y) return gcd(y,x); 5 else return gcd(y, x%y); 6 }
辗转相减法:
1 #include<iostream> 2 using namespace std; 3 int gcd(int a,int b) 4 { 5 if(a>b) 6 { 7 return gcd(a-b,b); 8 } 9 if(a<b) 10 { 11 return gcd(a,b-a); 12 } 13 //if(a==b) 14 return a; 15 } 16 int main() 17 { 18 int a,b; 19 cin>>a>>b; 20 cout<<gcd(a,b); 21 return 0; 22 }
非递归算法
1 int gcd(int x,int y) 2 { 3 int tmp; 4 while(tmp = x%y) 5 { 6 x = y; 7 y = tp; 8 } 9 return y; 10 }