算法歐幾里德與最大公約數(shù)

算法：歐幾里德與最大公約數(shù)任務(wù)嘗試編制程序來(lái)求解兩個(gè)整數(shù)的最大公約數(shù)，綜合運(yùn)用前面學(xué)習(xí)過(guò)的分支結(jié)婚的算法和循環(huán)結(jié)構(gòu)的算法。歐幾里得,（約公元前 330-275年），古希臘數(shù)學(xué)家。其著作《幾何原本》聞名于世， 2000多年來(lái)都被看作學(xué)習(xí)幾何的標(biāo)準(zhǔn)課本，所以稱歐幾里德為幾何之父。 歐幾里得將公元前七世紀(jì)以來(lái)希臘幾何積累起來(lái)的既豐富又紛紜的龐雜結(jié)果整理在一個(gè)嚴(yán)密統(tǒng)一的體系中， 從原始定義開始，列出條公設(shè)，通過(guò)邏輯推理，演繹出一系列定理和推論，從而建立了被稱為歐幾里得幾何學(xué)的第一個(gè)公理化數(shù)學(xué)體系。一、輾轉(zhuǎn)相除法歐幾里得在《幾何原本》第七卷中，提出的計(jì)算最大公約數(shù)的輾轉(zhuǎn)相除法至今仍在使用，也是基礎(chǔ)數(shù)學(xué)的一項(xiàng)基本內(nèi)容。這種方法比一般人們使用的窮舉法要簡(jiǎn)便、快捷得多，所以“輾轉(zhuǎn)相除法”又稱為歐幾里德算法。所謂“輾轉(zhuǎn)相除法”是指對(duì)于任何兩個(gè)自然數(shù)a、b，當(dāng)a>b時(shí)，活動(dòng)建議a=q*b+r。其中，q是b除a得到的部分商，r是a除以b后得到的余請(qǐng)說(shuō)出用數(shù)。顯然，當(dāng)r等于0時(shí)，b就是a、b的最大公約數(shù)。否則，a、b窮舉法求最大的最大公約數(shù)就等于b、r的最大公約數(shù)，這是因?yàn)閍與b的約數(shù)也一公約數(shù)的一般定是b與r的約數(shù)。而將b作為新的除式中的a，r作為新的除式中的算法。b，這樣反復(fù)求約數(shù)，直至r等于0，這時(shí)的b就是原先的a和b的最大公約數(shù)。下面，我們就編制一個(gè)小程序運(yùn)用“輾轉(zhuǎn)相除法”來(lái)求兩個(gè)整數(shù)的最大公約數(shù)。二、輾轉(zhuǎn)相除法的算法流程圖開始輸入正整數(shù) a輸入正整數(shù) bNo

Yesa>b？x=b

x=ay=a y=bNoy不等于0嗎?Yesr=x除以y的余數(shù)x=yy=rNo輸出x結(jié)束從流程圖中我們可以看出，首先輸入兩個(gè)自然數(shù)

a和

b。然后，通過(guò)分支判斷，將較大的數(shù)賦值給

x，較小的數(shù)賦值給

y。接下來(lái)，使用一個(gè)“當(dāng)”型循環(huán)結(jié)構(gòu)，先判斷

y（y是上次除式的余數(shù)，下次除式的除數(shù)）是否為

0，如果為

0說(shuō)明上次除式的除數(shù)（上次除式的 y就是下次除式的 x）就是原來(lái) x和y的最大公約數(shù)。那么，直接退出循環(huán)，輸出最大公約數(shù) x。如果不為0，則進(jìn)入循環(huán)體，計(jì)算 x除以y的余數(shù)，將余數(shù)賦值給r，再將本次除式除數(shù) y的值賦值給作為下次除式被除數(shù)的變量 x，將本次除式余數(shù)r的值賦值給作為下次除式除數(shù)的變量y。然后，重新回到“當(dāng)”型循環(huán)的入口。三、程序?qū)崿F(xiàn)范例：我用 VB編寫程序?qū)崿F(xiàn)這個(gè)算法。程序中用到了一個(gè)循環(huán)語(yǔ)句、一個(gè)分支語(yǔ)句、兩個(gè)輸入語(yǔ)句、一個(gè)輸出語(yǔ)句。1）建立窗體和輸出、命令按鈕組件對(duì)象。2）編寫“Command1”觸發(fā)的程序代碼。在“PrivateSubcommand1_click()”和“EndSub”之間輸入以下的程序代碼。DimaAsLong,bAsLong,rAsLong,xAsLong,yAsLonga=Text1.Textb=Text2.TextIfa>=bThenx=ay=bElsex=by=aEndIfDoWhiley<>0r=xModyx=yy=rLoopLabel1.Caption=x第一行，定義了 5個(gè)長(zhǎng)整型變量 a、b、r、x和y。第二行，通過(guò)文本輸入框獲取自然數(shù) a。第三行，通過(guò)文本輸入框獲取自然數(shù) b。第四行至第十行，通過(guò)雙分支條件語(yǔ)句，將 a、b中較大的數(shù)賦值給變量 x，較小的值賦值給變量 y。第十一行，判斷 y是否等于 0，使用的條件表達(dá)式是“ y<>0”。如果條件成立，則繼續(xù)執(zhí)行循環(huán)體第十二行的操作。 否則，結(jié)束循環(huán)，執(zhí)行Loop語(yǔ)句的下一行語(yǔ)句，即第十六行。

活動(dòng)建議嘗試畫出用窮舉法求最大公約數(shù)的算法流程圖。第十二行，將 x除以y的余數(shù)賦值給變量 r。第十三行，將 y的值賦值給變量 x。第十四行，將 r的值賦值給變量 y。第十五行，在Loop語(yǔ)句處，程序無(wú)條件轉(zhuǎn)向循環(huán)語(yǔ)句的入口 “DoWhile”語(yǔ)句。重新進(jìn)行條件判斷。第十六行，將x的值賦值給文本標(biāo)簽 Label1的caption屬性，用于輸出最大公約