c/c++求两个数的最大公约数(递归版)

简介: c/c++求两个数的最大公约数(递归版)

我们先假设 x>y gcd(x,y)为x与y的最大公约数,先假设gcd(x,y)=d, d为x和y的最大公约数,那么可以得到这样一个结论:x能被d整除,y能被d整除。 OK,注意了,要变换了,因为x和y都能被d整除,所以x-y也能被d整除(我们提前假设了x>y了的额),再变换一下,因为x-y能被d整除,所以(x%y)也能被d整除。 OK,我们可以得到gcd(x,y)=gcd(x-y,y)=gcd(x%y,y) 应该能理解吧(你想想看嘛,y没有变,x,x-y,x%y都能被d整除,所以最终答案肯定还是d噻)good,我们知道了这个思路,就可以愉快的写代码了(递归版)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int f(int x, int y) {
  if (x%y==0) {
    return y;
  }
  return f(y, x%y);//这里不懂的可以思考下额  也比较简单
}
int main() {
  int x, y;
  cin>>x>>y;//输入x与y
  if (x < y)
    swap(x, y);//如果x<y就交换x与y的值
  int ans = f(x, y);
  printf("%d", ans);
  return 0;
}



相关文章
汉诺塔问题(递归)/梵塔问题c++
汉诺塔问题(递归)/梵塔问题c++
|
算法 C++
C++快速幂(递归)
C++快速幂(递归)
【C++】递归,搜索与回溯算法入门介绍和专题一讲解
【C++】递归,搜索与回溯算法入门介绍和专题一讲解
|
6月前
|
设计模式 中间件 程序员
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
331 3
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
6月前
|
人工智能 算法 C++
c++算法学习笔记 (18) 约数
c++算法学习笔记 (18) 约数
|
6月前
|
C++
C++ 递归与面向对象编程基础
C++ 递归是函数自我调用的技术,用于简化复杂问题。以递归求和为例,`sum` 函数通过不断调用自身累加数字直到 `k` 为 0。递归需谨慎,避免无限循环和资源浪费。面向对象编程(OOP)将程序划分为交互对象,具有属性和方法,提升代码复用、维护和扩展性。C++ OOP 基本概念包括类、对象、属性和方法。通过创建类和对象,利用点语法访问成员,实现代码组织。
47 0
|
6月前
|
Java Go Python
Golang每日一练(leetDay0103) 区域和检索1~3
Golang每日一练(leetDay0103) 区域和检索1~3
58 0
Golang每日一练(leetDay0103) 区域和检索1~3
|
6月前
|
Java Go C++
C/C++每日一练(20230424) 只出现一次的数字、有效的括号、递归反序正整数
C/C++每日一练(20230424) 只出现一次的数字、有效的括号、递归反序正整数
57 0
C/C++每日一练(20230424) 只出现一次的数字、有效的括号、递归反序正整数