常用算法

1.欧几里得算法

算法描述

⒈ 令r为a/b所得余数（0 ≤ r < b） 若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
(转自百度百科)

代码

unsigned int 
God(unsigned int M ,unsigned int N)
{
    unsigned int Rem; //余数

    while(N)
    {
        Rem = M%N;
        M  =N;
        N = Rem; 
    } 

    return M;
}

算法复杂度O(logN); (详细分析见《数据结构与算法分析（C语言描述）》第23页)；

---

2. 列表内容计算X的N次幂；

bool IsEven(int i)
{
    return (i%2==0);
}

long int
Pow(unsigned int X,unsigned int N)
{
    if(N==0)
        return 1;
    if(N==1)
        return X;
    if(IsEven(N))  //是否为偶数 
        return Pow(X*X,N/2);
    else
        return Pow(X*X,N/2)*X;
}

算法时间复杂度为O(logN);