斐波那契数列和公约数算法

     前几天看了《编程之美》，感觉被华丽的bs了，上面的一些发散思维的面试题给我很大感触。一道题可从几个不同的角度进行思考，对应于不同的解题方法和算法复杂度。书中有关于斐波那契数列和公约数的算法，上面用到了几种我没有想到的方法，结合书上的算法，我给出了下面的几种解答。

/* 求最小公倍数 */
int get_mcm(int a, int b)
{
    int tmp;

    if (a < b)
        return get_mcm(b, a);

    tmp = a;
    while (tmp%b)
        tmp += a;

    return tmp;
}

/* 求最大公约数
    欧几里德-辗转求余法
    若x>y, get_mcd(x, y)=get_mcd(y, y%x)
*/
int get_mcd2(int a, int b)
{
    if (a < b)
        return get_mcd2(b, a);

    int tmp;
    while (tmp=a%b)
    {
        a = b;
        b = tmp;
    }

    return b;
}

/* 《编程之美》上的解法
    若x>y, get_mcd(x, y)=get_mcd(x-y, y)
*/
int get_mcd(int a, int b)
{
    if (a < b)
        return get_mcd(b, a);

    if (0 == b)
        return a;
    else
    {
        if (a&0x1)/* x为奇数 */
        {
            if (b&0x1)
                return get_mcd(a-b, b);
            else
                return get_mcd(a, b>>1);
        }
        else/* x为偶数 */
        {
            if (b&0x1)
                return get_mcd(a>>1, b);
            else
                return get_mcd(a>>1, b>>1)<<1;
        }
    }
}

/* 斐波那契数列 1,1,2,3,5,8,13,...


   递归求解


*/
int Fibonacci2(size_t n)
{
    if ( n==1 || n==2)
        return 1;

    return Fibonacci2(n-1) + Fibonacci2(n-2);
}

/* 斐波那契数列
    《编程之美》上使用Fibanacci通项的O(1)解法
     F(n)是离(golden_ratio^n)/sqrt(5)最近的整数
    @refer
 */
int Fibonacci(size_t n)
{
    const double sqrt5 = 2.236068; /*sqrt(5)*/
    const double golden_ratio = (1+sqrt5)/2;
    return (int)floor( pow(golden_ratio, n)/sqrt5 + 0.5 );
}