C語言最大公約數(shù)示例教程
更新時間：2021年11月27日 16:24:44 作者：Pretend..
這篇文章主要為大家介紹了C語言最大公約數(shù)的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
窮舉法
（1） i=?a ，b中較小的數(shù)
（2）若a，b能同時被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)相除法求兩個數(shù)的最大公約數(shù)的步驟如下：
（1）先用小的一個數(shù)除大的一個數(shù)，得第一個余數(shù)；
（2）再用第一個余數(shù)除小的一個數(shù)，得第二個余數(shù)；
（3）又用第二個余數(shù)除第一個余數(shù)，得第三個余數(shù)；
這樣逐次用后一個數(shù)去除前一個余數(shù)，直到余數(shù)是0為止。那么，最后一個除數(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語言最大公約數(shù)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語言最大公約數(shù)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
堆和棧都是一種數(shù)據(jù)項按序排列的數(shù)據(jù)結(jié)構(gòu)。在C語言中是非常重要的知識點，接下來通過本文給大家介紹C語言中堆和棧的區(qū)別，感興趣的朋友一起看下吧2016-06-06
這篇文章主要介紹了基于C++實現(xiàn)的各種內(nèi)部排序算法,非常經(jīng)典,需要的朋友可以參考下2014-08-08
下面小編就為大家?guī)硪黄狢++之類和對象課后習(xí)題簡單實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-07-07
這個程序還是比較復(fù)雜的，把這句話作為文章的開頭可以看出它的真實性.....這篇文章主要介紹了文本查詢程序的實現(xiàn)，下面我們一起來看看2022-06-06
ReadDirectoryChangesW是Windows操作系統(tǒng)提供的一個函數(shù),用于監(jiān)視目錄的變化,本文主要為大家介紹了如何使用ReadDirectoryChangesW實現(xiàn)監(jiān)控目錄文件變化,需要的可以參考下2023-11-11
最近需要寫一個程序，要是讓qt到程序自適應(yīng)，本文主要介紹了Qt地圖自適應(yīng)拉伸的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要為大家詳細(xì)介紹了c/c++實現(xiàn)圖書信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了C語言執(zhí)行程序時遇到的常見問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了希爾排序算法的C語言實現(xiàn)示例,希爾排序可以看作為一種高級的插入排序,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細(xì)介紹了OpenCV實現(xiàn)人臉檢測功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02