系列文章目錄
C語言系列基礎演算法系列，每一篇博主都是努力做到用最多最優的解法實作，如果有想要了解的其他演算法可以評論區留言哦！
整數排序的幾種方法
兩種平均成績題型
求兩個數的較大值
最大公約數的幾種求法
- 系列文章目錄
- 前言
- 一、問題描述
- 二、問題分析
- ps：
- 問題解法
- 判斷是否互質：
- 解法一：窮舉法
- 解法二：輾轉相除法
- 解法三：輾轉相減法
- 總結
前言
最大公約數（gcd）是C語言學習程序中經常遇到的一種演算法題，本篇博文將介紹求出兩個數的最大公約數的各種解法，
提示：以下是本篇文章正文內容，下面案例可供參考
一、問題描述
求任意兩個正整數的最大公約數（GCD），
二、問題分析
如果有一個自然數 a 能被自然數 b 整除，則稱 a 為 b 的倍數，b 為 a 的約數，幾個自然數公有的約數，叫做這幾個自然數的公約數，公約數中最大的一個公約數，稱為這幾個自然數的最大公約數，
根據約數的定義可知，某個數的所有約數必不大于這個數本身，幾個自然數的最大公約數必不大于其中任何一個數，要求任意兩個正整數的最大公約數即求出一個不大于其中兩者中的任何一個，但又能同時整除兩個整數的最大自然數
ps：
在我們求最大公約數的時候，要考慮兩個數是否互質，如果互質，則沒有最大公約數，所以我們在寫代碼的時候應該先判斷兩個是的互質情況，
問題解法
判斷是否互質：
判斷互質我們需要直到兩點：
1.互質指最大公約數等于1的兩個自然數，
2.1和任意數互質，
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
// 如果是互質數回傳0，不是則回傳1
int is_coprime(int x, int y)
{
if (1 == x || 1 == y)
{
return 1;
}
int z = 0;
while (z = x % y)
{
if (0 == z)
{
break;
}
else
{
x = y;
y = z;
}
}
if (1 == y)
{
return 0;
}
else
{
return 1;
}
}
int main()
{
int a = 0;
int b = 0;
//輸入
scanf("%d %d", &a, &b);
//判斷是否為互質數
int ret = is_coprime(a, b);
return 0;
}
解法一：窮舉法
因為公約數絕對不能超過兩個自然數本身，所以第一思路應該是在兩個數之間找到較小的那個，逐步自減一，直到找到一個能同時被兩個自然數整除的公約數，就是最大公約數
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
// 如果是互質數回傳0，不是則回傳1
int is_coprime(int x, int y)
{
if (1 == x || 1 == y)
{
return 0;
}
int z = 0;
while (z = x % y)
{
if (0 == z)
{
break;
}
else
{
x = y;
y = z;
}
}
if (1 == y)
{
return 0;
}
else
{
return 1;
}
}
int GCD1(int x, int y)
{
int tmp = 0;
//讓x為較小的數
if (x > y)
{
//交換x，y的值
tmp = x;
x = y;
y = tmp;
}
int i = 0;
//從大到小找到符合條件的數
for (i = x; i > 0; i--)
{
if (0 == (x % i) && 0 == (y % i))
{
break;
}
}
return i;
}
int main()
{
int a = 0;
int b = 0;
int gcd = 0;
//輸入
scanf("%d %d", &a, &b);
//判斷是否為互質數
int ret = is_coprime(a, b);
if (ret)
{
gcd = GCD1(a, b);
}
printf("最大公約數為：%d\n", gcd);
return 0;
}
后文解法單獨給出函式代碼，互質數及主函式可與解法一相同
解法二：輾轉相除法
圖示：
代碼：
int GCD2(int x, int y)
{
int z = 0;
while (z = x % y)
{
x = y;
y = z;
}
return y;
}
解法三：輾轉相減法
圖示：
代碼：
int GCD3(int x, int y)
{
//兩個數一直相減直到相等
while (x != y)
{
if (x > y)
{
x -= y;
}
else
{
y -= x;
}
}
return x;
}
總結
以上為三種求最大公約數的方法，希望能夠給大家帶來幫助
有想要整理的內容歡迎各位評論區留言嗷！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/292226.html
標籤：其他