wlbk.net
当前位置:首页 >> 最大公约数C穷举法 >>

最大公约数C穷举法

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

求最大公约数算法:(1)辗转相除法 两整数a和b:① a%b得余数c ② 若c=0,则b即为两数的最大公约数,结束 ③ 若c≠0,则a=b,b=c,再回去执行①(2)相减法 两整数a和b:① 若a>b,则a=a-b ② 若a<b,则b=b-a ③ 若a=b,则a(或b)即为两数

楼主要求的穷举法: #include void main(void) { int x,y,t; scanf("%d%d",&x,&y); if(x void main(void) { int x,y,r; scanf("%d%d",&x,&y); r=x%y; while(r) {x=y;y=r;r=x%y;} printf("%d\n",y); }

两个数m,n利用穷举求最大公约数,只要遍历2到m即可 int gcd(int m, int n) { int i, t = -1; for(i = 2; i<m; i++) //遍历 if(m%i==0 && n%i==0)t = i; //t记录最大值 return t; }

#include<stdio.h> int main() { int a,b,i; scanf("%d %d",&a,&b); if(a>b){i=a;a=b;b=i;} for(i=a;i>1;i--) if(a%i==0&&b%i==0)break; printf("最大公约数是:%d\n",i); return 0; }

C++中,引用变量之前必须对其初始化,看了你这段代码,发现你的变量r在for循环判断之前并没有初始化而直接对其判断是否为0,这是一种错误的引用.而且对於输入的两个数m、n,在处理的时候最好不要改变它们本身的值,而将其拷贝给另外俩个变量(自己重新声明两个变量),这是一种很好的编程习惯.

//不知道这是不是穷举法,(//是可选的)#include "stdafx.h" void main() { int a,b,i,j; //如果觉得数不够大,可以定义为double类型 //int c; scanf("%d%d",&a,&b); //c = a < b ? a : b ; for(i=1;i<=(a<b?a:b);i++) //for(i = 2;i <= c; i++) { if((a%i == 0)&&(b%i == 0)) j = i; } printf("%d\n",j); }

需要找出两个数的最小值,进行穷举法求解,参考代码如下#include<stdio.h>int main(){ int x,y,min,i; scanf("%d%d",&x,&y); min=x>y?y:x; if(min<=0){ printf("error"); return 0; } for(i=min;i>=1;--i){ if(x%i==0&&y%i==0) break; } printf("两个数的最大公约数为%d",i); return 0;}

要代码?还非要穷举法…表示已经习惯了辗转相除 设两个数为x,y 从1开始枚举到x,y中较小一个,if(x%i==0&&y%i==0)ans=i; 跑完后ans即为最大公约数 逆序枚举可能会快些 已经晓得最大公约数了,求最小公倍数可以用这个公式 xy=最大公约数*最小公倍数,把最小公倍数求出来

#include main(){ int a,b,n,m; printf("input two number.\n"); scanf("%d %d",&a,&b); for(n=(a+b)/2;n>0;n--){ if((a%n==0)&&(b%n==0)) break; } m=a*b/n; printf("%d\n%d\n",n,m); } 运行的时候从键盘输入两个整数,输出的数第一个是最大公约数,第二个数是 最小公倍数.考虑到最大公约数与最小公倍数之积等于原来两数之积,可以简化计算.

5213.net | ldyk.net | 369-e.com | qwrx.net | nczl.net | 网站首页 | 网站地图
All rights reserved Powered by www.wlbk.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com