牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

求最大公约数的3个实现

实现代码：
/// 求最大公约数(欧几里德算法/辗转相除法)(递归)
int gcd1(int m, int n)
{
    if (n == 0) return m;
    else return gcd1(n, m%n);
}
/// 求最大公约数(欧几里德算法/辗转相除法)(迭代)
int gcd2(int m, int n)
{
    int r = 0;
    while (n != 0)
    {
        r = n;
        n = m % n;
        m = r;
    }
    return m;
}
/// 求最大公约数(更相减损法)
int gcd3(int m, int n)
{
    while (m != n)
    {
        if (m > n) m -= n;
        else n -= m;
    }
    return m;
}

测试代码：
int _tmain(int argc, _TCHAR* argv[])
{
    int nGcd = gcd1(16, 40);
    assert(nGcd == 8);

    nGcd = gcd2(16, 40);
    assert(nGcd == 8);

    nGcd = gcd3(16, 40);
    assert(nGcd == 8);

    system("pause");
    return 0;
}

posted on 2014-05-27 10:28 杨粼波 阅读(664) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理