简介
在本实验中，你将学习如何在 C 程序中使用欧几里得算法来找到两个整数的最大公约数（GCD）。你将首先从用户输入中读取两个整数，然后应用欧几里得算法来计算它们的 GCD，最后打印结果。本实验涵盖了数论和离散数学中的基本概念，使用 C 编程语言提供了这些原理的实际应用。
读取两个整数
在这一步中，你将学习如何在 C 程序中从用户输入读取两个整数，以找到它们的最大公约数（GCD）。
首先，让我们为我们的 GCD 程序创建一个新的 C 文件：
cd ~/project
nano gcd.c
现在，添加以下代码来读取两个整数：
#include <stdio.h>
int main() {
int num1, num2;
printf("输入第一个整数：");
scanf("%d", &num1);
printf("输入第二个整数：");
scanf("%d", &num2);
printf("第一个数字：%d\n", num1);
printf("第二个数字：%d\n", num2);
return 0;
}
让我们来分析一下这段代码：
scanf()用于从用户读取整数输入%d是整数的格式说明符&num1和&num2将变量的内存地址传递过去以存储输入
编译并运行该程序：
gcc gcd.c -o gcd
./gcd
示例输出：
输入第一个整数：48
输入第二个整数：18
第一个数字：48
第二个数字：18
应用欧几里得算法
在这一步中，你将实现欧几里得算法来找出两个整数的最大公约数（GCD）。
打开之前的 gcd.c 文件并进行修改，以包含 GCD 计算：
cd ~/project
nano gcd.c
用欧几里得算法的实现更新代码：
#include <stdio.h>
// 使用欧几里得算法计算 GCD 的函数
int calculateGCD(int a, int b) {
// 确保为正数
a = (a > 0)? a : -a;
b = (b > 0)? b : -b;
// 欧几里得算法
while (b!= 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("输入第一个整数：");
scanf("%d", &num1);
printf("输入第二个整数：");
scanf("%d", &num2);
// 计算 GCD
gcd = calculateGCD(num1, num2);
printf("第一个数字：%d\n", num1);
printf("第二个数字：%d\n", num2);
printf("最大公约数：%d\n", gcd);
return 0;
}
让我们来分析一下欧几里得算法的实现：
- 该算法反复用较大的数除以较小的数
- 它使用取模运算符
%来得到余数 - 这个过程一直持续到余数变为 0
- 最后一个非零余数就是 GCD
编译并运行程序：
gcc gcd.c -o gcd
./gcd
示例输出：
输入第一个整数：48
输入第二个整数：18
第一个数字：48
第二个数字：18
最大公约数：6
打印最大公约数
在这一步中，你将对最大公约数（GCD）结果进行格式化并打印，同时添加更多背景信息，使输出更具信息量。
打开之前的 gcd.c 文件，并对输出添加一些格式设置：
cd ~/project
nano gcd.c
更新代码以增强 GCD 输出：
#include <stdio.h>
// 使用欧几里得算法计算 GCD 的函数
int calculateGCD(int a, int b) {
// 确保为正数
a = (a > 0)? a : -a;
b = (b > 0)? b : -b;
// 欧几里得算法
while (b!= 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("最大公约数（GCD）计算器\n");
printf("----------------------------------------\n");
printf("输入第一个整数：");
scanf("%d", &num1);
printf("输入第二个整数：");
scanf("%d", &num2);
// 计算 GCD
gcd = calculateGCD(num1, num2);
// 格式化输出
printf("\n结果：\n");
printf("第一个数字： %d\n", num1);
printf("第二个数字： %d\n", num2);
printf("GCD: %d\n", gcd);
// 额外解释
printf("\n解释：\n");
printf("最大公约数（GCD）是能同时整除这两个数且不留下余数的最大正整数。\n");
return 0;
}
编译并运行程序：
gcc gcd.c -o gcd
./gcd
示例输出：
最大公约数（GCD）计算器
----------------------------------------
输入第一个整数：48
输入第二个整数：18
结果：
第一个数字： 48
第二个数字： 18
GCD： 6
解释：
最大公约数（GCD）是能同时整除这两个数且不留下余数的最大正整数。
主要改进：
- 添加了标题和分隔符
- 以对齐的列格式化输出
- 包含了 GCD 概念的解释
- 保留了核心的 GCD 计算逻辑
总结
在本实验中，你首先学习了如何使用 scanf() 函数从用户输入中读取两个整数。然后，你实现了欧几里得算法来计算这两个数的最大公约数（GCD）。欧几里得算法是一种通过反复应用取模运算直到余数变为零来高效找到 GCD 的方法，此时 GCD 就是最后一个非零余数。最后，你打印了计算出的 GCD。
