关于两数的最大公约数gcd
2024-10-18 21:23:36
深根半夜里研究C++的语法,在弄到关于函数的定义 这一部分时突然想写个试试,就拿比较熟悉的gcd来好了。
活这么久gcd一直是用辗转相除法(或者说欧几里得算法)得出的,根据《算法导论》第三版的中文页码P547给出的伪代码,很容易就得出C++的写法。
int gcd(int a,int b){ if(b==0) return a; else return gcd(b,a % B); }
However----
当a,b比较大的时候显得特别慢,所以出现了来自《九章算术》中的更相减损术来求gcd。(怕是活久见的实例。。。)
更相减损术的代码如下:
int gcd(int a,int b){ if(a==b) return a; else if(a<b) return gcd(b-a,a); else return gcd(a-b,b); }
换句话说,其原理可以被称为“辗转相减法”【笑】。根据gcd(a,b)=gcd(|a-b|,min(a,b)),然后设定一下边界(即两个相等的数,其gcd值为本身),就有了。具体证明不知道【喂太草率了吧!!】,反正没问题可以用就是了。
But----
当|a-b|比较大的时候,很明显递归次数比较多,这不是想要的结果。再看一遍原文:
可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。
好了,【作为一名文科生恬不知耻地笑了】其实原文的目的是为了约分,“可半者半之”就是说能约2就约2,然后不能约2了再找gcd约分。
所以分类讨论一下:
- 两数皆偶:美滋滋,易有gcd(a,b)=2×gcd(a÷2,b÷2)
- 一奇一偶:只要想象一下类似约分一个分数like 9÷30,很显然有gcd(a,b)=gcd(a,b÷2),因为偶数除以2只是排除掉了一个因子2,而2又不可能是奇数的因子,所以可以得到这个等式成立
- 两数皆奇:那怎么办呐?【笑】有小学奥数可知在整数范围内,奇数-奇数=偶数。所以跑一次“辗转相减法”以后,问题就转化为了上一种情况
所以ok,final版本的gcd就出来了,大半夜的写错了别打我啊。。。
int gcd(int a,int b){ if(a==b) return a; else switch (check(a,b)){ case 0:return 2*gcd(a/2,b/2);break; case 1:return gcd(a,b/2);break; case 2:return gcd(a/2,b);break; case 3:return gcd(abs(a-b),min(a,b));break; } }
有必要说明一下的是check函数检验的是将要参与gcd运算的两数的奇偶性,0就是同偶,1和2都是一奇一偶只不过位置有区别,3就是同奇的情况;abs是绝对值函数,min则返回两数间较小的一个。
最新文章
- 全局唯一ID设计
- 关于JS的编码转换问题
- 重启Ubuntu后Hadoop的namenode起不来的解决办法
- atitit.mp4&#160;视频文件多媒体格式结构详解
- Java基础の乱弹琴二:break关键字
- Libfilth(一个滤波器C库)使用
- Nginx服务器架构简析
- 多设备官方教程(6)控制多版本API
- DM8168 坎坷硬件之路(DDR3)
- 在confluence中出现Handshake failed due to invalid Upgrade header: null
- Javascript 中的map/reduce
- 目录导航「深入浅出ASP.NET Core系列」
- MySQL小计
- Table &#39;performance_schema.session_variables&#39; doesn&#39;t exist错误的一
- 事件监听addEventListener----attachEvent
- Django模板语言相关内容 Djan
- python卸载或者安装时提示There is a problem with this Windows Installer package.A program required for this install to complete could not be run. Contact your support personnel or package vendor
- codevs 1001 舒适的线路 kruskal/gcd
- 线程的同步之Synchronized在单例模式中的应用
- Android性能测试工具:Emmagee介绍
热门文章
- BZOJ3456 城市规划 【多项式求逆】
- BZOJ1293 [SCOI2009]生日礼物 【队列】
- POJ1456:Supermarket(并查集+贪心)
- Java Web转发和重定向问题
- javascript中Date使用总结(转)
- React 获取 url 参数 —— this.props.match
- IDEA的常用快捷键
- Idea工具点滴积累
- [object-c 2.0 程序设计]object-c file handle (二)
- 类的 propert,classmethod,ataticmethod 方法 与 多态