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

李彬

在计算机运算和编程的过程中，最终运算结果为正负数的现象是非常普遍存在的，而这些最终数据的正负数会直接影响到程序员设计计算机程序的效率问题，如果在计算机编程的过程中使用辗转相除法则可以避免这些问题的出现。在计算机的计算程序中，辗转相除法是代数计算的重要理论，辗转相除法的运算特点和计算机的运行程序有着很大的共通性，在具体的运算过程中可以使用辗转相除法来求得最大公约数，那么就避免了最终输出结果存在正负整数的问题，程序员就可以在自然数的范围之内进行，这样的计算流程可以大大节省计算时间，同时也提高了计算结果的准确性，有着非常良好的应用前景。

一、辗转相除法概念分析

辗转相除法，又名euclidean algorithm，是一种求最大公约数的一种方法。它的具体流程为：用数列中较大的数来除以最小的数，然后用这两个数相除得出的余数再去除以除数，接着再用这两个数的余数来除以前面的第一个余数，按照这样的流程反复相除，直至除到最后余数为零为止。那么最后一次的这个除数就是开始计算时两个数的最大公约数。

二、辗转相除法、更相减损法、穷举法对比分析

通过上述的概念分析，我们可以知道辗转相除法有着较大的优点，它的连续相除能够使得整个计算流程以一种比较系统的方法来求出两个数的最大公约数，而不需要我们再对两个数进行因式分解。因为在具体的计算和操作过程中，因数分解是一个比较困难的过程，尤其是数量比较大的时候，因数分解对于程序员来说更是不小的挑战，即便是现代最先进的计算机加入，也是对此非常难以处理的。当然，辗转相除法也有着自身的缺点，从上文的论述中我们可以清晰地看出，辗转相除法的运算是非常繁琐和复杂的，长时间的运算很容易出现差错，而且从算法的实现角度来看，这种方法对于运行设备的存储空间要求是比较大的，其运算时间也是非常长的，其运算速度也不太快。而穷举法的主要计算思想就是根据数量的主要特征来确定出大致的范围，然后对数值进行一个一个的验证，如果某一个情况是符合题目的条件的，那么就是该题目的唯一解，如果不符合条件，则无解。其主要的优点就在于计算简单，但是其主要缺点是运行所需要花费的时间比较长，在利用穷举法的时候，我们通常采用的是三种列举方法，第一是顺序列举，该方法是指在答案的范围内的各种情况是很容易和自然数进行一一对应的，或者说本身就是自然数，那么具有这样的特征的时候，我们就可以使用顺序列举;第二是排列列举，该种方法主要指的是数据的形式是一组数的排列方式，我们可以列举出所有答案所在范围内的排列，这就是所谓的排列列举;第三是组合列举，组合列举是无序排列的，也是说当答案额度数据形式为一些元素的组合的时候，我们通常是要采用组合列举的。

更相减损法是出自于我们前人的《九章算术》中的一种算法，是一种求最大公约数的算法，它本来是为数据的约分而设计的，应用是比较广泛的，随着计算机的兴起，更相减损术作为一种算法也是广泛应用在数学和计算机工程中的。和辗转相除法相比，这两种方法都是求最大公因数的方法，在主要的计算方法上，辗转相除法主要是以除法为主要算法，而更相减损术主要则是以减法为算法，但是在计算的次数对比上来看，辗转相除法的计算次数是相对较少的，但是如果两个数字之间的大小差别很大的时候，两者的计算次数是比较明显的。从最终的结果体现形式来看，辗转相除法最终的结果是相除的余数为0得到的，而更相减损术主要是和减数的差而得到的。更相减损法在两个数量之间的差距比较大的时候可以将时间复杂度退化成0（N），而辗转相除法则可以稳定在0（logN）。所以，在目前的应用中，辗转相除法和计算机算法的结合较为紧密。

三、辗转相除法计算最大公约数原理分析

辗转相除法有着较大的优点，它的连续相除能够使得整个计算流程以一种比较系统的方法来求出两个数的最大公约数，而不需要我们再对两个数进行因式分解。这样可以避免因式分解中的盲目性，提供了运算的效率。根据数学上最大公约数的定义，在使用辗转相除法来求取数字的最大公约数的时候，我们主要是通过数字之间的反复计算、反复相除来求出最大公约数。具体的计算过程可以通过文字描述如下：对于题目中已知的两个数量A、B，我们采用A÷B的算法，进而求出A÷B的值，在大多数情况下，A÷B的值都不是一个整数，还会有余数现象的产生，我们将它们相除的余数用C来表示，一般而言，最终的计算结果可以分为两种，第一，C=0，那么我们就将此时的B的值称之为A、B的最大公约数，第二，C≠0，那么我们就接着用B÷C，这时同样有两种情况，当结果不等于零的时候我们就接着按照上述的过程进行计算，直至最终的结果为零为止，最终得到的结果就是A、B两数的最大公约数。举个具体的例子来说，求整数31875和6375的最大公约数，按照上述的方法，我们首先拿31875÷6375，得到了结果为5，说明此时的余数为0，那么31875和6375的最大公约数就为6375，而12345和765的最大公约数计算就和上述计算略有不同，首先我们先计算12345÷765最终的结果为16余105，這时候我们发现余数不等于0，那么就需要我们接着进行下去，就拿765÷105，最终的结果为7余30，这时候的余数不为0，所以我们接着进行上述的计算，用105÷30得到3余15，其余数依然不为零，那么我们就接着用30÷15得到了整数为2，这时候我们就可以认为12345和765的最大公约数为15.这种循环往复的计算非常适合计算机的程序设计特点，所以我们在计算机的编程中输入图1所示的语句，在该式子中，M、N代表两个整数，其中R作为余数，我们可以将上述的两个例子带入试算。

首先将整数31875输入到程序框内，然后在接着的程序框中输入整数6375，按下运算键1之后，我们可以得到的结果显示为：？/31875/？/6375/6375-Disp-。在第二个例子的试算中，我们将整数12345输入到程序框中，在接着的程序框中输入765，同样按下运算键1，最终得到的结果显示为：？/12345/？/765/15/-Disp-。

四、辗转相除法计算最小公倍数原理分析

利用计算机的程序计算两个数的最小公倍数其原理是和求最大公倍数有着相似的特点的，是在求最大公约数的基础上进行的，在求A、B两数的最小公倍数时，首先要计算出A×B的值，然后再计算出A×B的值除以A与B的最大公约数的值，然后得到的商C就是A、B的最小公倍数。

举个例子来说，求12345和765的最小公倍数，那么按照上述的计算流程就是先用12345×765，计算出的结果为9443925，然后根据上文的计算结果，我们知道12345和765的最大公约数为15，那么我们就拿9443925÷15得到结果629595，那么12345和765的最小公倍数就是629595，具体的计算机系统编程语言见图2所示。在下图中，A、B是代表两个整数，我们将12345输入到对话框中，接着输入765，按下运算键1，得到了最终的结果为629595，计算机的编程显示为：？/12345/？/765/629595/-Disp-。

五、二元一次不定方程整数解的求解过程分析

从二元一次不定方程整数解的求解原理来看，其主要的核心是判断二元一次不定方程的整数解是否存在的问题，也是说通过判定两个系数的最大公约数和最小公倍数的基础上综合进行的。例如，我们假设二元一次方程为ax+by=C，其中abc均为整数，那么在计算的过程中就是寻找该方程是否具有整数解的过程。在求解的过程中，我们首先要计算出a和b的最大公约数，该过程可以利用辗转相除法进行求解，求出的最大公约数我们将其命名为d，然后使用c÷d，如果c÷d的余数为0，那么就说明二元一次不定方程ax+by=C是存在着整数解的，而且整数解的数量是无穷个，如果c÷d的值不为零，那么就说明ax+by=C二元一次不定方程不存在整数解，也就是说该等式的整数解为零。举个具体的例子来说，我们来判断一下28x+12y=200是否存在着整数解。我们可以参照上述的方法来进行运算。首先利用我们所述的辗转相除法来计算出28和12的最大公约数，也就是用28除以12，得到结果为2余4，此时的结果不为零，那么我们就接着用12除以4等于3，此时得到了整除，那么我们可以认为4为28和12的最大公约数，然后计算出200÷4=50，也就是说此时的余数为0，也就是说该等式28x+12y=200是存在着整数解的，而且整数解有无数个。再举个例子来说，我们要求2x+4y=1是否具有整数解。首先，我们采用辗转相除法来计算出2和4的最大公约数，通過计算4÷2我们知道其结果为2，是整除的，那么就说明，4和2的最大公约数为2，然后再计算1÷2的值，我们发现并不能整除，那么就说明该等式2x+4y=1是不存在整数解的，在具体的应用中我们主要是利用N-S的结构化流程图来描述其算法，详细见图3所示。

六、结语

计算机的发明和使用为人们的计算提供了更多的便利，在计算机的计算程序中，辗转相除法是代数计算的重要理论，将其编制在计算机程序中能够对算法进行较大程度的改良，换句话说，辗转相除法的运算特点和计算机的运行程序有着很大的共通性，因此，辗转相除法应用到计算机程序之中能够更好地与计算机的性能结合，能够更加快速和便捷地求出一些较为复杂算式中的最大公约数和最小公倍数，同时还能够解决计算机算法中的一些疑难问题，有着非常好的应用效果。通过上述的论述和研究，我们也可以清晰地看出辗转相除法在解决一些计算机中的复杂问题具有比较强的优势，尤其是在处理和解决整数之间求取最大公约数、最小公倍数以及二元一次方程的整数解等方面的问题有着较好的准确性。本文的研究也是立足于理论，比较和分析了辗转相除法的优势与特点，从当前的实际应用情况出发，对于程序设计中的辗转相除法的相关适用情况和算法语句进行了深入分析，明确了辗转相除法的基本原理以及使用范围，对于辗转相除法中的程序设计问题也进行了探讨，并且从程序运行的角度来解决数据计算的问题，这样可以解决实际操作过程中的一些问题，大大的提高的运算的效率和质量，提高运算的精度，为计算机的运算提供了新的思路。

参考文献：

[1]杨妮，魏春强. 辗转相除法的统一公式及其应用[J]. 安康学院学报，2018，30（01）：107-109.

[2]汪仲文，官春梅，王和香，邹庭荣. 多项式最大公因式的启发式教学实践[J]. 大学数学，2017，33（01）：103-108.

[3]王鹏. 计算机程序设计上辗转相除法的实际应用研究[J]. 数字技术与应用，2017（06）：78-79.

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

[5]何躍. 基于Small Basic的最大公约数算法的实现及其效率验证[J]. 科技展望，2016，26（30）：198-199.

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

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

责任编辑 魏家坚