题目描述：最大公约数问题
思路：三个思路
(1)gcd(x,y) = gcd(y,x%y);
(2)gcd(x,y) = gcd(y,x-y);
(3)gcd(x,y) = gcd(x/2,y/2)*2;(x,y均被2整除)
1 #include <iostream> 2 #include <queue> 3 #include <climits> 4 #include <algorithm> 5 #include <memory.h> 6 #include <stdio.h> 7 using namespace std; 8 9 static int num_1 = 0; 10 static int num_2 = 0; 11 static int num_3 = 0; 12 int gcd_1(int a,int b) 13 { 14 if(b == 0) 15 { 16 ++num_1; 17 return a; 18 } 19 else 20 { 21 ++num_1; 22 return gcd_1(b,a%b); 23 } 24 } 25 int gcd_2(int a,int b) 26 { 27 if(b == 0) 28 { 29 ++num_2; 30 return a; 31 } 32 if(a < b) 33 { 34 ++num_2; 35 return gcd_2(b,a); 36 } 37 ++num_2; 38 return gcd_2(b,a-b); 39 } 40 int gcd_3(int a,int b) 41 { 42 ++num_3; 43 if(b == 0) 44 { 45 return a; 46 } 47 if(a < b) 48 { 49 return gcd_3(b,a); 50 } 51 if(a % 2 == 0) 52 { 53 if(b % 2 == 0) 54 { 55 return (gcd_3(a>>1,b>>1)<<1); 56 } 57 else 58 { 59 return gcd_3(a>>1,b); 60 } 61 } 62 else 63 { 64 if(b % 2 == 0) 65 { 66 return gcd_3(a,b>>1); 67 } 68 else 69 { 70 return gcd_3(b,a-b); 71 } 72 } 73 } 74 75 int main() 76 { 77 int a = 12; 78 int b = 15; 79 cout<<gcd_1(a,b)<<" "<<gcd_2(a,b)<<" "<<gcd_3(a,b)<<endl; 80 cout<<num_1<<" "<<num_2<<" "<<num_3<<endl; 81 return 0; 82 }