目录😋
任务描述
本关任务：编写两个子函数，分别求任意两个整数的最大公约数和最小公倍数。
相关知识
为了完成本关任务，你需要掌握：
- 循环控制 / 跳转语句的使用
- 如何求最大公约数
- 如何求最小公倍数
一、循环控制 / 跳转语句的使用
1. 循环控制语句（for 循环）
- 基本原理：
for循环是一种常用的循环结构，它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)。初始化表达式在循环开始时执行一次，用于初始化循环变量。循环条件在每次循环迭代开始时进行检查，如果为真，则执行循环体中的代码。更新表达式在每次循环体执行完后执行，用于更新循环变量。- 示例代码
int main() { // 打印1到10的数字 for (int i = 1; i <= 10; i++) { printf("%d ", i); } printf("\n"); return 0; }
2. 循环控制语句（while 循环）
- 基本原理：
while循环在循环开始时检查循环条件。只要条件为真，就会执行循环体中的代码。语法格式为while(循环条件)。循环条件是一个表达式，它返回一个布尔值（真或假）。在循环体中，通常需要包含一些能够改变循环条件的语句，否则可能会导致无限循环。- 示例代码
int main() { int i = 1; while (i <= 10) { printf("%d ", i); i++; } printf("\n"); return 0; }
3. 跳转语句（break 语句）
- 基本原理：
break语句用于立即跳出当前循环（for、while、do - while）或switch语句。当程序执行到break语句时，循环或switch语句会立即终止，程序控制流将跳转到循环或switch语句后的下一条语句。- 示例代码（在循环中使用 break）
int main() { for (int i = 1; i <= 10; i++) { if (i == 5) { break; } printf("%d ", i); } printf("\n"); return 0; }
4. 跳转语句（continue 语句）
- 基本原理：
continue语句用于跳过当前循环迭代的剩余部分，直接开始下一次循环迭代。当程序执行到continue语句时，循环体中continue语句之后的代码将不会被执行，而是直接跳转到循环的更新表达式（对于for循环）或循环条件检查（对于while和do - while循环）。- 示例代码（在循环中使用 continue）
int main() { for (int i = 1; i <= 10; i++) { if (i == 5) { continue; } printf("%d ", i); } printf("\n"); return 0; }
二、求最大公约数
1. 概念回顾
最大公约数（Greatest Common Divisor，简称 GCD），指两个或多个整数共有约数中最大的一个。例如，12 和 18 的最大公约数是 6。
2. 常用算法及代码实现
（1）辗转相除法（欧几里得算法）：
- 算法原理：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的新余数（第二余数）去除第一余数，如此反复，直到最后余数是 0 为止。此时的除数就是最大公约数。
- 代码示例：
// 辗转相除法求最大公约数的函数 int gcd(int a, int b) { while (b!= 0) { int temp = b; b = a % b; a = temp; } return a; } int main() { int num1 = 24, num2 = 36; int result = gcd(num1, num2); printf("最大公约数为：%d\n", result); return 0; }
在上述代码中：
- 定义了一个名为
gcd的函数，它接受两个整数参数a和b，用于求这两个数的最大公约数。- 在
gcd函数内部，通过while循环，只要b不为 0，就进行以下操作：
- 先将当前的
b值暂存到temp变量中。- 然后更新
b的值为a除以b的余数（即a % b）。- 再将之前暂存的
temp（也就是原来的b）赋值给a，相当于用除数和余数不断进行替换操作，直到余数为 0，此时的a就是最大公约数。- 在
main函数中，定义了两个示例数字24和36，调用gcd函数求出它们的最大公约数，并将结果输出显示。（2）更相减损术（可用于优化辗转相除法等情况）：
- 算法原理：可先判断两数是否都是偶数，如果是，则先同时除以 2，记录下约去的 2 的个数，然后用较大数减去较小数，接着把所得的差与较小数比较，并以大数减小数，继续这个操作，直到两数相等为止，最后将之前记录的约去的 2 的个数乘上此时相等的这个数，就是最大公约数。
- 代码示例（结合辗转相除法优化）：
// 用更相减损术结合辗转相除法求最大公约数的函数 int gcd_optimized(int a, int b) { int factor = 1; // 记录约去2的个数 while (a % 2 == 0 && b % 2 == 0) { // 判断两数是否都是偶数 a /= 2; b /= 2; factor *= 2; } while (a!= b) { if (a > b) { a -= b; } else { b -= a; } } return a * factor; } int main() { int num1 = 24, num2 = 36; int result = gcd_optimized(num1, num2); printf("最大公约数为：%d\n", result); return 0; }
在这个代码中：
gcd_optimized函数首先通过一个while循环判断a和b是否都是偶数，如果是就不断约去 2，并记录约去 2 的个数（通过factor变量）。- 然后再通过另一个
while循环按照更相减损术的思路，用大数减小数，直到两数相等。- 最后返回的是约去 2 的个数乘以相等时的这个数，得到最大公约数。
三、求最小公倍数
1. 概念回顾
最小公倍数（Least Common Multiple，简称 LCM），是两个或多个整数公有的倍数中最小的一个。例如，4 和 6 的最小公倍数是 12。
2. 基于最大公约数求最小公倍数的方法及代码实现
两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。即
LCM(a, b) = a * b / GCD(a, b)。
// 辗转相除法求最大公约数的函数（前面已讲，此处复用） int gcd(int a, int b) { while (b!= 0) { int temp = b; b = a % b; a = temp; } return a; } // 求最小公倍数的函数 int lcm(int a, int b) { return a * b / gcd(a, b); } int main() { int num1 = 12, num2 = 18; int result = lcm(num1, num2); printf("最小公倍数为：%d\n", result); return 0; }
在上述代码中：
- 首先定义了
gcd函数用于求最大公约数（采用辗转相除法），这部分代码和前面介绍的一样。- 然后定义了
lcm函数用于求最小公倍数，它内部直接按照公式a * b / gcd(a, b)进行计算，也就是先获取两数的乘积，再除以它们的最大公约数。- 在
main函数中，定义了示例数字12和18，调用lcm函数求出它们的最小公倍数，并输出显示结果。
编程要求
根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。
测试说明
平台会对你编写的代码进行测试：
测试输入：
32 72
预期输出：
最大公约数是:8 最小公倍数是:288
测试输入：
56 98
预期输出：
最大公约数是:14 最小公倍数是:392
开始你的任务吧，祝你成功！
通关代码
int maxGYS(int a, int b)//求最大公约数子函数 { int r; r=a%b; //请在此添加代码 /*********Begin*********/ while(r !=0) { a=b; b=r; r=a%b; } return b; } /********* End *********/ int minGBS(int a, int b)//求最小公倍数子函数 { int i; //请在此添加代码 /*********Begin*********/ return (a*b) / maxGYS(a,b); /********* End *********/ } int main() { int a,b,t; printf("请输入两个整数:\n"); scanf("%d%d",&a,&b); if(a<b) //请在此添加代码 /*********Begin*********/ { t=a; a=b; b=t; printf("最大公约数是:%d\n",maxGYS(a,b)); printf("最小公倍数是:%d",minGBS(a,b)); } return 0; /********* End *********/ }
测试结果
