/*
 * ==========================================================================
 *
 *       Filename:  euclid.c
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2010年10月17日 16时27分21秒
 *
 * ==========================================================================
 */
#include <stdio.h>
int k = 1;
int euclid(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        ++k;
        return euclid(b, a % b);
}

int fib(int n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}
int main(void)
{
    printf ("最大公约数为%d\n",euclid(1111186,256));
    printf ("lame~定理 256大于%d",fib(k));

    /* 
     *如果Euclid算法需要k步来计算两个数的GCD,那么这两个数之中较小的一个必然
     *大于等于Fibonacci数列的第K项
     */
    return 0;
}

#include <stdio.h>
int euclid(int a,int b)
{
    int temp;
    while (a % b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}

int fib(int n)
{
    int x = 2;
    int result;
    int first = 1;
    int second = 1;
    if (n == 1 || n == 0)
        result = 1;
    while (x <= n) {
        ++x;
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}