编程之美系列(5)

    题目：最大公约数问题

 

    书上给出了三种解法，前两种都是大家常用的方法，第三种方法很奇特，效率也很高

第一种解法是根据公式：f(x,y) = f(y,x%y);如果y=0,则x为最大公约数

#include <stdio.h> 
#include <malloc.h> 
#include <stdlib.h>
#include <string.h>
#include <math.h>

int gcd(int x,int y)
{
    return (!y) ? x : gcd(y,x%y);
    //这段代码展开如下
    
    /*
    if(y == 0)
        return x;
    return gcd(y,x%y);
    */
}


int main()
{
    int x = 20;
    int y = 15;

    int ret = gcd(x,y);
    printf("%d/n",ret);
    system("pause");
    return 0;
}

 

第二种解法是根据公式，f(x,y)=f(x-y,y);当y=0时，x则为最大公约数

源代码如下：

#include <stdio.h> 
#include <malloc.h> 
#include <stdlib.h>
#include <string.h>
#include <math.h>

int gcd(int x,int y)
{
    if(x < y)//保证x>y
        return gcd(y,x);
    if(y == 0)
        return x;
    else
        return gcd(x-y,y);
}


int main()
{
    int x = 20;
    int y = 15;

    int ret = gcd(x,y);
    printf("%d/n",ret);
    system("pause");
    return 0;
}

 

第三种解法是前两种解法的结合：

当x,y均为偶数时，f(x,y)=2*f(x/2,y/2)=2*f(x>>1,y>>1);

当x为偶数，y为奇数时，f(x,y)=f(x>>1,y);

当x为奇数，y为偶数时，f(x,y)=f(x,y>>1);

当x，y都为奇数时，f(x,y)=f(x-y,y);