使用C++实现辗转相除法

辗转相除法是一种求最大公约数的算法，其实现如下：

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

其中，a 和 b 是两个整数，gcd 函数返回它们的最大公约数。

相关问题

c++实现辗转相除法

C++中实现辗转相除法（欧几里得算法）可以使用递归或循环的方式。下面是一个使用递归的示例代码：

#include <iostream>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    std::cout << "请输入两个整数：" << std::endl;
    std::cin >> num1 >> num2;
    int result = gcd(num1, num2);
    std::cout << "最大公约数是：" << result << std::endl;
    return 0;
}

在这个示例中，`gcd`函数使用递归的方式实现了辗转相除法。当`b`等于0时，递归结束，返回`a`作为最大公约数。否则，递归调用`gcd(b, a % b)`，将`b`和`a`除以`b`的余数作为新的参数传入。

用户输入两个整数后，程序会计算它们的最大公约数并输出。

编写C++用辗转相除法求最大公约数

下面是用 C 语言编写的辗转相除法求最大公约数的代码：

#include <stdio.h>

int gcd(int a, int b) {
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main() {
    int a, b;
    printf("请输入两个正整数：");
    scanf("%d %d", &a, &b);
    printf("它们的最大公约数是：%d\n", gcd(a, b));
    return 0;
}

代码中的 `gcd` 函数用于实现辗转相除法求最大公约数，其中 `a` 和 `b` 分别表示两个正整数。在函数中，首先计算 `a` 对 `b` 取模的结果 `r`，然后利用循环不断将 `b` 赋值给 `a`，`r` 赋值给 `b`，并重新计算 `r` 的值，直到 `r` 等于 0，此时最大公约数即为 `b`。

在 `main` 函数中，首先通过 `scanf` 函数获取用户输入的两个正整数，然后调用 `gcd` 函数求它们的最大公约数，并通过 `printf` 函数输出结果。