个人中心
gpt4 book ai didi

C++求最大公约数四种方法解析

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 37 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++求最大公约数四种方法解析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

C++求最大公约数的四种方法思路，供大家参考，具体内容如下 。

将最近学的求最大公约数的四种方法总结如下:

第一种：穷举法之一 。

解释：拿其中一个数出来，用一个临时变量（tem）保存，每次都把那两个数除以这个临时变量。如果能除断，直接返回tem；如果不能除断，tem- -，直到都能除断，再返回tem。tem就是它们的最大公约数.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int CommFactor1( int m, int n); //函数的声明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为：" << CommFactor1(a,b)<< endl;
  return 0;
}
int CommFactor1( int m, int n)
{
  int tem;
  for (tem = m;; tem--)
  {
  if (m % tem == 0 && n % tem == 0)
  {
   break ;
  }
  }
  return tem;
}

第二种：穷举法之二 。

解释：求出两数的所有公因子，再把公因子累乘得到最大公约数.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int CommFactor2( int m, int n); //函数的声明
int main()
{
   int a, b;
   cin >> a >> b;
   cout << "这两个数的最大公约数为：" << CommFactor2(a,b)<< endl;
   return 0;
}
int CommFactor2( int m, int n)
{
   int i;
   int factor = 1;
   for (i=2;i<=m&&i<<n;i++)
   {
     while (m % i == 0 && n % i == 0)  //这里不能用if语句，因为可能会有重复的公因子
     {
       factor = factor * i;
       m = m / i;
       n = n / i;
     }
   }
   return factor;
}

第三种：辗转相除法 。

解释：将两个数辗转相除直到余数为0。（具体思想请问度娘） 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int CommFactor3( int m, int n); //函数的声明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为：" << CommFactor2(a,b)<< endl;
  return 0;
}
int CommFactor3( int m, int n)
{
  int z = n;
  while (m % n != 0)
  {
  z = m % n;
  m = n;
  n = z;
  }
  return z;
}

第四种：辗转相减法 。

解释：将两个数辗转相减直到两数相等。（具体思想请问度娘） 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int CommFactor4( int m, int n); //函数的声明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为：" << CommFactor4(a,b)<< endl;
  return 0;
}
int CommFactor4( int m, int n)
{
 
  while (m != n)
  {
  if (m > n)
  {
  m = m - n;
  }
  else
  {
  n = n - m;
  }
  }
  return m;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：https://blog.csdn.net/qq_46459874/article/details/108628942 。

最后此篇关于C++求最大公约数四种方法解析的文章就讲到这里了,如果你想了解更多关于C++求最大公约数四种方法解析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

37 4 0
文章推荐： 如何成为合格的Java开发人员
文章推荐： jQuery浏览器CSS3特写兼容实例
文章推荐： PHP命令空间namespace及use的用法小结
文章推荐： 浅谈C++ 虚函数
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com