登 录
#include<iostream> using namespace std; //辗转相除法求最大公约数 int GCD(int x, int y) { if (x<0 || y<0) { return 0; } if (x<y) { int tmp = 0; tmp = y; y = x; x = tmp; } return (!y)? x:GCD(y , x % y); } //不用取模方式实现 int gcd(int x, int y) { if (x < y) return gcd(y, x); if (y == 0) return x; else return gcd(x - y, y); } //结合上述两种方法的巧妙算法 int GcdPlus(int x, int y) { if (x < y) return GcdPlus(y, x); if (y == 0) return x; else { if (0 == x % 2) { if (0 == y % 2) return (GcdPlus(x >> 1, y >> 1) << 1); else return GcdPlus(x >> 1, y); } else { if (0 == y % 2) return GcdPlus(x, y >> 1); else return GcdPlus(y, x - y); } } } int main() { cout << GCD(30,42) << endl; cout << gcd(42,30) << endl; cout << GcdPlus(42,30) << endl; return 0; }
抱歉!评论已关闭.