服务器证书与网站不符,ai写作网站,做网站的公司叫什么名字好,分类信息网站的建设维护本文是参考新浪博客而写。 欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式 gcd(a, b) gcd(b, a mod b) 其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 代码如下: #include iostream
#i… 本文是参考新浪博客而写。 欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式 gcd(a, b) gcd(b, a mod b) 其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 代码如下: #include iostream
#include math.h
using namespace std;int gcd1(int a,int b)//递归版本
{if (ab){int tempa;ab;btemp;}if (b0){return a;}else{return gcd1(b,a%b);}
}
int gcd2(int a,int b)//循环版本
{if (ab){int tempa;ab;btemp;}while ( b!0){int ca%b;ab;bc;}return a;
}
int main()
{int a,b;cout请输入两个正数endl;cinab;couta与b的最大公约数是:gcd2(a,b)endl;//couta与b的最大公约数是:gcd1(a,b)endl;}
欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a和b的大小有怎样的关系? 我们不妨设ab≥1a>b\ge1, 构造数列{un}:\{u_n\}:
u0a,u1b,...,ukuk−2moduk−1(k≥2),
u_0=a, u_1=b, ...,u_k=u_{k-2}mod u_{k-1}(k\ge2), 显然, 若算法需要n次模运算, 则有ungcd(a,b),un10u_n=gcd(a, b), u_{n+1}=0. 我们比较数列{un}\{u_n\}和菲波那契数列{Fn},\{Fn\}, un≥1F0un−1≥1F1
u_n\ge 1=F_0\\ u_{n-1}\ge 1=F_1\\ 又因为由ukmoduk1uk2,u_k mod u_{k+1}=u_{k+2}, 可得ukuk1×βuk2≥uk1uk2u_k=u_{k+1}\times \beta+u_{k+2}
\ge u_{k+1}+u_{k+2},故可得un−2≥un−1un≥F0F1F2
u_{n-2}\ge u_{n-1}+u_{n}\ge F_0+F_1=F_2 ,以此类推由数学归纳法容易得到un−k≥Fk,
u_{n-k}\ge F_k, 也就是uk≥Fn−k
u_k\ge F_{n-k}于是得到au0≥Fn,bu1≥Fn−1a=u_0\ge F_n, b=u_1\ge F_{n-1}. 也就是说如果欧几里得算法需要做n次模运算, 则b必定不小于Fn−1F_{n-1}. 根据斐波那契数列的性质, 有Fn−1(1.618)n5√
F_{n-1}\gt {(1.618)^n\over \sqrt{5}}, 即b(1.618)n5√b\gt {(1.618)^n\over \sqrt{5}}, 所以模运算的次数为O(lgb)O(lgb).
