用更相减损术求解最大公约数与最小公倍数

解题思路:

用辗转相除法求最大公约数已经写过了  利用递归与数学方法求解最大公约数与最小公倍数问题-Dotcpp编程社区

这次使用更相减损术求解最大公约数求解此题，求解此题需要明白两点：

1、更相减损术：

拿到用户输入的两个值：a,b，判断出较大值，用较大值减较小值，如此往复，直到为0，此时得到较大值=较小值，则此值为最大公约数

例：

输入98和63

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

7-7=0

则7为最大公约数

2、最小公倍数求法：

最小公倍数 = a* b / 最大公约数（a,b为用户输入值）

此时即可求解

注意事项:

需判断输入数中的较大值，用较大值减去较小值，以后每次进入dfs1循环时都需要判断

参考代码:

#include<iostream>

using namespace std;

int temp;//定义全局中间变量

int dfs1(int a,int b)

{

if (a > b)//判断a，b中的较大值

{

if (a==b)//设置退出条件

return a;

temp = a - b;//中间值拿到ab之间的差

a = b;//用b做下一项的较大值a

b = temp;//用ab的差做下一项的较小值

dfs1(a, b);

}

else

{

if (a==b)

return a;

temp = b - a;

b = a;

a = temp;

dfs1(a, b);

}

}

int dfs2(int a,int b,int c)//利用公式求出最小公倍数

{

return a * b / c;

}

int main()

{

int a, b, c, d, e, f;

cin >> a >> b;

c = dfs1(a, b);//求出最大公约数

d = dfs2(a, b, c);//求出最小公倍数

cout << c << " " << d << endl;

return 0;

}