用递归求最大公约数，急
第一个算法我想用递归实现辗转相除法求最大公约数，可是怎么返回当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;
}
*/
第二问效果截图：
代码如下：
#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 static/image/common/back.gif
#include
int divide(int a,int b);
int main()
而且这个代码在c free 下运行确是，我真是郁闷了 哎，我给你例子参考吧（希望给我评下分呀）
效果截图：
代码如下：
//用递归求最大公约数
//结果为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;
}
原理：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是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 static/image/common/back.gif
#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 static/image/common/back.gif
哎，我给你例子参考吧（希望给我评下分呀）
效果截图：
谢谢了，(*^__^*) 我找到错误的原因了，返回值有问题，if(c!=0)
b = divide(b,c);就好，楼下那种方法也对，能不能帮我看下第二个问题呢 仰望天上的光 发表于 2013-11-18 12:17 static/image/common/back.gif
int divide(int a,int b)
{
int c;
{:5_108:}再帮忙看下第二个问题吧 friendan 发表于 2013-11-17 19:15 static/image/common/back.gif
第二问效果截图：
谢谢了，我发现是编译器的问题= = 用递归求最大公约数
页:
[1]