百度移动网站生成,wordpress 链接按钮,石碣镇仿做网站,如果在各大网站做免费的网络推广文章目录 题目描述算法思路代码示例辗转相除法暴力穷尽法更相减损法Stein法 题目描述
给定两个数#xff0c;求这两个数的最大公约数
例如#xff1a; 输入#xff1a;20 40 输出#xff1a;20
算法思路
最大公约数#xff1a;即两个数据中公共约数的最大者
代码示例… 文章目录 题目描述算法思路代码示例辗转相除法暴力穷尽法更相减损法Stein法 题目描述
给定两个数求这两个数的最大公约数
例如 输入20 40 输出20
算法思路
最大公约数即两个数据中公共约数的最大者
代码示例
辗转相除法 让两个数中的大数对小数取余,再将小数赋予大数,结果赋予小数,重复以上动作直至两数其中一个数为零,那么另一个就是最大公约数 例如 18和24的最大公约数
第一次a 18 b 24 c a%b 18%24 18 循环中a 24 b18
第二次a 24 b 18 c a%b 24%18 6 循环中a 18 b 6
第三次a 18 b 6 c a%b 18%6 0 循环结束
此时b中的内容即为两个数中的最大公约数
#include stdio.hint main()
{int m 0;int n 0;int tmp 0;printf(请输入两个整数: );scanf(%d %d, m, n);while (tmp m % n){m n;n tmp;}printf(最大公约数为:%d\n, n);return 0;
}
暴力穷尽法 如果大数可以整除小数那么最大公约数为小数。 如果不能整除小数那么这两个数就按大到小依次对比小数小的数求余遇到都能够整除的就是最大公约数。 #includestdio.hint main(){//暴力穷举法int a 0;int b 0;printf(请输入两个整数);scanf(%d%d, a, b);if (a b){int i 0;for (i b; i 1; i--){if (a%i 0 b%i 0){printf(最大公约数为%d\n, i);break;}}}else{int j 0;for (j a; j 1; j--){if (a%j 0 b%j 0){printf(最大公约数为%d\n, j);break;}}}return 0;
}
更相减损法 当两个数相等时最大公约数为他们其中任意一个 当两个数不相等时用大数减小数得到的差和之前的那个小数再次相减直到两个数相等相等的两个中任意一个都是最大公约数。 #includestdio.hint main(){//更相减损法int a 0;int b 0;printf(请输出两个整数);scanf(%d%d, a, b);while ((a - b)!0){if (a b){a a - b;}else{b b - a;}}printf(最大公约数为%d\n, b);return 0;
}
Stein法 1两数均为偶数时将其同时除以2至少一数为奇数为止记录除掉的所有公因数2的乘积k 2如果仍有一数为偶数连续除以2直至该数为奇数为止 3用更相减损法(辗转相减法)即GCD(a,b)GCD(a-b,b)或辗转相除法求出两奇数的最大公约数d 4原来两数的最大公约数即为d*k。 #includestdio.hint main(){//Stein算法int a 0;int b 0;printf(请输入两个整数:);scanf(%d%d, a, b);int gcd 0;int k 1;while ((!(a 1)) (!(b 1))){ //step1;k 1; //用k记录全部公因子2的乘积 a 1;b 1;}while (!(a 1))a 1; //step2;while (!(b 1))b 1;if (ab) a ^ b, b ^ a, a ^ b; //交换使a为较大数 while (a ! b){ //step3;a - b;if (ab) a ^ b, b ^ a, a ^ b;}gcd k*a;printf(最大公约数为%d\n, gcd);return 0;
}
