/*
    求两个正整数m和n的最大公约数可用如下gcd(m,n)公式表示
               m           n=0
    gcd(m,n)= 
               gcd(n,m%n)  n>0
    */
    
#include <stack>    
using namespace std;

typedef stack<int>  ints;
//递归实现 
int gcd(int m,int n)
{
    int  res;
    if(n==0)
        res=m;
    else
        res=gcd(n,m%n);
    return res;
}

//非递归实现 
int gcd2(int m,int n)
{
    int res;
    while(n!=0)
    {
        int t;
        t=m; 
        m=n;
        n=t%n;
    }
    res=m;
    return res;    
}

//用栈实现非递归 
int gcd3(int m,int n)
{
    ints S;
    int res;
    while(n!=0)
    {
        S.push(n);
        S.push(m%n);
        n=S.top();
        S.pop();
        m=S.top();
        S.pop();
    }
    return m;
}

评论