牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
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 == 0return 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(1640);
    assert(nGcd 
== 8);

    nGcd 
= gcd2(1640);
    assert(nGcd 
== 8);

    nGcd 
= gcd3(1640);
    assert(nGcd 
== 8);

    system(
"pause");
    
return 0;
}

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


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