【约数】求最大公约数——递归
请使用递归算法计算正整数n和m的最大公约数GCD(n,m)。
G
C
D
(
n
,
m
)
=
{
=
m
,
当
m
<
=
n
且
n
m
o
d
m
=
0
=
G
C
D
(
m
,
n
)
,
当
n
<
m
时
=
G
C
D
(
m
,
n
m
o
d
m
)
,
其他
GCD(n,m)=\left\{\begin{matrix} =m,当 m<=n 且 n mod m =0\\ =GCD(m,n),当n<m时\\ =GCD(m,n \mod m),其他 \end{matrix}\right.
GCD(n,m)=⎩
⎨
⎧=m,当m<=n且nmodm=0=GCD(m,n),当n<m时=GCD(m,nmodm),其他
输入：
n m
输出：
n和m的最大公约数文章来源：https://www.toymoban.com/news/detail-774431.html
样例：
| 序号 | 测试输入 | 期待的输出 | 额外进程 |
|---|---|---|---|
| 1 | 24 48↵ |
24↵ |
0 |
| 2 | 13 15↵ |
1↵ |
0 |
思路
怎么说呢，其实只要理解了什么是递归，这道题就是把题目抄一遍
即
G
C
D
(
n
,
m
)
=
{
=
m
,
当
m
<
=
n
且
n
m
o
d
m
=
0
=
G
C
D
(
m
,
n
)
,
当
n
<
m
时
=
G
C
D
(
m
,
n
m
o
d
m
)
,
其他
GCD(n,m)=\left\{\begin{matrix} =m,当 m<=n 且 n mod m =0\\ =GCD(m,n),当n<m时\\ =GCD(m,n \mod m),其他 \end{matrix}\right.
GCD(n,m)=⎩
⎨
⎧=m,当m<=n且nmodm=0=GCD(m,n),当n<m时=GCD(m,nmodm),其他文章来源地址https://www.toymoban.com/news/detail-774431.html
代码
#include <stdio.h>
int GCD(int n, int m)
{
if (m <= n && n % m == 0) return m;
else if (n < m)return GCD(m, n);
else return GCD(m, n % m);
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", GCD(a, b));
}
到了这里，关于【约数】求最大公约数——递归的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
