用递归求最大公约数，急

诸葛暗

第一个算法我想用递归实现辗转相除法求最大公约数，可是怎么返回当c=0时b的值呢？第二个算法设两个整数为x、y   如果x=y，则最大公约数与x值（y值）相同；
   如果x>y，则最大公约数与x-y和y的最大公约数相同；
   如果x<y，则最大公约数与x和y-x的最大公约数相同。
可是没有实现是肿么回事- -，求指教啊，急................

#include<stdio.h>
int divide(int a,int b);
int main()
{
        int a,b;
       
        while(scanf("%d%d",&a,&b)==2)
    printf("(%d %d)=%d\n",a,b,divide(a,b));
       
        return 0;       
       
}

int divide(int a,int b)
{
        int c;
       
        c=a%b;
        printf("c:%d,a:%d,b:%d\n",c,a,b);
       
        if(c!=0)
        divide(b,c);
        printf("c:%d,a:%d,b:%d\n",c,a,b);
       
        return b;
}
/*
int divide(int a,int b)
{
        if(a>b)
        divide(a-b,b);
       
        else if(a<b)
        divide(a,b-a);
       
        else
        return b;
}
*/

friendan

第二问效果截图：


代码如下：

#include <stdio.h>
#include<math.h>


//第二个算法设两个整数为x、y   
//如果x=y，则最大公约数与x值（y值）相同；
//如果x>y，则最大公约数与x-y和y的最大公约数相同；
//如果x<y，则最大公约数与x和y-x的最大公约数相同。
//结果为1的话，那么原来的两个数是互质数
int func(int x,int y)
{
        if(x==y)
        {
                return x;
        }
        else if(x>y)
        {
                return func(x-y,y);
        }
        else
        {
                return func(x,y-x);
        }
}

void main ()
{
        printf("4,8最大公约数为：%d\n",func(4,8));
        printf("8,16最大公约数为：%d\n",func(8,16));
        printf("8,19最大公约数为：%d\n",func(8,19));
        printf("1515,600最大公约数为：%d\n",func(1515,600));
}

诸葛暗

我在vc下编译#include<stdio.h>
int divide(int a,int b);
int main()
{
        int a,b;
       
        while(scanf("%d%d",&a,&b)==2)
    printf("(%d %d)=%d\n",a,b,divide(a,b));
       
        return 0;       
       
}

int divide(int a,int b)
{
        int c;
       
        c=a%b;
        printf("c:%d,a:%d,b:%d\n",c,a,b);
       
        if(c==0)
        return b;
        else
        {
        divide(b,c);
    printf("c:%d,a:%d,b:%d\n",c,a,b);
   
   
        }                ，输出这个
}

诸葛暗

#include<stdio.h>
int divide(int a,int b);
int main()
{
        int a,b;
       
        while(scanf("%d%d",&a,&b)==2)
    printf("(%d %d)=%d\n",a,b,divide(a,b));
       
        return 0;       
       
}

int divide(int a,int b)
{
        int c;
       
        c=a%b;
       
       
        if(c==0)
        return b;
        else
        {
        divide(b,c);
   
   
   
        }               
}
，俩个代码只是相差两条输出语句啊，怎么最后的返回值就不一样了？？？

诸葛暗

诸葛暗 发表于 2013-11-17 19:49

                               
登录/注册后可看大图

#include
int divide(int a,int b);
int main()

而且这个代码在c free 下运行确是 ，我真是郁闷了

friendan

哎，我给你例子参考吧（希望给我评下分呀）
效果截图：


代码如下：

//用递归求最大公约数
//结果为1的话，那么原来的两个数是互质数
int divide(int a,int b)
{
        int n=a>b?a%b:b%a;//获取大数除小数的余数
        if(0==n)
        {
                return a>b?b:a;//返回除数
        }
        else
        {
                return divide(n,a>b?b:a); //辗转相除
        }
}


int main(int argc, char* argv[])
{
        printf("4,8最大公约数为:%d\n",divide(4,8));
        printf("8,16最大公约数为:%d\n",divide(8,16));
        printf("8,19最大公约数为:%d\n",divide(8,19));
        printf("1515,600最大公约数为:%d\n",divide(1515,600));
        return 0;
}

friendan

原理：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。

例如求1515和600的最大公约数，
第一次：用600除1515，商2余315；
第二次：用315除600，商1余285；
第三次：用285除315，商1余30；
第四次：用30除285，商9余15；
第五次：用15除30，商2余0。
1515和600的最大公约数是15。

注意：
3除2和3除以2是有区别的。
3除2是:2/3
3除以2是:3/2

仰望天上的光

诸葛暗 发表于 2013-11-17 19:49

                               
登录/注册后可看大图

#include
int divide(int a,int b);
int main()

int divide(int a,int b)
{
         int c;
         
        c=a%b;
         
        
        if(c==0)
         return b;
         else
         {
         //divide(b,c);
            return divide(b,c);
     
   
   
         }               
}

诸葛暗

friendan 发表于 2013-11-18 11:42

                               
登录/注册后可看大图

哎，我给你例子参考吧（希望给我评下分呀）
效果截图：

谢谢了，(*^__^*) 我找到错误的原因了，返回值有问题，if(c!=0)
                                                                        b = divide(b,c);就好，楼下那种方法也对，能不能帮我看下第二个问题呢

诸葛暗

仰望天上的光 发表于 2013-11-18 12:17

                               
登录/注册后可看大图

int divide(int a,int b)
{
         int c;

再帮忙看下第二个问题吧

诸葛暗

friendan 发表于 2013-11-17 19:15

                               
登录/注册后可看大图

第二问效果截图：

谢谢了，我发现是编译器的问题= =

卧室不要床

用递归求最大公约数