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

王鹏

摘要：本文从最大公约数、最小公倍数以及判断二元一次不定方程整数解等三个问题阐述了计算机程序设计上对于辗转相除法的实际应用过程。旨在明确辗转相除法在计算机程序设计方面的重要利用价值，通过应用辗转相除法更加快速、高效的解决大部分的数据计算问题，表明计算机程序具有简单、快捷的广泛运用前景。

关键词：计算机程序设计；辗转相除法；实际应用

中图分类号：TP311.1 文献标识码：A 文章编号：1007-9416（2017）06-0078-02

1 利用辗转相除法求最大公约数

根据最大公约数的代数定义，在利用辗转相除法求取算式的最大公约数时，通过数字之间的反复、重复相除过程实现该算式最大公约数的求取。具体过程如下：设定已知的整数X和Y，列式“X÷Y”，并计算X除以Y的值。主要观察式子“X÷Y”所得余数的数值，用字母Z表示。会有如下两种计算结果：第一，当“Z=0”时，这种情况较为简单，此时Y称之为X与Y的最大公约数。第二，当“Z≠0”时，列式“Y÷Z”继续进行计算，再判断所得余数Z1是否为0。当“Z1=0”时，此时Z就是X与Y的最大公约数；当“Z1≠0”时，再列式“Z÷Z1”进行计算，得到余数Z2，继续判断Z2是否为0，重复和按照上一循环的判断标准，直至“Zn=0”的情况出现，此时计算得到Zn算式中的分母Zn-1就是X和Y的最大公约数[1]。

例一：（a）求整数31260和6252的最大公约数。（b）求整数12345与765的最大公约数。具体计算过程如下：（a）根据“X÷Y”列式计算得“31260÷6252=5”，此时余数为0，因此整数31260和6252的最大公约数为6252。（b）根据“X÷Y”列式计算得“12345÷765=16……105”，此时余数不为0，因此继续列式计算得“765÷105=7……30”，此时余数仍然不为0，因此继续列式计算“105÷30=3……15”，此时余数不为0，因此继续列式计算“30÷15=2”，此时余数为0，最终计算得到12345与765的最大公约数为15。

运用计算机技术，利用辗转相除法求最大公约数，所需要的编成表达如图1所示。

其中M、N分别指代的两个整数，R指代余数，分别将题（a）和题（b）中的数据带入计算机程序中进行运用，具体做法如下：

（a）直接将整数31260输入程序框内，提行输入整数6252，按下运算键“1”之后得到的计算结果显示为：？/31260/？/6252/6252/-Disp-.（b）直接将整数12345输入程序框内，提行输入整数765，按运算键“1”之后得到计算结果显示为：？/12345/？/765/15/-Disp-。

2 利用辗转相除法求最小公倍数

算式与整数的最小公倍数求法，是在求得其最大公约数的基础上进行的。利用辗转相除法计算整数X与Y的最小公倍数，首先要将计算式子“X×Y”的结果Z，然后再计算X与Y的乘积除以X与Y最大公约数的结果，此时得到的商A就是X与Y的最小公倍数[2]。

例二：求整数12345与765的最小公倍数。具体计算过程如下：首先计算“12345×765=9443925”，然后计算“9443925÷15=629595”，因此12345与765的最小公倍数为629595。计算机程序设计过程如图2所示。

其中A、B指代的是两个整数，先将整数12345输入到程序框内，替换掉A的位置，提行输出正如765，替换掉B的位置。按下运算键“1”之后，得到629595的运算结果，计算机显示为：？/12345/？/765/629595/-Disp-。

3 利用辗转相除法判断二元一次不定方程的整数解问题

二元一次不定方程整数解存在与否的判断过程，需要在最大公约数和最小公倍数的基础上进行。二元一次不定方程的表达式如下：aX+bY=c。其中a、b、c均为已知整数，要判断该方程式是否存在整数解，首先要利用辗转相除法求得a与b的最大公约数d，然后按照“c÷d”进行计算，判断c能否将a与b的最大公约数整除，如果计算“c÷d”得到的余数为0，则说明方程式“aX+bY=c”存在整数解，且整数解的数量为无数多个；如果计算“c÷d”得到的余数不为0，说明方程式“aX+bY=c”不存在整数解，即整数解的个数为0[3]。

例三：（a）判断方程式28X+12Y=200是否存在整数解。（b）判断方程式2X+4Y=1是否存在整数解。

具体计算过程如下：（a）首先利用辗转相除法计算28和12存在的最大公约数，28÷12=2……4，此时余数不为0，因此继续列式计算“12÷4=3”，此时余数为0，也就是说28与12存在的最大公约数为4。然后列式计算“200÷4=50”，余数为0证明方程式28X+12Y=200存在整数解，且整数解的数量为无数个。（b）同样先利用辗转相除法计算2和4的最大公约数，4÷2=2，余数为0，因此2与4的最大公约数为2。再通过式子1÷2的计算结果，判断出1不能够将2整除，因此方程式2X+4Y=1不存在整数解。利用N-S结构化流程图来描述其算法如图3所示。

4 结语

综上所述，通过论述求取整数最大公约数、最小公倍数以及判断二元一次方程式整数解问题等实例，分析了计算机程序设计中辗转相除法的实际应用情况，不仅明确了辗转相除法的基本原理和应用范围，同时了解了利用辗转相除法进行计算机程序设计，能够更加方便的解决大部分的数据计算问题，省去了在程序设计中的不少麻烦，提高了计算机编程人员的变成效率与质量。

参考文献

[1]王玉新.计算机程序设计上辗转相除法的实际应用研究[J].数字技术与应用，2016，（3）：116.

[2]王晓英.辗转相除法求解二元一次不定方程[J].赤峰学院学报：自然科学版，2014，（23）：6-7.

[3]陈占铁.辗转相除法反推计算的矩阵表达式[J].遼宁省交通高等专科学校学报，2015，（5）：32-33+39.

Abstract：This article from the common denominator， LCM and judge two indeterminate problem three integer solution of equation describes the application process of computer program design for the Euclidean algorithm. To clear division algorithm and use in computer program design value， through the application of Euclidean algorithm to calculate the problem more quickly and efficiently solve most of the data shows that the computer program is simple， fast and widely application prospect.

Key Words：computer programming； divide by phase； practical applicationendprint