独孤小梦 发表于 2008-7-21 14:22

请问下求两个数的最大公约数怎么弄?谢谢!

谢谢啊!问题如下:请问下求两个数的最大公约数怎么弄?谢谢!
这里不清楚怎么弄!思考了好一会,还是没能写出程序来!

yejingx 发表于 2008-7-21 14:36

int GCD(int a, int b)
{
   if(b == 0) return a;
   else return GCD(b, a%b);
}

int LCM(int a, int b)
{
   return a*b/GCD(a,b);
})

独孤小梦 发表于 2008-7-21 16:44

可否加个注释什么的!谢谢啊!

独孤小梦 发表于 2008-7-21 18:04

自己顶起来＾

zhangzhongxu 发表于 2008-7-22 07:16

s1:输入m,n
s2:若m>n,则返回s3,否则m=n
s3:m/n的余数为r，若r=0则n为最大公约数，否则返回s4
s4:m=n,n=r,返回s3
s5:输出最大公约数n

YuriGagarin 发表于 2008-7-22 10:25

这个问题的关键，我想应该是楼主是否清楚：
　　最大公约数的定义？！

　　如果不清楚，建议百度！

ams87 发表于 2008-7-22 10:44

错在那里???

冒似真的不晓得错在那里...

#include "stdio.h"
main()
{int a,b,c,n;
        scanf("%d,%d",&a,&b);
        if (a>b)
           for(n=b;n>1;--n)
             { if(a/n==0&&b/n==0)
                printf("%d\n",n);
                }
        else
           for(n=a;n>1;--n)
             { if(a/n==0&&b/n==0)
              printf("%d\n",n);
               }
}

countryroad 发表于 2008-7-22 10:50

//利用递归求最大公约数 ，此算法好好理解
int GCD(int a, int b)
{
   if(b == 0) return a;
   else return GCD(b, a%b);
}

//求最小公倍数，用到最大公约数的返回值
int LCM(int a, int b)
{
   return a*b/GCD(a,b);
})

guoxiaoling 发表于 2008-7-22 11:34

#include "stdio.h"
main()
{int a,b,c,n;
    scanf("%d,%d",&a,&b);
    if (a>b)
       for(n=b;n>1;--n)
         { if(a/n==0&&b/n==0)
            {printf("%d\n",n);
              break;      
                }
           }
      else
       for(n=a;n>1;--n)
         { if(a/n==0&&b/n==0)
             {printf("%d\n",n);
              break;
              }
          }
}

崔园园 发表于 2008-7-22 20:02

这是一个简单的算法,请找一个例子走一遍程序

#include <stdio.h>
void main()
{int a,b,d;
scanf("%d,%d",&a,&b);
if(a>b)
d=div(a,b);
else
d=div(b,a);
printf（"a=%d,b=%d\n",a,b);
printf("d=%d");
}
int div(int a,int b)
{int r;
do
{r=a%b;a=b;b=r;}
while(r!=0);
return a;}

崔园园 发表于 2008-7-22 20:03

这是一个简单的程序,请找一个例子走一遍程序

独孤小梦 发表于 2008-7-22 21:07

还真不知道最大公约数的定义^
最近系统中毒,刚重装,郁闷!谢谢大家啊!

demonhack 发表于 2008-7-23 00:23

我不想说什么了…………
其实这是个小学问题……
最大公约数指几个数除了1以外最大的约数…………
中国有个很老的算法，算最大公约数的
叫更相减
高中学算法里有…………[tk13]

sam1119 发表于 2008-7-23 11:01

回复 10# 崔园园 的帖子

scanf("%d,%d",&a,&b);

"%d，%d"多了个逗号～～～

卧龙孔明 发表于 2008-7-23 16:23

easy...

hundnn 发表于 2008-7-23 16:30

[quote][bo][un]countryroad[/un] 在 2008-7-22 10:50 的发言：[/bo]

//利用递归求最大公约数 ，此算法好好理解
int GCD(int a, int b)
{
   if(b == 0) return a;
   else return GCD(b, a%b);
}

//求最小公倍数，用到最大公约数的返回值
int LCM(int a, int b)
{
   retur ... [/quote]
不错不错

xiaomengxia2008 发表于 2008-7-23 16:47

回复 1# 独孤小梦 的帖子

参考下面的程序: 求两个正整数的最大公约数和最小公倍数.
main()
{
　int a,b,num1,num2,temp;
　printf("please input two numbers:\n");
　scanf("%d,%d",&num1,&num2);
　if(num1<num2)
　{ temp=num1;
　　num1=num2;　
　　num2=temp;
　}
a=num1;b=num2;
while(b!=0)/*利用辗除法，直到b为0为止*/
　{
　　temp=a%b;
　　a=b;
　　b=temp;
　}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);
}

卧龙孔明 发表于 2008-7-23 16:56

[code]
int gcd(int x,int y)
{
    return x?gcd(y%x,x):y;
}
[/code]

mqh21364 发表于 2008-7-23 16:58

欧几里德算法。

百度一下，你就知道。

coming 发表于 2008-7-23 17:30

恩 我开始写这个程序的时候是这样想的 就是随便取两个数里面的一个数 然后递减 比如说有
a b两个数 就取a 赋给c 然后c--,直到（a%c&&b%c==0）就可以求出来了

不过然后我看书说有个欧几里德算法 很优 我不太记得了~~~

页: [1] 2

编程论坛