C 语言递归计算最小公倍数(LCM)

CCBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

在本实验中,我们将编写一个 C 程序,使用递归来找到两个数的最小公倍数(LCM)。最小公倍数是能够被这两个数整除的最小正整数,且不留下任何余数。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL c(("`C`")) -.-> c/BasicsGroup(["`Basics`"]) c(("`C`")) -.-> c/FunctionsGroup(["`Functions`"]) c(("`C`")) -.-> c/FileHandlingGroup(["`File Handling`"]) c(("`C`")) -.-> c/UserInteractionGroup(["`User Interaction`"]) c/BasicsGroup -.-> c/variables("`Variables`") c/BasicsGroup -.-> c/operators("`Operators`") c/FunctionsGroup -.-> c/function_declaration("`Function Declaration`") c/FunctionsGroup -.-> c/function_parameters("`Function Parameters`") c/FunctionsGroup -.-> c/math_functions("`Math Functions`") c/FunctionsGroup -.-> c/recursion("`Recursion`") c/FileHandlingGroup -.-> c/create_files("`Create Files`") c/UserInteractionGroup -.-> c/user_input("`User Input`") c/UserInteractionGroup -.-> c/output("`Output`") subgraph Lab Skills c/variables -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/operators -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/function_declaration -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/function_parameters -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/math_functions -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/recursion -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/create_files -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/user_input -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} c/output -.-> lab-123279{{"`C 语言递归计算最小公倍数(LCM)`"}} end

理解 LCM 的概念

在开始编程之前,我们先来理解 LCM 的概念。两个整数的最小公倍数(LCM)是能够被这两个数整除的最小正整数。要找到两个数的最小公倍数,我们可以使用以下公式:

LCM = (number1 * number2) / GCD

其中,number1number2 是我们需要找到 LCM 的两个数,而 GCD 是这两个数的最大公约数(Greatest Common Divisor)。

创建一个新的 C 文件

让我们在 ~/project/ 目录下创建一个名为 main.c 的新 C 文件,我们将在其中编写程序。

编写代码

将以下代码复制并粘贴到 main.c 文件中。

#include<stdio.h>

int find_lcm(int, int); // 函数原型声明

int main()
{
    int a, b, lcm;
    printf("输入两个整数以查找 LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // 函数调用
    printf("%d 和 %d 的 LCM 是 %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // 函数定义
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

编译并运行程序

保存 main.c 文件,并在终端中使用以下命令编译程序:

gcc main.c -o main

使用以下命令运行程序:

./main

在提示时输入两个整数,程序将显示这两个数的最小公倍数(LCM)。

理解代码

让我们来理解刚刚编写的代码。

  • 我们首先使用 #include<stdio.h> 在程序中包含标准输入输出库。
  • 我们声明了 find_lcm 函数的原型,稍后将在程序中定义它。这是必要的,因为我们在 main 函数中调用 find_lcm 函数时,其实际定义还未出现。
  • main 函数中,我们声明了三个整型变量 ablcm
  • 我们使用 printf 提示用户输入两个整数,并使用 scanf 接收输入。
  • 然后我们调用 find_lcm 函数,并将 ab 作为参数传递给它。
  • find_lcm 函数接受两个整型参数 ab,并通过递归返回这两个数的最小公倍数(LCM)。
  • 我们初始化一个静态变量 temp 为 1,它将保存我们正在检查的当前值是否为倍数。
  • 在每次递归中,我们检查 temp 是否是 ab 的倍数。
  • 如果是倍数,我们返回 temp 作为 LCM。
  • 如果不是倍数,我们递增 temp 并递归调用 find_lcm 函数,直到找到 LCM。

测试程序

使用不同的输入值测试程序,并验证其输出的最小公倍数(LCM)是否正确。

完整代码

以下是使用递归查找两个数的最小公倍数(LCM)的 C 程序完整代码:

#include<stdio.h>

int find_lcm(int, int); // 函数原型声明

int main()
{
    int a, b, lcm;
    printf("输入两个整数以查找 LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // 函数调用
    printf("%d 和 %d 的 LCM 是 %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // 函数定义
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

总结

在本实验中,我们学习了如何使用递归编写一个 C 程序来查找两个数的最小公倍数(LCM)。我们使用递归函数来找到 LCM,并详细解释了程序的每一步。我们还学习了如何使用终端编译和运行 C 程序。

您可能感兴趣的其他 C 教程