免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3297 | 回复: 17

求多个数的最大公约数!!(请高手指教!!!) [复制链接]

论坛徽章:
0
发表于 2005-12-28 19:30 |显示全部楼层
最近在论坛上看到关于多个数最大公约数的求法,大家见解不一。我没事也做了一个,自我感觉良好。不知道我的算不算是一种新的解法(本人至今未看到过,可能见识短浅吧!)。希望高手能够指点一二。如果您有空,请把更妙的解法写下来,也让我们这些菜鸟见识一下世面。谢谢!!!
如果想赞的,请不要客气,尽情发挥。
如果想骂的,请含蓄点。


  1. #include<stdio.h>
  2. #define N 4
  3. int min(int a[]);
  4. int chan(int a[]);
  5. void main()
  6. {
  7.         int a[N],i,j,t,p[N],q;
  8.         for(i=0;i<N;i++)
  9.                 scanf("%d",a+i);
  10.         t=min(a);
  11.         for(j=t;j>1;j--)
  12.         {
  13.                 for(i=0;i<N;i++)
  14.         p[i]=a[i]%j;
  15.         q=chan(p);
  16.         if(q)
  17.                 {
  18.                         printf("成功,最大公约数为:%d\n",j);
  19.                         break;
  20.                 }
  21.         }
  22.         if(j==1)  printf("不存在最大公约数");
  23. }
  24. int min(int a[])
  25. {
  26.         int i;
  27.         for(i=0;i<N;i++)
  28.                 if(*a>*(a+i))   *a=*(a+i);
  29.                 return *a;
  30. }
  31. int chan(int a[])
  32. {
  33.         int i;
  34.         for(i=0;i<N;i++)
  35.                 if(a[i]!=0)  return 0;
  36.                 return 1;
  37. }
复制代码

论坛徽章:
0
发表于 2005-12-28 19:37 |显示全部楼层
没意思

论坛徽章:
0
发表于 2005-12-28 20:22 |显示全部楼层
不错,如果有算法的说明就更好了!

论坛徽章:
0
发表于 2005-12-28 20:34 |显示全部楼层
帮你改了一下,见笑了:



  1. #include<stdio.h>

  2. int min(int *,int );
  3. int chan(int *,int);

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

  26. }
  27. int min(int a[],int N)
  28. {
  29.         int i;
  30.         for(i=0;i<N;i++)
  31.                 if(*a>*(a+i))   *a=*(a+i);
  32.                 return *a;
  33. }
  34. int chan(int a[],int N)
  35. {
  36.         int i;
  37.         for(i=0;i<N;i++)
  38.                 if(a[i]!=0)  return 0;
  39.                 return 1;
  40. }
复制代码

论坛徽章:
0
发表于 2005-12-28 20:38 |显示全部楼层
原帖由 ly4885806 于 2005-12-28 19:30 发表
                  break;
                }
        }
        if(j==1)  printf("不存在最大公约数");
}



不存在,这个......

论坛徽章:
0
发表于 2005-12-28 20:43 |显示全部楼层
如果我要求10000和9999的最大公约数那不是要循环判断9999次。。。。。

论坛徽章:
0
发表于 2005-12-28 21:03 |显示全部楼层
呵呵 我的程序做的确实不怎么样  有等改进。
谢谢4楼帮我改了一下,长了见识。
大家有意见尽管提呀~~~

论坛徽章:
0
发表于 2006-01-03 09:18 |显示全部楼层
楼主:请大家注意上面的两个程序都是错误的,至于错在哪我还没看出来,请高手指点一下。

论坛徽章:
0
发表于 2006-01-03 09:34 |显示全部楼层

回6楼

当然不需要,只需判断2到min(a,b)的平方数之间的素数即可.俺没看楼主的代码.

论坛徽章:
0
发表于 2006-01-03 23:28 |显示全部楼层
用辗转相除法吧
纯搜索几个大的素数乘出来的数求起来比较费事
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP