C++求最大公因数(gcd)的六重境界 |
您所在的位置:网站首页 › 循环变量i › C++求最大公因数(gcd)的六重境界 |
前言
众所周知,最大公因数(gcd)是C++程序中第二常见的函数(仅次于判素数)。正因此,一个简单的gcd也能被不同的OIER写出不同的“境界”。 话不多说,直接开始! 第一境界:暴力枚举!如果你是一个连while循环都没写过的超级蒟蒻(天南星科植物魔芋属植物),那么你该怎么写判最大公因数程序? 答案很简单:暴力枚举! 我们可以用循环变量i直接从A,B中的小值直接反向枚举到1,如果能同时被A,B整除,直接输出i就行了。 这样写虽然长(其实也不是很长),但也是最直白的思路了: int gcd(int a,int b) { for(int i=min(a,b);i>=1;i--) if(a%i==0&&b%i==0) return i; }但这样写的时间复杂度是O(min(a,b)),因此一旦A,B都特别大的时候(比如说都是2的31次方),这种方法的运行速度将会比乌龟还慢,自然会时间超限(TLE)。 第二境界:辗转相除法很快,你就学会了while循环,同时也去百度上搜索了辗转相除法。 辗转相除法就是定义一个变量R来储存A模B的值,再将A的值设为B,B的值设为R。以此类推,直到B=0为止。然后直接输出A就行了。 这样写虽然长了一点,但是时间复杂度获得了飞跃性的提升: int gcd(int a,int b) { while(b>0) { int r=a%b; a=b;b=r; } return a; }作为一名初学者,会这段程序就够了(bushi)。 第三境界:递归一个寒假过去了,曾经的那名蒟蒻终于学会了递归。 你发现,用递归写最大公因数又快了很多。 用递归写最大公因数,还是基于辗转相除法。这样写,当A模B等于0时,返回B;否则返回递归求解B和A模B的最大公因数的值。 于是,你写出了一段递归求解的程序: int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); }可这样写在OJ上没有通过。奇怪,百度上不是那么写的吗? 事实上,根据辗转相除法的性质,应该是在B等于0是返回此时A的值,而不是在当A模B等于0时返回B的值。 你把程序改了一下,果然通过(AC)了这道题目: int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } 第四境界:三元组你在《信息学奥赛一本通》中学到了有关三元组的知识。 "啊?三元组?这似乎能运用到gcd上啊。" 事实上,三元组在时间复杂度上与递归相比并没有变快。但是,使用三元组,原本两行的代码变成了一行。 于是,求最大公因数的算法由两行变成了一行: int gcd(int a,int b) {return (b==0?a:gcd(b,a%b);} 第五境界:编译器自带函数!前段时间,你在一篇题解上发现了__gcd这个编译器自带函数。 于是你一口气写出了判最大公因数的整个程序(真的只用了一口气的时间): #include using namespace std; int main() { int a,b; cin>>a>>b; couta>>b; cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |