高精度整数运算(6)除法

除法是我们实现高精度整数运算中的最后一个四则运算,之所以会放到如此靠后的位置,那是因为在我看来,除法是这四个运算里最难实现的。实际上,在实现除法的运算中,我们用到了几乎之前所有的内容,包含“比较”、“乘法”、“减法”。所以在有了前面的铺垫后,我们实现高精度整数的除法运算就轻而易举了。 依照惯常思路,我们利用我们手算除法的方式来实现高精度除法运算,如图1所示。 我们从左侧逐位获取被除数的一位,然后进行试除,并记录商,反复操作后就能得到高精度商,这个商是向下取整的(没有浮点位),在除法运算的试除的过程中,我们把除数从9开始作为商进行试除,试除的商递减,第一个使得被除数相同位数字减去试除商乘以除数的结果大于零的试除商,即为实际此位上的商。 最后只需要把前导零去除,并按照乘法处理数字符号的方法给结果填上正负标记即可(除法和乘法可以相互转化,但是在运算中我们没有这么做的原因是,除数求倒的过程需要高精度的浮点数,而且该浮点数很可能是无限循环的,这会导致我们的结果最后并不准确)。 下面就是除法的具体实...

高精度整数运算(5)负数与减法

鉴于从本篇文章开始后的高精度运算类加入了“负数”概念,在实现高精度整数运算的时候如果要求能计算负数,那就需要在每次运算的时候加入很多判断,这在解题过程中会使效率降低很多,所以我将本篇文章及之后相关的文章都归类到“开发探索”当中。实际上,在比赛中如果需要用到负数,只要知道负数的下界,我们就可以用正整数来表示负数,方法为: 运算中处理的数字 = 实际数字 + 负数下界的绝对值 通过这样的方法我们可以规避对于负数运算的额外判断,而且可以确保在运算过程中只会涉及到正整数间的运算,而绝不会出现负数。 但是对于一个真正的高精度运算而言,存在下界是不允许的,所以在这里,我们就来探讨整个整数域上的高精度运算。 在高精度整数类中,我们增加一个成员symbol来表示当前数字的符号是正或是负。这样我们在运算的时候就可以针对数字的符号来选择进行何种方式的运算。需要关注的是,我们要处理的是正整数,数字的符号是作为一种标记来存在的,所以现在我先将正负数字之间存在的各种运算关系整理如下,使我们在运算过程中只考虑正数与正数的运算:

高精度运算(4)比较

比较运算用于比较两个高精度整数的大小,算法十分简单,只需要按照两个规则,就可以得到两个数字谁大谁小: (1)如果一个数字比另一个数字位数少,则这个数字必比另一个数字小。 这就要求我们存储的数字不能有前导零。 (2)从末位开始向个位逐个比较,位上的数字大的,则这个数字也大。 通过这样的比较法则,我们就可以实现比较运算小于号“<”: [crayon-5bc79c2169474774766015/] 神奇的是,我们只需要一个小于的比较运算符,就可以实现其它所有的比较运算符,请看下面的代码: [crayon-5bc79c216947c107071461/] 下面给出完整的高精度运算类的代码: [crayon-5bc79c2169480762740059/]

高精度运算(3)乘法

在本篇文章中我们将实现高精度乘法运算。 乘法和加法比起来就复杂很多了,我们知道乘法可以由加法直接实现(连续加因数2次因数1),在有我们之前的加法运算的基础的情况下,这种乘法运算极其简单便能实现(但是需要先做出高精度数比较运算,这是下节的内容了,不过这种方法并不明智,对于一个N位数乘以N位数的运算,其时间复杂度为O(10^N),这个增长速度实在是太大了。 那么我们继续按照上次的思路,回到我们算乘法的竖式,看图1: 对于我们的乘法运算,按照计算机的运算思路,就是两个大循环,逐位相乘,最后再相加,然后转换为十进制数字,也就是进位,就能得到我们的结果了。 下面是乘法的实现方法: [crayon-5bc79c216966d648012327/] 依照惯例,给出完整的高精度整数类的代码,除了增加了乘法及乘法相关的运算符的重载外,为了防止乘法运算中相加过程中出现数值溢出,原先的short类型的容器修改为了int,这样可以确保不会出现乘法运算溢出的现象,同时在每次赋值和输入的最后,会自动去掉数字的前...

高精度运算(2)加法

在解决了高精度整数的输入、存储以及输出的问题后,我们终于开始正式思考“运算”部分的实现。 加法是最简单的一种四则运算,也是我们小学时数学最先就学到的运算规则,对于内置的整数类型而言,计算机通过二进制的电位运算可以快速的得到结果,而对于我们按位存入的高精度整数而言,要想对其进行加法运算,我们就需要返璞归真,首先,我们来回忆下小学时的加法,看图1: 从个位开始相加,结果放在横线下,如果相加的结果超过10,则进1到下一位。 没错,我们就是要所要依靠的就是这样一个简单的规则! 首先考虑到我们存储数字的方式:如果两个数字位数不同,则会出现超过数位的数字再相加时vector out of range的情况,所以我们要把两个数字一个一个加到结果的位置上(比如图1的个位,结果位原先是0,先把4加到结果位,结果位变为4,然后再把2加到结果为,变为6),这样可以方便我们对两个加数的各个位的情况进行把握。 下面就是加法运算的具体实现方法: [crayon-5bc79c2169aaf186524174/...

高精度运算(1)结构

在解题过程中,经常会出现需要运算的数据超过系统内置的整型范围的情况,在这种时候我们就需要用到高精度运算算法,我将分几篇文章来解释,如何实现高精度运算,并且我将会将高精度运算封装为一个命名为BigInt的高精度整数类,方便未来的使用。 在本篇中,主要实现的是高精度整数的存储、输入与输出。 在给出具体的实现之前,我先介绍一点预备知识,关于C++标准库vector。 vector这个词在上一篇文章中提及过,vector是C++提供的一种顺序容器,而对于vector这种容器来说,其特点就是支持快速的随机访问(想一想数组通过下标值访问的方式),作为一种可变长的容器,我们可以把它当作一种“高端的数组”,用vector来存储高精度整数的好处在于可以解决由大整型数组来存数高精度整数时所造成的空间浪费问题。 我们对于高精度整数的存储方式是按位存储,为了避免运算的时候对齐各个位时产生麻烦,所以我们从个位开始存储,也就是说,在vector容器中存储的数字顺序,与你实际看到的数字顺序是正好相反的。 下面就给出具体

栈(stack)是一种数据结构,它遵循一个简单的规则,即后进先出(Last in First out, LIFO)。 栈的工作方式很容易理解,用一个图表形象的表示就是这样,见图1: 这个只有上端开口的容器,就是用来存放数据的栈,我们要取容器中的东西,必须从最顶端开始,一个一个拿掉,才能取到我们想要的,而如果要放一个元素呢,也只能放在最顶端,这也就是栈的后进先出原则。 这样的数据结构可以使用C++标准库来实现,非常简单,下面就对C++标准库中的栈做一点简介: C++提供了三种顺序容器(sequential container)vector(支持快速随机访问)、list(支持快速插入删除)、deque(双端队列),vector比较类似与数组,而list则更加像链表结构。C++标准库为顺序容器提供了三种容器适配器(adaptor), 不要被名字吓到,所谓适配器,就像你的电脑电源适配器一样,将交流电(这里是顺序容器)做出一定的调整,来适合电脑工作,也就是说,容器适配器,是利用容器来...

DP记忆化搜索

动态规划(dynamic programming)这个名词曾不止一次吓到我,而事实上,动态规划作为一种思想而非算法,其最大的作用是优化。这次笔记中,我就对最为经典的The Triangle[1]问题来对DP的记忆化搜索进行解释。 如图1,从三角形的最上面的顶点往下层走(每次只能向左或向右一个),那么如何走,才能途径的所有位置的点数之和最大呢? 第一种自然而然的思路就是把所有可能的路径都找到,并找到其中点数和最大的一条路径作为答案,然而这样的思路却存在着很大的效率问题,从第一个顶点开始往下走,每走一步都有2种选择,那么走到第N层的时候,路径数目就多达2^N条,枚举如此巨大数目的路径,必然会使程序在测试的过程中出现超时(TLE),所以这样的方法并不可取。 至此,我们可以隆重推出动态规划的思想了,我们从结果来看,答案的路径是确认的,那么第一步只有向左或向右才可能到达最终答案的地点,第二步也是,第三步也是……在这个过程中,我们往下走,只选择“能到达最优解”的路径走,这样就可以帮助我们减少大量的搜索