黃紹龍

摘要：該文介紹了歐幾里得算法以及兩正整數(shù)與它們的最大公約數(shù)和最小公倍數(shù)的等積關(guān)系，并給出了證明。

關(guān)鍵詞：歐幾里得算法；迭代；最大公約數(shù)；最小公倍數(shù)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）06-0111-01

Abstract： This article introduces the Euclids algorithm and the equal-product relationship between two positive integers and their greatest common divisor and least common multiple， it also gives the proofs.

Key words： Euclids algorithm； iteration； greatest common divisor； least common multiple

清華大學(xué)出版社出版、譚浩強(qiáng)編著的《C程序設(shè)計》是被廣泛使用的教程，其中第6章課后的一道習(xí)題是：輸入兩個正整數(shù)和，求其最大公約數(shù)和最小公倍數(shù).該題目是想通過這一章的知識重點(diǎn)循環(huán)結(jié)構(gòu)來求解.一般有兩種思路：1）依據(jù)最大公約數(shù)和最小公倍數(shù)的定義；2）先依據(jù)數(shù)論中的歐幾里得算法（又稱輾轉(zhuǎn)相除法）求最大公約數(shù)，再利用“等積關(guān)系”求最小公倍數(shù).第一種方法直觀且易于理解，而第二種方法是課本給出的參考答案，但沒有說明原理，我們不容易接受.本文通過解釋并證明第二種方法的數(shù)學(xué)原理，使我們對此方法有更加深入透徹的理解.

4 函數(shù)實(shí)現(xiàn)

1）求最大公約數(shù)函數(shù)

int gcd（int m，int n）

{

int r，t；

if（m>n） {t=m；m=n；n=t；}

while（m！=0）{t=n%m；n=m；m=t；}

return n；

}

2）求最小公倍數(shù)函數(shù)

int lcm（int m，int n）

{ return m*n/gcd（m，n）； }

5 結(jié)論

程序設(shè)計課程要達(dá)到的目標(biāo)不僅僅是語言知識的獲得和動手能力的培養(yǎng)，還應(yīng)該著眼于更高層次的思維活動，即算法背后蘊(yùn)藏的原理，使學(xué)生體會思考的樂趣，知其然知其所以然，從而對知識有更加深入的理解，掌握的也更加牢固.

參考文獻(xiàn)：

[1] Ronald L Graham.Concrete Mathematics[M].北京：機(jī)械工業(yè)出版社，2002.

[2] 譚浩強(qiáng).C程序設(shè)計[M].3版.北京：清華大學(xué)出版社，2005.