最大公约数问题？求助！！！ - 编程论坛

#2

pangding2010-08-08 23:52

x=(x+y+fabs(x-y))/2;
y=(x+y-fabs(x-y))/2;

这两句是干什么用的？

#3

pangding2010-08-08 23:56

哦，是为了让 x 是两个数的较大者是吧？

其实不用这么写，小数除以大数的余数还是小数，所以如果 x 小的话，进循环里之后。

r = 7 % 8 （7 % 8 还是 7）
然后 x = y; y = r; 就能把两个数换过来，如果本来 x 就大，就相当于做了一次辗转相除了。

不过我没看出来你这个运行的为什么不对，你自己调试一下唄～～

#4

ragnaros2010-08-09 09:11

楼上说的很对！
x=(x+y+fabs(x-y))/2; //这里如果x<y，那么x=y，也就是说如果输入7 8，经过这条语句x被赋值为8
y=(x+y-fabs(x-y))/2; //这里y开始是等于8，而x经过上条语句也被赋值为8，所以y还是等于8
也就是说这两条语句一执行，当x<y时，x和y都被赋值为它们中较大的那个数，也就是求两个较大数的公约数，结果还是较大数本身。

程序代码：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int x,y;
    cout<<"please enter two integer numbers:";
    cin>>x>>y;
    //x=(x+y+fabs(x-y))/2;
    //y=(x+y-fabs(x-y))/2;
    int r;
    do
    {
        r=x%y;
        x=y;
        y=r;
    }
    while(r);
    cout<<"The common denominator is: "<<x<<endl;
    return 0;
}

注释掉这两句就没问题了。

#5

towhee2010-08-09 10:48

楼上说的很对！
x=(x+y+fabs(x-y))/2;
y=(x+y-fabs(x-y))/2;
第一句的结果改变了x的值，违背了第二句的原意。
单就这两句来说，可以增加一个中间变量来将x和y对调。

#6

Incomplete2010-08-09 13:36

回复 3楼 pangding

谢谢！看来不能乱用max=(a+b+fabs(a-b))/2;和min=(a+b-fabs(a-b))/2;这个公式。
我写了个递归的：
#include<iostream>
using namespace std;
int GCD(int x,int y)
{
    if(x%y==0)
        return y;
    return GCD(y,x%y);
}
int main()
{
    int x,y;
    cout<<"please enter two integer numbers:";
    cin>>y>>x;
    cout<<"The common denominator is: "<<GCD(x,y)<<endl;
    return 0;
}

[ 本帖最后由 Incomplete 于 2010-8-9 13:45 编辑 ]

#7

pangding2010-08-10 01:20

还有一个小问题忘了说了，在做第一次除法之前，得看一下 y 是不是 0，要不然是会出错的。
最简捷的写法可能是像下面这样：

程序代码：

int gcd(int a, int b)
{
    while (b) {
    int t = a%b;
        a = b;
        b = t;
   }
   return a;
}

这样 b 是零的时候是直接 return a，可以省去判断。