用迭代法求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)

1、用迭代法求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)化工 09110605摘要：迭代法是一種循環(huán)控制語(yǔ)句和循環(huán)結(jié)構(gòu)程序的設(shè)計(jì)方法。在計(jì)算機(jī)解決問(wèn) 題的時(shí)候，總希望從復(fù)雜的問(wèn)題中找到規(guī)律，并歸結(jié)為簡(jiǎn)單問(wèn)題的重復(fù)，發(fā)揮其 擅長(zhǎng)重復(fù)運(yùn)算的特點(diǎn)，讓它重復(fù)執(zhí)行一組語(yǔ)句，直到滿足給定條件為止。因此， c語(yǔ)言提供了重復(fù)操作的語(yǔ)句，由這些語(yǔ)句構(gòu)成的程序稱為循環(huán)結(jié)構(gòu)。本文就 是采用迭代法，利用c語(yǔ)言中提供的重復(fù)語(yǔ)句，求得兩個(gè)數(shù)的最大公約數(shù)和最小 公倍數(shù)。關(guān)鍵詞：循環(huán)語(yǔ)句；循環(huán)結(jié)構(gòu)；迭代法；最大公約數(shù)和最小公倍數(shù)Iterative Method with the greatest common divisor and lea

2、stcommon multiple of two numbersChemical 09110605 WANG MengAbstract: The iterative method is a loop control statement and loop structure design process. When the computer to solve the problem, hoping to find from the law of complex issues and boil down to a simple repetition of questions, to play th

3、e good characteristics of repeat operation, let it repeat a set of statements until the date that satisfies the given conditions. Therefore, c language repeat the statement provided by these statements constitute the program is called loop structure. This is the iterative method, using c language pr

4、ovided by the repeated statement, obtained the greatest common divisor and least common multiple of two numbers.Key words: loop; loop structure; iteration; greatest common divisor and least common multiple1、前言：算法設(shè)計(jì)是程序設(shè)計(jì)的關(guān)鍵，也是程序設(shè)計(jì)的難點(diǎn)。選擇算法的標(biāo)準(zhǔn)首先是 算法的正確性、可靠性和易理解性；其次就是算法所需要的存儲(chǔ)空間要小、運(yùn)算 速度要快等。迭代法也稱為輾轉(zhuǎn)法，是一種不

5、斷用變量的原值推導(dǎo)出新值的方法。用迭代 法有三個(gè)要點(diǎn)：一是確定迭代變量，在可以用迭代法解決問(wèn)題中，必須存在一個(gè) 或多個(gè)直接或間接地不斷由原值遞推出的新值的變量，這個(gè)變量就是迭代變量； 二是建立迭代關(guān)系，即如何從變量的前一個(gè)值推出下一個(gè)值;三是迭代結(jié)束條件， 即需要迭代的次數(shù)無(wú)法確定，直到滿足某種條件結(jié)束。所以通常采用條件控制， 用while語(yǔ)句或dowhile語(yǔ)句實(shí)現(xiàn)。解決這種求得兩數(shù)最大公約數(shù)和最小公倍數(shù)的問(wèn)題，還可以用調(diào)用函數(shù)的方 法，即編寫兩個(gè)函數(shù)，分別求兩個(gè)整數(shù)的最大公約數(shù)和最小公倍數(shù)。然后用主函 數(shù)進(jìn)行調(diào)用這兩個(gè)函數(shù)，在這種方法中主函數(shù)總是包括如下內(nèi)容：（1）輸入數(shù)據(jù)（如果需要）。（

6、2）調(diào)用函數(shù)完成要求的功能。（3）輸出結(jié)果。本文是用迭代法解決該問(wèn)題的。2、原理：求兩個(gè)數(shù)x、y的最大公約數(shù)和最小公倍數(shù)。最小公倍數(shù)=x*y/g大公約數(shù)；所以關(guān)鍵就是求得最大公約數(shù)。本文采用“輾 轉(zhuǎn)相除法”求最大公約數(shù)。輾轉(zhuǎn)相除法就是重復(fù)做：求a除以b的余數(shù)p；a等于原來(lái)的b；b等 于p，直到p等于0時(shí)，a就是最大公約數(shù)。其中迭代變量是a和b；迭代關(guān)系是a=b，b=p；迭代結(jié)束條件是p等于0。2、1 NS 圖：2、2程序代碼：void main() int x,y,a,b,p;printf(x,y=);scanf(%d,%d,&x,&y);a=x;b=y;do p=a%b;a=b;b=p; w

7、hile(p!=0);printf(%d,%dn,a,x*y/a);A程序測(cè)試：x, y=18, 12(回車)6, 363、算法設(shè)計(jì):輸入x、y,并分別送到a、b中求最大公約數(shù)（保留x, y求最小公倍數(shù)）。 重復(fù)執(zhí)行：p=a%b；a=b；b=p；，直到p=0，a即為最大公約數(shù)。 最小公倍數(shù)=x*y/a。4、結(jié)論：迭代法是求得兩個(gè)數(shù)最大公約數(shù)和最小公倍數(shù)的常用程序設(shè)計(jì)方法，它 的程序編譯較為簡(jiǎn)單，完成要求效率較高。建議遇到求解相關(guān)問(wèn)題時(shí)，優(yōu)先考慮 該種方法。其次是運(yùn)用函數(shù)互相調(diào)用的方法（前言中提及到的），用該種方法時(shí) 最好是編程人手多，每個(gè)人分別編輯實(shí)現(xiàn)功能不同的函數(shù)模塊，最后將各函數(shù)吻 合到一起歸為一個(gè)程序，從而解決問(wèn)題。如果單人獨(dú)自完成該程序的調(diào)試，那么 會(huì)容易出現(xiàn)錯(cuò)