辗转相除法,求最大公因子

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

文章简介:

1. C++递归版本的算法

2. 算法正确性证明

3. C++非递归版本的算法

一、递归版本算法

/*  * Copyright (c) 2014, 烟台大学计算机与控制工程学院 * All rights reserved. * 作    者:何小乐 * 完成日期:2014/10/29 * 修改日期:2018/10/3 * 版 本 号:v1.1 * * 名字:gcd_recursive * 描述:使用递归的方法得到两个整型数的“最大公因子” * 参数约定: a != 0             b == 0时表示此时a为两个数的最大公因子 * 返回值意义:0表示参数异常 */int gcd_recursive(int a, int b){    if(a == 0)        return 0;    if(b == 0)        return a;     return gcd_recursive(b, a%b);}

二、算法正确性证明

算法通俗来说:

要求(a,b)的最大公因子,假设a>=b,r表示a%b,易知r<b,并且由于a、b、r具有相同的最大公因子(下面会证明这个关键点),所以对(a,b)的求解问题可以转化为小规模的(b、r)问题(b<a,r<b);

a<b时,(a,b)=(b,a%b)=(b,a),与上同理。

现用较严谨的方法证明以上描述:

设g为(a,b)的最大公因子,| a | > | b |,即a = m x g,b = n x g

设a%b的商为c,余数为r,即a = b x c + r

由a = b x c + r,得r = a – b x c

由a = m x g,b = n x g,r = a – b x c得r = (m – n x c) x g

即g也是a、b、r的最大公因子

因为| a | > | b | > | r |,考虑到a、b有可能是负数

所以对(a、b)的求解可以转化为对(b、r)的求解

证毕

三、非递归版本

递归版本随着递归深度的增加而用于存储函数的信息的开销变大,以下是上述算法的非递归版本

/* * 名字:gcd * 描述:gcd_recursive的非递归版本 * 参数约定:同gcd_recursive * 返回值意义:同gcd_recursive */int gcd(int a, int b){    if(a == 0)        return 0;     int tmp;     while(b != 0){        tmp = a;        a = b;        b = tmp%b;    }    return a;}

点这里可以跳转到人工智能网站