一道程序設(shè)計習題的數(shù)學原理

黃紹龍

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

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

中圖分類號：TP311 文獻標識碼：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

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

4 函數(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è)計課程要達到的目標不僅僅是語言知識的獲得和動手能力的培養(yǎng)，還應(yīng)該著眼于更高層次的思維活動，即算法背后蘊藏的原理，使學生體會思考的樂趣，知其然知其所以然，從而對知識有更加深入的理解，掌握的也更加牢固.

參考文獻：

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

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