首页 > 编程笔记 > C++笔记 阅读:2,368

C++最大公约数(递归)详解

使用递归可以计算两个数字的最大公约数。根据欧几里得算法,两个正整数 x 和 y 的最大公约数的计算方法如下:

gcd(x,y) = y; 如果y除以x而没有余数
gcd(x,y) = gcd(y, x/y的余数);否则

这个定义指出,如果 x/y 没有余数,则 x 和 y 的最大公约数是 y;否则,答案就是 y 和 x/y 的余数的最大公约数。

下面的程序显示了递归的 C++ 实现:
// This program demonstrates a recursive function to
// calculate the greatest common divisor (gcd) of two numbers.
#include <iostream>
using namespace std;

// Function prototype
int gcd(int, int);
int main()
{
    int num1, num2;
    cout << "Enter two integers: ";
    cin >> num1 >> num2;
    cout << "The greatest common divisor of " << num1;
    cout << " and " << num2 << " is ";
    cout << gcd(num1, num2) << endl;
    return 0;
}
int gcd(int x, int y)
{
    if (x % y == 0) //base case
        return y;
    else
        return gcd{y, x % y);
}
程序输出结果:

Enter two integers: 49 28
The greatest common divisor of 49 and 28 is 7

爱面试的程序媛,一个分享面试经验的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,定时分享程序员面试的那点事。

面试如何造火箭?工作如何拧螺丝?都在这个公号哦。

扫描二维码关注公众号,免费领取价值 1000 元的求职面试资料(限时免费)!

当你决定关注「爱面试的程序媛」,你已然超越了90%的程序员!

爱面试的程序媛二维码
微信扫描二维码关注