C語(yǔ)言最大公約數(shù)示例教程
窮舉法
（1） i=?a ，b中較小的數(shù)
（2）若a，b能同時(shí)被i整除，則i即為最大公約數(shù)，結(jié)束
（3）若不能，則 i--，再回去執(zhí)行（2）
#include<stdio.h>
int main()
{
int i = 0;
int j = 0;
scanf("%d %d", &i, &j);
int k = i > j ? i : j;//i>j,k=i;i<j,k=j
while(1)
{
if (i%k == 0 && j%k == 0)
{
printf("最大公約數(shù)為；%d\n", k);
break;
}
k--;
}
return 0;
}
?輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的步驟如下：
（1）先用小的一個(gè)數(shù)除大的一個(gè)數(shù)，得第一個(gè)余數(shù)；
（2）再用第一個(gè)余數(shù)除小的一個(gè)數(shù)，得第二個(gè)余數(shù)；
（3）又用第二個(gè)余數(shù)除第一個(gè)余數(shù)，得第三個(gè)余數(shù)；
這樣逐次用后一個(gè)數(shù)去除前一個(gè)余數(shù)，直到余數(shù)是0為止。那么，最后一個(gè)除數(shù)就是所求的最大公約數(shù)。
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
int c = 0;
scanf("%d %d", &a, &b);
while (c = a%b)
{
a = b;
b = c;
}
printf("%d\n", b);
return 0;
}
?輾轉(zhuǎn)相減法
兩整數(shù)a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數(shù)的最大公約數(shù)，結(jié)束
（4）若a≠b，則再回去執(zhí)行（1）
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);
int ret = 0;
while (1)
{
if (a < b)
{
int tmp = 0;
tmp = a;
a = b;
b = tmp;
}
ret = a - b;
if (ret == b)//判斷
{
printf("ret = %d", ret);
break;
}
else//交換
{
a = b;
b = ret;
}
}
return 0;
}
以上就是C語(yǔ)言最大公約數(shù)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言最大公約數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
堆和棧都是一種數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu)。在C語(yǔ)言中是非常重要的知識(shí)點(diǎn)，接下來(lái)通過(guò)本文給大家介紹C語(yǔ)言中堆和棧的區(qū)別，感興趣的朋友一起看下吧2016-06-06
基于C++實(shí)現(xiàn)的各種內(nèi)部排序算法匯總
這篇文章主要介紹了基于C++實(shí)現(xiàn)的各種內(nèi)部排序算法,非常經(jīng)典,需要的朋友可以參考下2014-08-08
C++之類和對(duì)象課后習(xí)題簡(jiǎn)單實(shí)例
下面小編就為大家?guī)?lái)一篇C++之類和對(duì)象課后習(xí)題簡(jiǎn)單實(shí)例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-07-07
C++詳解Primer文本查詢程序的實(shí)現(xiàn)
這個(gè)程序還是比較復(fù)雜的，把這句話作為文章的開頭可以看出它的真實(shí)性.....這篇文章主要介紹了文本查詢程序的實(shí)現(xiàn)，下面我們一起來(lái)看看2022-06-06
C/C++實(shí)現(xiàn)監(jiān)控目錄文件變化
ReadDirectoryChangesW是Windows操作系統(tǒng)提供的一個(gè)函數(shù),用于監(jiān)視目錄的變化,本文主要為大家介紹了如何使用ReadDirectoryChangesW實(shí)現(xiàn)監(jiān)控目錄文件變化,需要的可以參考下2023-11-11
Qt地圖自適應(yīng)拉伸的實(shí)現(xiàn)示例
最近需要寫一個(gè)程序，要是讓qt到程序自適應(yīng)，本文主要介紹了Qt地圖自適應(yīng)拉伸的實(shí)現(xiàn)示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
C/C++實(shí)現(xiàn)圖書信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了c/c++實(shí)現(xiàn)圖書信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
C語(yǔ)言執(zhí)行程序時(shí)遇到的常見問題及解決
這篇文章主要介紹了C語(yǔ)言執(zhí)行程序時(shí)遇到的常見問題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了希爾排序算法的C語(yǔ)言實(shí)現(xiàn)示例,希爾排序可以看作為一種高級(jí)的插入排序,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)人臉檢測(cè)功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02