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

C++最大公约数(递归)详解,第1张

概述使用递归可以计算两个数字的最大公约数。根据欧几里得算法,两个正整数 x 和 y 的最大公约数的计算方法如下: gcd(x,y) = y; 如果y除以x而没有余数 gcd(x,y) = gcd(y, x/y的余数);否则 这个 使用递归可以计算两个数字的最大公约数。根据欧几里得算法,两个正整数 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 prototypeint 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

总结

以上是内存溢出为你收集整理的C++最大公约数(递归)详解全部内容,希望文章能够帮你解决C++最大公约数(递归)详解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://www.outofmemory.cn/langs/1231086.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-06
下一篇 2022-06-06

发表评论

登录后才能评论

评论列表(0条)

保存