用递归求最大公约数，急

诸葛暗

第一个算法我想用递归实现辗转相除法求最大公约数，可是怎么返回当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

第二问效果截图：


代码如下：

1. #include <stdio.h>
   
2. #include<math.h>
   
3. 
   
4. 
   
5. //第二个算法设两个整数为x、y   
   
6. //如果x=y，则最大公约数与x值（y值）相同；
   
7. //如果x>y，则最大公约数与x-y和y的最大公约数相同；
   
8. //如果x<y，则最大公约数与x和y-x的最大公约数相同。
   
9. //结果为1的话，那么原来的两个数是互质数
   
10. int func(int x,int y)
    
11. {
    
12.         if(x==y)
    
13.         {
    
14.                 return x;
    
15.         }
    
16.         else if(x>y)
    
17.         {
    
18.                 return func(x-y,y);
    
19.         }
    
20.         else
    
21.         {
    
22.                 return func(x,y-x);
    
23.         }
    
24. }
    
25. 
    
26. void main ()
    
27. {
    
28.         printf("4,8最大公约数为：%d\n",func(4,8));
    
29.         printf("8,16最大公约数为：%d\n",func(8,16));
    
30.         printf("8,19最大公约数为：%d\n",func(8,19));
    
31.         printf("1515,600最大公约数为：%d\n",func(1515,600));
    
32. }
    
33. 
    

复制代码

诸葛暗

我在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. //用递归求最大公约数
   
2. //结果为1的话，那么原来的两个数是互质数
   
3. int divide(int a,int b)
   
4. {
   
5.         int n=a>b?a%b:b%a;//获取大数除小数的余数
   
6.         if(0==n)
   
7.         {
   
8.                 return a>b?b:a;//返回除数
   
9.         }
   
10.         else
    
11.         {
    
12.                 return divide(n,a>b?b:a); //辗转相除
    
13.         }
    
14. }
    
15. 
    
16. 
    
17. int main(int argc, char* argv[])
    
18. {
    
19.         printf("4,8最大公约数为:%d\n",divide(4,8));
    
20.         printf("8,16最大公约数为:%d\n",divide(8,16));
    
21.         printf("8,19最大公约数为:%d\n",divide(8,19));
    
22.         printf("1515,600最大公约数为:%d\n",divide(1515,600));
    
23.         return 0;
    
24. }

复制代码

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

                               
登录/注册后可看大图

第二问效果截图：

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

卧室不要床

用递归求最大公约数