本关任务:编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。
为了完成本关任务,你需要掌握:
基本原理:for
循环是一种常用的循环结构,它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)
。初始化表达式在循环开始时执行一次,用于初始化循环变量。循环条件在每次循环迭代开始时进行检查,如果为真,则执行循环体中的代码。更新表达式在每次循环体执行完后执行,用于更新循环变量。
示例代码
#include <stdio.h>
int main() {
// 打印1到10的数字
for (int i = 1; i <= 10; i++) {
printf("%d ", i);
}
printf("\n");
return 0;
}
基本原理:while
循环在循环开始时检查循环条件。只要条件为真,就会执行循环体中的代码。语法格式为while(循环条件)
。循环条件是一个表达式,它返回一个布尔值(真或假)。在循环体中,通常需要包含一些能够改变循环条件的语句,否则可能会导致无限循环。
示例代码
#include <stdio.h>
int main() {
int i = 1;
while (i <= 10) {
printf("%d ", i);
i++;
}
printf("\n");
return 0;
}
基本原理:break
语句用于立即跳出当前循环(for
、while
、do - while
)或switch
语句。当程序执行到break
语句时,循环或switch
语句会立即终止,程序控制流将跳转到循环或switch
语句后的下一条语句。
示例代码(在循环中使用 break)
#include <stdio.h>
int main() {
for (int i = 1; i <= 10; i++) {
if (i == 5) {
break;
}
printf("%d ", i);
}
printf("\n");
return 0;
}
基本原理:continue
语句用于跳过当前循环迭代的剩余部分,直接开始下一次循环迭代。当程序执行到continue
语句时,循环体中continue
语句之后的代码将不会被执行,而是直接跳转到循环的更新表达式(对于for
循环)或循环条件检查(对于while
和do - while
循环)。
示例代码(在循环中使用 continue)
#include <stdio.h>
int main() {
for (int i = 1; i <= 10; i++) {
if (i == 5) {
continue;
}
printf("%d ", i);
}
printf("\n");
return 0;
}
最大公约数(Greatest Common Divisor,简称 GCD),指两个或多个整数共有约数中最大的一个。例如,12 和 18 的最大公约数是 6。
算法原理:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的新余数(第二余数)去除第一余数,如此反复,直到最后余数是 0 为止。此时的除数就是最大公约数。
代码示例:
#include <stdio.h>
// 辗转相除法求最大公约数的函数
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 的个数乘上此时相等的这个数,就是最大公约数。
代码示例(结合辗转相除法优化):
#include <stdio.h>
// 用更相减损术结合辗转相除法求最大公约数的函数
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
循环按照更相减损术的思路,用大数减小数,直到两数相等。最小公倍数(Least Common Multiple,简称 LCM),是两个或多个整数公有的倍数中最小的一个。例如,4 和 6 的最小公倍数是 12。
两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。即 LCM(a, b) = a * b / GCD(a, b)
。
#include <stdio.h>
// 辗转相除法求最大公约数的函数(前面已讲,此处复用)
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
开始你的任务吧,祝你成功!
#include <stdio.h>
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 *********/
}