C語(yǔ)言中如何調(diào)用函數(shù)求最大公約數(shù)和最小公倍數(shù)

C語(yǔ)言求最大公約數(shù)和最小公倍數(shù)(2010-03-20 22:23:46)轉(zhuǎn)載標(biāo)簽： 雜談 分類： 編程

成都創(chuàng)新互聯(lián)公司成立于2013年，先為改則等服務(wù)建站，改則等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為改則企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

求最大公約數(shù)和最小公倍數(shù)

假設(shè)有兩個(gè)數(shù)a和b，求a,b的最大公約數(shù)和最小公倍數(shù)實(shí)際上是一個(gè)問(wèn)題，得出這兩個(gè)數(shù)的最大公約數(shù)就可以算出它們的最小公倍數(shù)。

最小公倍數(shù)的公式是 a*b/m

m為最大公約數(shù)

因?yàn)?/p>

a=m*i; b=m*j;

最小公倍數(shù)為 m*i*j

那么，下面就開(kāi)始計(jì)算a和b的最大公約數(shù)。

更相損減法：

《九章算術(shù)·方田》作分?jǐn)?shù)約簡(jiǎn)時(shí)，提到求最大公因數(shù)方法：反覆把兩數(shù)的較大者減去較小者，直至兩數(shù)相等，這數(shù)就是最大公因數(shù)。這方法除了把除法換作減法外，與輾轉(zhuǎn)相除法完全相同。例如書(shū)中求91和49的最大公因數(shù)：

91 49, 91 - 49 = 42

49 42, 49 - 42 = 7

42 7, 42 - 7 = 35

35 7, 35 - 7 = 28

28 7, 28 - 7 = 21

21 7, 21 - 7 = 14

14 7, 14 - 7 = 7

7 = 7, 因此91和49的最大公因數(shù)是7

輾轉(zhuǎn)相除法：

輾轉(zhuǎn)相除法是利用以下性質(zhì)來(lái)確定兩個(gè)正整數(shù) a 和 b 的最大公因數(shù)的：

若 r 是 a ÷ b 的馀數(shù), 則

gcd(a,b) = gcd(b,r)

a 和其倍數(shù)之最大公因數(shù)為 a。

另一種寫(xiě)法是：

a ÷ b，令r為所得馀數(shù)（0≤r＜b）

若 r = 0，演算法結(jié)束；b 即為答案。

互換：置 a←b，b←r，并返回第一步。

這個(gè)算法可以用遞歸寫(xiě)成如下:

function gcd(a, b) {

if a mod b0

return gcd(b, a mod b);

else

return a;

}

或純使用循環(huán):

function gcd(a, b) {

define r as integer;

while b ≠ 0 {

r := a mod b;

a := b;

b := r;

}

return a

}

其中“a mod b”是指取 a ÷ b 的余數(shù)。

C語(yǔ)言：

#include stdio.h

int gcd(int a,int b)//最大公約數(shù)

{

if (ab) return gcd(b,a);

else if (b==0) return a;

else return gcd(b,a%b);

}

int lcm(int a,int b)

{

return a*b/gcd(a,b);

}

main()

{

int a,b;

scanf("%d%d",a,b);

printf("最大公約數(shù)：%d\n",gcd(a,b));

printf("最小公倍數(shù)：%d\n",lcm(a,b));

}

輸入兩個(gè)正整數(shù)m和n, 求其最大公約數(shù)和最小公倍數(shù). 1 用輾轉(zhuǎn)相除法求最大公約數(shù) 算法描述: m對(duì)n求余為a, 若a不等于0 則 m - n, n - a, 繼續(xù)求余 否則 n 為最大公約數(shù) 2 最小公倍數(shù) = 兩個(gè)數(shù)的積 / 最大公約數(shù)

#include int main()

{

int m, n; int m_cup, n_cup, res;

printf("Enter two integer:\n");

scanf("%d %d", m, n);

if (m 0 n 0)

{

m_cup = m;

n_cup = n;

res = m_cup % n_cup;

while (res != 0)

{

m_cup = n_cup;

n_cup = res;

res = m_cup % n_cup;

}

printf("Greatest common divisor: %d\n", n_cup);

printf("Lease common multiple : %d\n", m * n / n_cup);

}

else printf("Error!\n");

return 0;

}

★ 關(guān)于輾轉(zhuǎn)相除法, 搜了一下, 在我國(guó)古代的《九章算術(shù)》中就有記載，現(xiàn)摘錄如下: 約分術(shù)曰：“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。” 其中所說(shuō)的“等數(shù)”，就是最大公約數(shù)。求“等數(shù)”的辦法是“更相減損”法，實(shí)際上就是輾轉(zhuǎn)相除法。輾轉(zhuǎn)相除法求最大公約數(shù)，是一種比較好的方法，比較快。對(duì)于52317和75569兩個(gè)數(shù)，你能迅速地求出它們的最大公約數(shù)嗎？一般來(lái)說(shuō)你會(huì)找一找公共的使因子，這題可麻煩了，不好找，質(zhì)因子大。現(xiàn)在教你用輾轉(zhuǎn)相除法來(lái)求最大公約數(shù)。先用較大的75569除以52317，得商1，余數(shù)23252，再以52317除以23252，得商2，余數(shù)是5813，再用23252做被除數(shù)，5813做除數(shù)，正好除盡得商數(shù)4。這樣5813就是75569和52317的最大公約數(shù)。你要是用分解使因數(shù)的辦法，肯定找不到。那么，這輾轉(zhuǎn)相除法為什么能得到最大公約數(shù)呢？下面我就給大伙談?wù)劇１热缯f(shuō)有要求a、b兩個(gè)整數(shù)的最大公約數(shù)，a＞b，那么我們先用a除以b，得到商8，余數(shù)r1：a÷b＝q1…r1我們當(dāng)然也可以把上面這個(gè)式子改寫(xiě)成乘法式：a＝bq1＋r1------l）如果r1＝0，那么b就是a、b的最大公約數(shù)3。要是r1≠0，就繼續(xù)除，用b除以r1，我們也可以有和上面一樣的式子： b＝r1q2＋r2-------2）如果余數(shù)r2＝0，那么r1就是所求的最大公約數(shù)3。為什么呢？因?yàn)槿绻?）式變成了b＝r1q2，那么b1r1的公約數(shù)就一定是a1b的公約數(shù)。這是因?yàn)橐粋€(gè)數(shù)能同時(shí)除盡b和r1，那么由l）式，就一定能整除a，從而也是a1b的公約數(shù)。反過(guò)來(lái)，如果一個(gè)數(shù)d，能同時(shí)整除a1b，那么由1）式，也一定能整除r1，從而也有d是b1r1的公約數(shù)。這樣，a和b的公約數(shù)與b和r1的公約數(shù)完全一樣，那么這兩對(duì)的最大公約數(shù)也一定相同。那b1r1的最大公約數(shù)，在r1＝0時(shí)，不就是r1嗎？所以a和b的最大公約數(shù)也是r1了。有人會(huì)說(shuō)，那r2不等于0怎么辦？那當(dāng)然是繼續(xù)往下做，用r1除以r2，……直到余數(shù)為零為止。在這種方法里，先做除數(shù)的，后一步就成了被除數(shù)，這就是輾轉(zhuǎn)相除法名字的來(lái)歷吧。

C語(yǔ)言編程：從鍵盤(pán)輸入兩個(gè)正整數(shù)a和b，求a和b的最小公倍數(shù)，咋做？

代碼文本：

#include "stdio.h"

int mylcm(int a,int b){//求LCM函數(shù)

int t;

if(ab)

t=a,a=b,b=t;

for(t=a;t%b;t+=a);

return t;//返回LCM

}

int main(int argc,char *argv[]){

int a,b;

printf("Enter a b(int a0,b0)...\n");

if(scanf("%d%d",a,b)==2 a0 b0)

printf("The LCM is %d\n",mylcm(a,b));

else//提示輸入錯(cuò)誤并退出

printf("Input error, exit...\n");

return 0;

}

比較簡(jiǎn)單，供參考……

c語(yǔ)言中l(wèi)cm是什么意思？

最小公倍數(shù)

英文全稱:

Lowest Common Multiple

這不僅是C語(yǔ)言中的標(biāo)識(shí)符，通常在別的計(jì)算機(jī)語(yǔ)言中，也是這么標(biāo)識(shí)的。

本文題目：c語(yǔ)言函數(shù)lcm,C語(yǔ)言函數(shù)嵌套
分享地址：http://chinadenli.net/article27/dsepocj.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、企業(yè)建站、網(wǎng)站收錄、網(wǎng)站內(nèi)鏈、搜索引擎優(yōu)化、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)