辗转相除法在计算机程序设计上的实际应用

摘 要：对辗转相除法在计算机程序设计上的实际应用进行归纳：求最大公约数，求最小公倍数，如何判定二元一次不定方程有无整数解，如何把十进制整数部分转化为R进制。

关键词：N-S结构化流程图；PASCAL源程序；辗转相除法；计算机程序设计；实际应用

定理1：若A1、A2…An是N个不全为零的整数，则（A1，A2…An）=(|A1|，|A2|…|An|)

定理2：若B是任一个正整数，则（0，B）=B

推论：若B是任一非零整数，则（0，B）=|B|

以上两个引论易证，证明过程从略，这样在下文使用辗转相除法求最大公约数时就可以省去讨论正、负整数的麻烦，从而只需在自然数范围内进行讨论。

一、如何求两个整数的最大公约数

要想利用辗转相除法在微机上实现求任意两个整数最大公约数就必须先从键盘上输入两个整数M、N先求M除以N，看余数R是否为零，如果R为零则N就是M、N两个数的最大公约数，否则就应该把分母作为分子，把余数作为分母再一次利用分子除以分母求余，看余是否为零，若为零，则此时的分母就为M、N两数的最大公约数，否则还要把此时分母作为分子，余数作为分母，再一次判定分子除以分母看余数是否为零，依次类推，直到余数为零，则此时分母就为M、N两数的最大公约数。

例如：求28和12的最大公约数

28 MOD 12 余数为4 不为零

12 MOD 4 余数为0 为零

则28和12的最大公约数为4

用N-S结构化流程图来描述其算法如下：

［略］

PASCAL语言源程序

PROGRAM maxgys（INPUT，OUTPUT）；

VAR m，n，r:INTEGER；

BEGIN

WRITELN（‘input m and n data:’）；

READLN(m，n)；

r:=m MOD n；

WHILE r0 DO

BEGIN

m:=n；

n:=r；

r:=m MOD n；

END；

WRITELN（n）；

END.

在求出两个整数最大公约数的基础上，来求多个整数的最大公约数要作以下处理：先按上面的求法求出两个整数的最大公约数，然后再把求出的最大公约数和第三个整数放在一起作为两个新的整数再一次求其最大公约数，依次类推，即可求出多个整数的最大公约数。

二、如何求两个整数的最小公倍数

在上面，我们较详细地论述了如何求两个整数的最大公约数，在此基础上，再求两个整数的最小公倍数，则只需用原来两个整数的乘积除以最大公约数所得的商即为所要求的最小公倍数。

用N-S结构化流程图来描述其算法如下：

［略］

PASCAL语言源程序

PROGRAM mingbs（input，output）；

VAR a，b，m，n，r:INTEGER；

BEGIN

WRITELN（‘input m and n data:’）；

READLN(M，N)；

a:=m；

b:=n；

r:=m MOD n；

WHILE r0 DO

BEGIN

m:=n；

n:=r；

r:=m MOD n；

END；

WRITELN（a*b DIV n）；

WRITELN；

END.

例如：求28和12的最小公倍数

28和12的最大公约数为4

则该两数的最小公倍数为28*12 DIV 4即为84

在求出两个整数最小公倍数的基础上，再求多个整数的最小公倍数。用上面的求法先求出两个整数的最小公倍数，然后把求出的最小公倍数和第三个整数放在一起作为两个新的整数再一次求其最小公倍数，依次类推，即可求出多个整数的最小公倍数。

三、如何判断二元一次不定方程（AX+BY=C）有无整数解

在上面，我们已经较详细地论述了如何求两个整数的最大公约数，在上面的基础上，要判断二元一次不定方程有无整数解，只需要按上面论述的方法先求出A和B的最大公约数，然后再来判定C是否能整除A和B的最大公约数，如果能整除就有整数解，否则就无整数解。

用N-S结构化流程图来描述其算法如下：

［略］

例如：判定28x+12y=100有无整数解

28和12的最大公约数为4

100能整除４所以该方程有整数解

PASCAL语言源程序

PROGRAM ynzsj（INPUT，OUTPUT）；

VAR a，b，c，r:INTEGER；

BEGIN

WRITELN（‘input a，b，c data:’）；

READLN（a，b，c）；

r:=a MOD b；

WHILE R0 DO

BEGIN

a:=b；

b:=r；

r:=a MOD b；

END；

IF c MOD b=0

THEN WRITELN（‘该方程有整数解’）

ELSE WRITELN（‘该方程无整数解’）；

WRITELN；

END.

四、如何把十进制数的整数部分转化为R进制

要想把十进制数的整数部分转化为R进制（主要是二进制、八进制、十六进制）就必须从键盘上输入整数N和要想转化的进制R，并让S为1接着求N除以R的商M并把N除以R的余数放在A［S］中，若M为零，则按倒序输出A［S］，否则应该在S中加1放进S中并把M中的数放入N中，然后再求N除以R的商放入M中并把N除以R的余数放在A［S］中，再一次判定M是否为零，依次类推，直到M中的数为零，然后按倒序输出A［S］即可。

例如：把十进制10转化为二进制为多少？

S=1 10 除以2商为5 不为零 余数为0即A［S］=0

S=2 5 除以2商为2 不为零 余数为1即A［S］=1

S=3 2 除以2商为1 不为零 余数为0即A［S］=0

S=4 1 除以2商为0 为零 余数为1即A［S］=1

由上表可知 a［4］=1，a［3］=0，a［2］=1，a［1］=0

所以（10）10 =（1010）2

用N-S结构化流程图来描述其算法如下

［略］

PASCAL语言源程序

PROGRAM dtobjz（INPUT，OUTPUT）；

VAR i，r，m，n，s:INTEGER；

a:ARRAY［1…8］OF INTEGER；

BEGIN

WRITELN（‘请输入十进制的整数部分’）；

READLN(n)；

WRITELN（‘请输入转化为几进制’）；

READLN（r）；

s:=1；

m:=n DIV r；

a［s］:=n MOD r；

WHILE m0 DO

BEGIN

s:=s+1；

n:=m；

m:=n DIV r；

a［s］:=n MOD r；

END；

WRITELN（‘十进制数’，n，‘转化为’，R，‘进制数为：’）；

FOR i:=s DOWNTO 1 DO

WRITE（a［I］）；

WRITELN；

END.

作为一名计算机专业教师，在多年来的语言课教学中，我感悟最深的就是在学习语言课时要有意识、有目的地进行分门别类归纳和总结。通过归纳，能够加深对有关知识的理解，不要在学习语言时以点论点而应该以点带面，善于进行归纳和总结，如果就停留此水平上那还是不够的，还必须在总结和归纳的基础上经过深入思考并受其启发能够用已掌握知识来解决一些没有解决的问题。

参考文献：

闵嗣鹤，严士健.初等数论：2版.高等教育出版社，1957-11.

（作者单位 亳州中药科技学校）