C++递归解法：求两个正整数的最大公约数 |21xrx.com

C++递归解法：求两个正整数的最大公约数

2023-07-01 12:27:26 深夜i -- --

C++ 递归最大公约数正整数

对于两个正整数a和b，若a能够整除b，那么a和b的最大公约数就是b；否则，则a和b的最大公约数等价于b和a mod b的最大公约数。这个过程可以使用递归算法来实现。

下面是C++语言中递归解法的实现代码：


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

递归的终止条件是当b为0时，返回a，否则返回gcd(b, a mod b)的计算结果。由于每一个递归过程都会将b替换为a mod b，所以可以保证除数始终比被除数小，且递归过程会不断缩小它们之间的差距，最终得到它们的最大公约数。

下面的代码使用了递归解法来计算10和25的最大公约数：


#include<iostream>
using namespace std;
int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
int main(){
  int a = 10, b = 25;
  cout<<"\nGCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
  return 0;
}

最终输出结果：GCD of 10 and 25 is 5

递归解法比较简单，但需要注意它的时间复杂度为O(logmin(a,b))。因此，对于较大的数，递归解法可能会抛出栈溢出异常。在这种情况下，可以使用循环或更高效的算法来优化计算过程。

上一篇: idea打包java可执行jar包

下一篇: C++与逻辑 – 强大的编程语言与清晰的思维方式

评论区

()

相似文章