一道程序设计习题的数学原理

黄绍龙

摘要：该文介绍了欧几里得算法以及两正整数与它们的最大公约数和最小公倍数的等积关系，并给出了证明。

关键词：欧几里得算法；迭代；最大公约数；最小公倍数

中图分类号：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程序设计》是被广泛使用的教程，其中第6章课后的一道习题是：输入两个正整数和，求其最大公约数和最小公倍數.该题目是想通过这一章的知识重点循环结构来求解.一般有两种思路：1）依据最大公约数和最小公倍数的定义；2）先依据数论中的欧几里得算法（又称辗转相除法）求最大公约数，再利用“等积关系”求最小公倍数.第一种方法直观且易于理解，而第二种方法是课本给出的参考答案，但没有说明原理，我们不容易接受.本文通过解释并证明第二种方法的数学原理，使我们对此方法有更加深入透彻的理解.

4 函数实现

1）求最大公约数函数

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）求最小公倍数函数

int lcm（int m，int n）

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

5 结论

程序设计课程要达到的目标不仅仅是语言知识的获得和动手能力的培养，还应该着眼于更高层次的思维活动，即算法背后蕴藏的原理，使学生体会思考的乐趣，知其然知其所以然，从而对知识有更加深入的理解，掌握的也更加牢固.

参考文献：

[1] Ronald L Graham.Concrete Mathematics[M].北京：机械工业出版社，2002.

[2] 谭浩强.C程序设计[M].3版.北京：清华大学出版社，2005.