c++这个求最大公约数的函数求大佬分析！！！

c++这个求最大公约数的函数求大佬分析！！！如图，主要是标注的那个函数，我在网上看到的，虽然我能理解辗转相除法，但是看到这个我分析了半天还是懵了。之前自己写都是用辗转相除写的比较多，这尼玛一行就搞定了，还不用判断两个数谁大谁小要不要互换位置的问题，决定以后就按这个写了！但是希望有个大佬来帮我分析一下为啥这样写可以

举报该问题

推荐答案 2018-06-29

辗转相除法终止条件就是余数为0，也就是n=0，这时候条件语句按照后半段取值，返回m，也就是最终的最大公约数。而当n!=0时的算法是递推公式gcd(m,n)=gcd(n,m%n)
至于交换大小，当m<n的时候m%n=m相当于gcd(m,n)=gcd(n,m)就调整好大小顺序了，之后后一个参数都是严格小于前一个的，就没有顺序问题了。
不过这么写不确定有没有尾递归优化，可能有性能损失。不过估计编译器会按照if优化掉，不至于爆栈

温馨提示：答案为网友推荐，仅供参考

当前网址：http://99.wendadaohang.com/zd/7zttWvj7zXOee7Btee.html

其他回答

第1个回答 2018-06-29

这是一种使用递归求最大公约数的方法。
假设在13行调用gcd函数时，a的值为7，b的值为35；进入gcd函数执行第六行代码，这个函数只有当n的值等于0的时候，才会停止递归；现在我们的n其实就是35，不满足条件则执行gcd(n,m%n)进行递归；这时候递归到一个新的函数，现在的m是35，n是7(因为7%35的结果为7)，然后再执行第六行代码，发现n依然不等于0；继续递归也就是执行gcd(n,m%n)，现在m的值为7，n的值为0(因为35%7的结果为0)。
以上是对这个函数进行的举例说明，其实主要还是在gcd(n,m%n)这个代码上，自己慢慢体会下，不难掌握的。追问

贼6，说的我都懂了

第2个回答 2018-06-29

递归
一直调用gcd(int m,int n)

具体的你可以单步调试走一下,这个方式应该资源占用会多些

相似回答

[C++]解释一下关于求最大公约数的代码答：两个程序是一个意思，都是欧几里得辗转相除法求最大公约数，这种方法的解释如下：设有两个数num1和num2，假设num1比较大。令余数r = num1 % num2。当r == 0时，即num1可以被num2整除，显然num2就是这两个数的最大公约数。当r != 0时，令num1 = num2（除数变被除数），num2 = r（...

...n,unsigned int m)”求出n和m的最大公约数并返回答：方法一：非递归辗转相除法 int fun(unsigned int n,unsigned int m){ int m_cup, n_cup, res; /*被除数, 除数, 余数*/ m_cup = m;n_cup = n;res = m_cup % n_cup;while (res != 0){ m_cup = n_cup;n_cup = res;res = m_cup % n_cup;} return n_cup;} 方法二...

c++用函数求两个数的最大公约数如果不是输出0答：if (result != 1) { cout << "它们的最大公约数是" << result << endl;} else { cout << 0 << endl;} return 0;} 以上代码定义了一个 gcd() 函数来求解两个数的最大公约数。该函数采用递归的方式，如果第二个参数为 0，则返回第一个参数，否则将两个参数分别取余数并进行递归操作...

c++ 函数程序 求最大公约数 最小公倍数答：include<stdio.h> void main(){ int gcd(int a,int b),gcm(int a,int b,int c);int a,b,abd,abm;printf("plese input number:\n");scanf("%d,%d",&a,&b);abd=gcd(a,b);abm=gcm(a,b,abd);printf("abd=%d,abm=%d",abd,abm);} int gcd(int x,int y){ int r;if(x...

c++编写一个求两个整数最大公约数和最小公倍数的函数答：编写该程序的整体思路：分别定义最大公约数函数和最小公倍数函数，然后再main函数里面调用它。C语言实现代码如下：include<stdio.h> include<math.h> int fun_gy(int,int); //声明最大公约数函数 int fun_gb(int,int); //声明最小公倍数函数 main(){ int a,b,gy,gb;printf("输入两个...

如何用C++编程求两个自然数的最大公约数?答：先用辗转相除法求出它们的最大公约数gcd 因为最小公倍数lcm满足：lcm * gcd = i * j，所以可以求出lcm 再判断lcm是否正好是gcd的120倍即可 C++代码和运行结果如下：可见成功得到符合条件的两组数：(115, 552) 和 (232, 435)，望采纳~附源码：include <iostream> using namespace std;int ...

用C++编写函数求两个整数的最大公约数和最小公倍数答：include<stdio.h>int max(int a,int b){ //求最大公约数的函数 int i,k; for(i=1;i<=(a>b?b:a);i++) if(a%i==0&&b%i==0) k=i; return k;}int min(int a,int b){ //求最小公倍数的函数 int c,d,i; c=a>b?b:a; //大的 d=...

c++求最大公约数和最小公倍数?答：include <stdio.h> int main(){ int a,b,c,m,t;printf("请输入两个数:\n");scanf("%d%d",&a,&b);if(a

C++求两个数的最大公约数,程序没错,但求不出想要的结果,请高手...答：如下：include<iostream> using namespace std;int main(){ int m,n,i,t;cout<<"input two number:";cin>>m>>n;if(m<n){ t=m;m=n;n=t;} i=n;while(i){ if((m%i)==0 && (n%i)==0) break;else i--;} cout<<i<<endl;getchar();getchar();return 0;} ...

大家正在搜

编程求最大公约数最小公倍数最小公倍数和最大公约数的关系 c语言函数求最大公约数定义函数求最大公约数最大公约数的函数名称调用函数求最大公约数编写函数求最大公约数递归求最大公约数函数三个数的最大公约数