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í)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針
這篇文章主要介紹了C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-11-11
C語(yǔ)言中邏輯運(yùn)算符與條件運(yùn)算符的學(xué)習(xí)教程
這篇文章主要介紹了C語(yǔ)言中邏輯運(yùn)算符與條件運(yùn)算符的學(xué)習(xí)教程,條件運(yùn)算符問(wèn)號(hào)即三目運(yùn)算符使用起來(lái)十分方便,需要的朋友可以參考下
2016-04-04
C語(yǔ)言關(guān)于自定義數(shù)據(jù)類型之枚舉和聯(lián)合體詳解
枚舉顧名思義就是把所有的可能性列舉出來(lái)，像一個(gè)星期分為七天我們就可以使用枚舉，聯(lián)合體是由關(guān)鍵字union和標(biāo)簽定義的，和枚舉是一樣的定義方式，不一樣的是，一個(gè)聯(lián)合體只有一塊內(nèi)存空間，什么意思呢，就相當(dāng)于只開(kāi)辟最大的變量的內(nèi)存，其他的變量都在那個(gè)變量占據(jù)空間
2021-11-11
C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析
這篇文章主要介紹了C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-11-11
深入了解C語(yǔ)言中常見(jiàn)的文件操作方法
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中常見(jiàn)的文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-06-06
C++ getcwd函數(shù)獲取項(xiàng)目運(yùn)行路徑方法詳解
在Linux下做QT項(xiàng)目時(shí)，需要獲取項(xiàng)目的運(yùn)行路徑，于是用getcwd函數(shù)進(jìn)行獲取，然后在Windows下進(jìn)行測(cè)試，發(fā)現(xiàn)獲取到的是程序的項(xiàng)目路徑，即代碼文件路徑，然后再Linux QT中測(cè)試，獲取到的又是運(yùn)行路徑，這就很納悶了。經(jīng)過(guò)再三測(cè)試，終于發(fā)現(xiàn)了原因
2022-10-10
C語(yǔ)言使用鏈表實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言使用鏈表實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2019-12-12
C++ Leetcode實(shí)現(xiàn)從英文中重建數(shù)字
本文主要介紹了當(dāng)給你一個(gè)字符串s，其中包含字母順序打亂的用英文單詞表示的若干數(shù)字（0-9）時(shí)，如何通過(guò)Leetcode按升序返回原始的數(shù)字。感興趣的童鞋可以來(lái)看看
2021-11-11
C++單例類模板詳解
這篇文章主要介紹了C++單例類模板，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2019-03-03
C語(yǔ)言的遞歸函數(shù)詳解
這篇文章主要為大家介紹了C語(yǔ)言的遞歸函數(shù)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助
2022-01-01