Chinaunix

标题: 求多个数的最大公约数！！（请高手指教！！！） [打印本页]
作者: ly4885806    时间: 2005-12-28 19:30
标题: 求多个数的最大公约数！！（请高手指教！！！）
最近在论坛上看到关于多个数最大公约数的求法，大家见解不一。我没事也做了一个，自我感觉良好。不知道我的算不算是一种新的解法（本人至今未看到过，可能见识短浅吧！）。希望高手能够指点一二。如果您有空，请把更妙的解法写下来，也让我们这些菜鸟见识一下世面。谢谢！！！
如果想赞的，请不要客气，尽情发挥。
如果想骂的，请含蓄点。


  2. #include<stdio.h>
  3. #define N 4
  4. int min(int a[]);
  5. int chan(int a[]);
  6. void main()
  7. {
  8.         int a[N],i,j,t,p[N],q;
  9.         for(i=0;i<N;i++)
  10.                 scanf("%d",a+i);
  11.         t=min(a);
  12.         for(j=t;j>1;j--)
  13.         {
  14.                 for(i=0;i<N;i++)
  15.         p[i]=a[i]%j;
  16.         q=chan(p);
  17.         if(q)
  18.                 {
  19.                         printf("成功，最大公约数为：%d\n",j);
  20.                         break;
  21.                 }
  22.         }
  23.         if(j==1)  printf("不存在最大公约数");
  24. }
  25. int min(int a[])
  26. {
  27.         int i;
  28.         for(i=0;i<N;i++)
  29.                 if(*a>*(a+i))   *a=*(a+i);
  30.                 return *a;
  31. }
  32. int chan(int a[])
  33. {
  34.         int i;
  35.         for(i=0;i<N;i++)
  36.                 if(a[i]!=0)  return 0;
  37.                 return 1;
  38. }
复制代码
作者: 圆点坐标    时间: 2005-12-28 19:37
没意思
作者: dbcat    时间: 2005-12-28 20:22
不错,如果有算法的说明就更好了!
作者: dbcat    时间: 2005-12-28 20:34
帮你改了一下,见笑了:



  2. #include<stdio.h>

  4. int min(int *,int );
  5. int chan(int *,int);

  7. main()
  8. {
  9.         int *a,i,j,t,*p,q,N;
  10.         scanf("%d",&N);
  11.         puts("\n");
  12.         a=(int *) malloc (N*sizeof(int));
  13.         p=(int *) malloc (N*sizeof(int));
  14.         for(i=0;i<N;i++)
  15.                 scanf("%d",a+i);
  16.         t=min(a,N);
  17.         for(j=t;j>1;j--)
  18.         {
  19.                 for(i=0;i<N;i++)
  20.         p[i]=a[i]%j;
  21.         q=chan(p,N);
  22.         if(q)
  23.                 {
  24.                         printf("成功，最大公约数为：%d\n",j);
  25.                         break;
  26.                 }
  27.         }
  28.         if(j==1)  printf("不存在最大公约数");

  30. }
  31. int min(int a[],int N)
  32. {
  33.         int i;
  34.         for(i=0;i<N;i++)
  35.                 if(*a>*(a+i))   *a=*(a+i);
  36.                 return *a;
  37. }
  38. int chan(int a[],int N)
  39. {
  40.         int i;
  41.         for(i=0;i<N;i++)
  42.                 if(a[i]!=0)  return 0;
  43.                 return 1;
  44. }
复制代码
作者: win_hate    时间: 2005-12-28 20:38
原帖由 ly4885806 于 2005-12-28 19:30 发表
                  break;
                }
        }
        if(j==1)  printf("不存在最大公约数");
}



不存在，这个......
作者: hisher    时间: 2005-12-28 20:43
如果我要求10000和9999的最大公约数那不是要循环判断9999次。。。。。
作者: ly4885806    时间: 2005-12-28 21:03
呵呵 我的程序做的确实不怎么样  有等改进。
谢谢4楼帮我改了一下，长了见识。
大家有意见尽管提呀~~~
作者: ly4885806    时间: 2006-01-03 09:18
楼主：请大家注意上面的两个程序都是错误的，至于错在哪我还没看出来，请高手指点一下。
作者: soul_of_moon    时间: 2006-01-03 09:34
标题: 回6楼
当然不需要,只需判断2到min(a,b)的平方数之间的素数即可.俺没看楼主的代码.
作者: frog_skywalker    时间: 2006-01-03 23:28
用辗转相除法吧
纯搜索几个大的素数乘出来的数求起来比较费事
作者: RobinHoo    时间: 2006-01-04 00:25

  2. #include<stdio.h>
  3. main()
  4. {
  5.         unsigned short m,n,l;
  6.         scanf("%u,%u",&m,&n);
  7.         printf("The greatest common divisor of %u and %u is ",m,n);
  8.         if (m<n)
  9.         {
  10.                 l=m;
  11.                 m=n;
  12.                 n=l;
  13.         }
  14.         while (m%n!=0)
  15.         {
  16.                 l=m;
  17.                 m=m%n;
  18.                 n=l;
  19.         }
  20.         printf("%u\n",n);


  23. }
复制代码
作者: Yarco    时间: 2006-01-04 07:56
提示: 作者被禁止或删除 内容自动屏蔽
作者: soul_of_moon    时间: 2006-01-04 08:03
标题: 回11楼
这个行吗?!
作者: ly4885806    时间: 2006-01-05 16:25
楼主：本人开始列出的程序有些错误，经过我的不懈努力，终于找到错误并改了过来。关于注释大家可千万别看，那是我为了让女朋友看懂而弄的（呵呵，俺女朋友比较笨），在座的还用不着看。
哪位能说出的原来程序出错原因，就请说一下吧！
#include<stdio.h>
#define N 4   //宏定义  这里定义求4（N）个数的最大公约数
int min(int a[]); //用来寻找N个数最小的那一个数 并返回出来
int chan(int a[]); //用来判断一个数组中的元素是否都为0 ，是返回1 否则返回0
void main()
{
        int a[N],i,j,t,p[N],q;
    for(i=0;i<N;i++)
                scanf("%d",a+i);  //输入N个数
    t=min(a);   //找出最小的数
        for(j=t;j>1;j--)
    {
                for(i=0;i<N;i++)
        p=a%j;   //将数组A中的数对J取余 将得到的数分别赋给数组P
        q=chan(p);   //调用函数 判断数组P中的数是否都为0
        if(q)    //用于判断
        {
                        printf("成功，最大公约数为：%d\n",j);
            break;  //因为求最大公约数 所以找到一个立刻退出循环
        }
        }
    if(j==1)  printf("不存在最大公约数");//J=1时 表示没有找出最大公约数
}
int min(int a[])
{
        int i,min=a[0];
    for(i=0;i<N;i++)
                if(min>*(a+i))   min=*(a+i);
                return min;
}
int chan(int a[])
{
        int i;
        for(i=0;i<N;i++)
                if(a!=0)  return 0;  //函数中只要执行了一个RETURN后 函数便立刻结束
                return 1;
}
作者: ly4885806    时间: 2006-01-05 16:30
大家注意：十一楼的程序错了
作者: jeffshia    时间: 2006-01-05 16:43
efficiency!!
作者: RobinHoo    时间: 2006-01-05 17:19
不好意思，我给出的是以辗转相除法两个数的代码。另任何两个正整数都有最大公约数的，最小为一。还有解决这样的问题数学模型要好，比如找一个数的因子，只要找比sqrt(N)范围的可整除的数即可。另外，N个数的最大公约数可以两两相求一次循环就可以了。
作者: win_hate    时间: 2006-01-05 20:18
http://bbs.chinaunix.net/viewthr ... p;extra=&page=1



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2