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

1、用迭代法求兩個數(shù)的最大公約數(shù)和最小公倍數(shù)化工 09110605摘要：迭代法是一種循環(huán)控制語句和循環(huán)結(jié)構(gòu)程序的設(shè)計方法。在計算機(jī)解決問 題的時候，總希望從復(fù)雜的問題中找到規(guī)律，并歸結(jié)為簡單問題的重復(fù)，發(fā)揮其 擅長重復(fù)運(yùn)算的特點(diǎn)，讓它重復(fù)執(zhí)行一組語句，直到滿足給定條件為止。因此， c語言提供了重復(fù)操作的語句，由這些語句構(gòu)成的程序稱為循環(huán)結(jié)構(gòu)。本文就 是采用迭代法，利用c語言中提供的重復(fù)語句，求得兩個數(shù)的最大公約數(shù)和最小 公倍數(shù)。關(guān)鍵詞：循環(huán)語句；循環(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è)計是程序設(shè)計的關(guān)鍵，也是程序設(shè)計的難點(diǎn)。選擇算法的標(biāo)準(zhǔn)首先是 算法的正確性、可靠性和易理解性；其次就是算法所需要的存儲空間要小、運(yùn)算 速度要快等。迭代法也稱為輾轉(zhuǎn)法，是一種不

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

6、2）調(diào)用函數(shù)完成要求的功能。（3）輸出結(jié)果。本文是用迭代法解決該問題的。2、原理：求兩個數(shù)x、y的最大公約數(shù)和最小公倍數(shù)。最小公倍數(shù)=x*y/g大公約數(shù)；所以關(guān)鍵就是求得最大公約數(shù)。本文采用“輾 轉(zhuǎn)相除法”求最大公約數(shù)。輾轉(zhuǎn)相除法就是重復(fù)做：求a除以b的余數(shù)p；a等于原來的b；b等 于p，直到p等于0時，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程序測試：x, y=18, 12(回車)6, 363、算法設(shè)計:輸入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é)論：迭代法是求得兩個數(shù)最大公約數(shù)和最小公倍數(shù)的常用程序設(shè)計方法，它 的程序編譯較為簡單，完成要求效率較高。建議遇到求解相關(guān)問題時，優(yōu)先考慮 該種方法。其次是運(yùn)用函數(shù)互相調(diào)用的方法（前言中提及到的），用該種方法時 最好是編程人手多，每個人分別編輯實現(xiàn)功能不同的函數(shù)模塊，最后將各函數(shù)吻 合到一起歸為一個程序，從而解決問題。如果單人獨(dú)自完成該程序的調(diào)試，那么 會容易出現(xiàn)錯