快捷導(dǎo)航

C++求最大公約數(shù)四種方法解析

更新時(shí)間：2020年09月17日 14:06:59 作者：時(shí)光zz

這篇文章主要為大家詳細(xì)介紹了C++求最大公約數(shù)四種方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

C++求最大公約數(shù)的四種方法思路，供大家參考，具體內(nèi)容如下

將最近學(xué)的求最大公約數(shù)的四種方法總結(jié)如下：

第一種：窮舉法之一

解釋：拿其中一個(gè)數(shù)出來(lái)，用一個(gè)臨時(shí)變量（tem）保存，每次都把那兩個(gè)數(shù)除以這個(gè)臨時(shí)變量。如果能除斷，直接返回tem；如果不能除斷，tem- -，直到都能除斷，再返回tem。tem就是它們的最大公約數(shù)。

#include <iostream>
using namespace std;
int CommFactor1(int m, int n); //函數(shù)的聲明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "這兩個(gè)數(shù)的最大公約數(shù)為：" << 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;
}

第二種：窮舉法之二

解釋：求出兩數(shù)的所有公因子，再把公因子累乘得到最大公約數(shù)。

#include <iostream>
using namespace std;
int CommFactor2(int m, int n); //函數(shù)的聲明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "這兩個(gè)數(shù)的最大公約數(shù)為：" << 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語(yǔ)句，因?yàn)榭赡軙?huì)有重復(fù)的公因子
    {
      factor = factor * i;
      m = m / i;
      n = n / i;
    }
  }
  return factor;
}

第三種：輾轉(zhuǎn)相除法

解釋：將兩個(gè)數(shù)輾轉(zhuǎn)相除直到余數(shù)為0。（具體思想請(qǐng)問(wèn)度娘）

#include <iostream>
using namespace std;
int CommFactor3(int m, int n); //函數(shù)的聲明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "這兩個(gè)數(shù)的最大公約數(shù)為：" << 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;
}

第四種：輾轉(zhuǎn)相減法

解釋：將兩個(gè)數(shù)輾轉(zhuǎn)相減直到兩數(shù)相等。（具體思想請(qǐng)問(wèn)度娘）

#include <iostream>
using namespace std;
int CommFactor4(int m, int n); //函數(shù)的聲明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "這兩個(gè)數(shù)的最大公約數(shù)為：" << 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;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: