企业官网建设流程全解析

北京做网站建设的公司,网址大全123设为主页,巴中汽车网站建设,山西省网站制作一. 什么是最大公约数#xff08;GCD#xff09;最大公约数#xff08;Greatest Common Divisor#xff09;是指两个或多个整数共有约数中最大的一个。例如#xff1a;12 和 18 的公约数有 1, 2, 3, 6#xff0c;其中最大的是 6所以 gcd(12, 18) 6二. 方法一#xff1a…一. 什么是最大公约数GCD最大公约数Greatest Common Divisor是指两个或多个整数共有约数中最大的一个。例如12 和 18 的公约数有 1, 2, 3, 6其中最大的是 6所以 gcd(12, 18) 6二. 方法一辗转相除法欧几里得算法1.这是最经典的求最大公约数的方法基于以下原理两个数的最大公约数等于较大数除以较小数的余数和较小数的最大公约数gcd(a, b) gcd(b, a % b)其中 a % b 表示 a 除以 b 的余数。2.举个例子求 gcd(12, 18)gcd(12, 18) gcd(18, 12) // 先确保第一个数大18 ÷ 12 1 余 6gcd(18, 12) gcd(12, 6) // 应用公式12 ÷ 6 2 余 0gcd(12, 6) gcd(6, 0)当第二个数为0时第一个数就是答案6三.现在看代码的详细解释方法1.1循环实现public static int gcd1(int a, int b) { // 确保a b if (a b) { int temp a; // 临时变量保存a的值 a b; // 把b的值赋给a b temp; // 把原来a的值赋给b } // 执行到这里a一定是较大的数b是较小的数 // 辗转相除 while (b ! 0) { // 当b不等于0时继续循环 int remainder a % b; // 求a除以b的余数 a b; // 把b的值赋给a b remainder; // 把余数赋给b } return a; // 当b0时a就是最大公约数 }用例子走一遍计算 gcd1(12, 18)输入 a12, b18因为 12 18交换a18, b12进入while循环第一次循环b12≠0remainder 18 % 12 6a 12b 6第二次循环b6≠0remainder 12 % 6 0a 6b 0第三次b0退出循环返回 a6方法1.2递归实现public static int gcd2(int a, int b) { if (b 0) { // 终止条件当b0时 return a; // a就是最大公约数 } return gcd2(b, a % b); // 递归调用用(b, a%b)继续计算 }递归的思考方式把大问题分解成小问题每次递归都让问题变小一点直到遇到最简单的情况b0用例子走一遍计算 gcd2(12, 18)第一次调用gcd2(12, 18)b18≠0不返回a调用 gcd2(18, 12%18) 即 gcd2(18, 12)第二次调用gcd2(18, 12)b12≠0调用 gcd2(12, 18%12) 即 gcd2(12, 6)第三次调用gcd2(12, 6)b6≠0调用 gcd2(6, 12%6) 即 gcd2(6, 0)第四次调用gcd2(6, 0)b0 ✓返回 a6结果层层返回6 ← 6 ← 6 ← 6四.再看测试代码public static void main(String[] args) { int a 12; int b 18; // 测试两种方法 System.out.println(gcd1( a , b ) gcd1(a, b)); System.out.println(gcd2( a , b ) gcd2(a, b)); // 更多测试 System.out.println(\n更多测试); System.out.println(gcd(24, 36) gcd2(24, 36)); // 应该是12 System.out.println(gcd(17, 13) gcd2(17, 13)); // 两个质数应该是1 System.out.println(gcd(100, 0) gcd2(100, 0)); // 一个数为0应该是100 }理解辗转相除法就像以大换小的游戏用大数除以小数得到余数原来的小数变成新的大数余数变成新的小数重复直到余数为0最后的小数就是答案用 gcd(12, 18) 来说开始大18, 小1218 ÷ 12 1 余 6 → 新大12, 新小612 ÷ 6 2 余 0 → 余数为0停止答案就是最后的小数6