高精度整数问题

, , , , , ,*,高精度整数问题,组合数和,Catalan,的精确计算,福州大学,04,计算机,(3),班,王建南,学号：,030402332,算法与数据结构第二次作业解题报告,问题描述,编一个大整数模板类，用来做高精度整数（也就是任意位数的整数）的四则运算，包括,加法（,addition,）,减法（,subtraction,）,乘法（,multiplication,）,除法（,division,）,利用上面设计的大整数模板类精确地计算组合数和,Catalan,数。,大整数的介绍,在某些情况下,(,如数据加密和科学计算等方面,),，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制,(,如,C+,中的,Double,类型有效位只有,15,位,),。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。,需要解决的问题,大整数的表示,在利于编程实现，同时便于提高运算效率的基础上选择数据结构。这个主要是考查数据结构。我们将会发现，在数据结构上的一个小改进对效率的提高有时会有很大帮助的。而数据结构在一定程度上是可以弥补算法的不足的。,大整数的运算,利用所选的数据结构，正确、高效地实现整数的四则运算。这主要考查算法。我们可以看到算法的选择对程序的效率是有绝对影响的。算法是决定程序效率的根本。,大整数的表示,由于大整数的位数太多，我们首先要做的是把它“拆”开来，放在若干个地方，然后建立不同存储地址之间的联系。很明显，线性数组,(,或者说是线性表,),是首选。下面的存储方式很直观也是最容易想到的。,对于大整数,1112223334445,我们可以用一维数组来表示：,数组下标：,存储数据：,0,1,2,3,4,5,6,7,8,9,10,11,12,1,1,1,2,2,2,3,3,3,4,4,4,5,进位没有存放的位置,大整数的表示,但我们可以发现这种表示方法的一个不足之处：,计算这个大整数加上,9000000000000,的结,果。如果用前面的方式存储，我们会发现进位没有,地方存放了。,数组下标：,大整数一：,大整数二：,结果：,1,为什么会出现这种情况？原因在于我们把大整数的,高位存放在数组的下标小的位置。而解决这个问题,的方法也很简单，就是把整数反过来存放。,0,1,2,3,4,5,6,7,8,9,10,11,12,1,1,1,2,2,2,3,3,3,4,4,4,5,9,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,这个进位可以通过扩大数组的方法来存放,大整数的表示,另一种表示方式,数组下标：,大整数一：,大整数二：,结果：,1,其实前一种表示方法还会有一个问题。就是高位的对,齐，这个我们可以通过减法观察到，这里就不说了。,基于以上原因，我们采用线性数组，同时把高位存放,在下标大的地方。虽然这样子存放我们看起来不那,么直观，但后面我们会看到这种存放方式的好处。,0,1,2,3,4,5,6,7,8,9,10,11,12,5,4,4,4,3,3,3,2,2,2,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,9,5,4,4,4,3,3,3,2,2,2,1,1,0,高精度加法运算,在确立了使用线性数组表示的大前提后，我们可以很容易地解决高精度加法。,(,这里为了简便，我就不用类实现了，同时假设那两个大整数都为正数。,),1.,初始化数组，数组全部元素置为,0,2.,用字符串读入大整数，同时以反向存储的方式,存放在数组中,3.,进位标志,flag,置为,0,。从数组低位开始进行加,法运算。这里只要注意,flag,的更新就行了。,4.,反向输出结果,高精度加法运算,高精度加法举例,这里我们假设我们已读入两个大整数，并且也已经被分别反向存放在数组,a,和数组,b,中了。,加数,a 8 7 4 2 5 9 7 8,0,0,加数,b 4 8 3 1 4 8 5 1 9,0,结果,c 2 6 8 3 9 7 3 00 1,进位,e 1 1 0 0 0 1 1 1 1 0,上面的过程表示为,87952478+915841384=1003793862,减法亦可用相同的方法实现，只是现在标志换成借,位标记而已。,前面补,0,的原因是为了对齐,高精度加、减法小结及其改进,我们首先要明确的一点是，选择线性数组及反向存,储的方式并不是偶然的。我们可以列一个竖式，用,手工模拟,854+87,的加法就会理解为什么要这样子,处理了。,而我们同时会发现，一个数组元素只存储一个位的,方式有点浪费，虽然这很合乎我们的习惯。但可不,可以通过增加存储位数的方法来提高效率呢？毕竟,我们需要的这个一个位计算机只要,4,个二进制位就可,以表示了，而,VC,给我们分配的一个,int,却有,32,位。,大整数的运算之加、减法的改进,我们来分析只存储一个位的大整数加法是怎样进行,的。,加数,a 8 7 4 2 5 9 7 8,0,0,加数,b 4 8 3 1 4 8 5 1 9,0,结果,c 2 6 8 3 9 7 3 00 1,进位,e 1 1 0 0 0 1 1 1 1 0,设,i,表示数组第,i,位数，则,ci, = (,ai, +,bi, + e) % 10;,e = (,ai, +,bi, + e) / 10;,大整数的运算之加、减法的改进,所以我们如果要进行多位存储的话，我们只要把上,面的计算式子改成,ci, = (,ai, +,bi, + e) % M;,e = (,ai, +,bi, + e) / M;,其中,M,为,10,的,n,次方，,n,为规定的位数。如，每个,数组元素都存储,4,个位，则,M=10000,。,这个改进并没有引起程序上大的变动，但它的对运,算次数的减少是很有用的。做每个元素存储,n,位的,加法，其加法的次数为只存储一位的,1/n,。这是因,为它,增大了存储密度，所以运算速度也随之提升,了。,高精度加法程序,flag = 0;,n =,min(a,的位数，,b,的位数,);,M= 10000;,For (i=0; in | flag; i+),ci, = (,ai, +,bi, + flag) % M;,flag = (,ai, +,bi, + flag) / M;,习题,四川大学,Online Judge 1001,和,1002, 4 0 1 5 2 4 1 4 7 8 5,乘数：,56,进位：,39 26 2 5 28 14 23 7 23 41 48 32 3 0,结果：,2 3 6 8 5 0 8 9 1 5 9 8 2 3,所以乘法的最后结果就是,32895198058632,这里的关键就是进位不一定是一位的。其原理和加法多,位存储的运算是一样的。,高精度乘法,现在我们来看看大整数乘以大整数是怎样进行的。,还是先做手工模拟一下,516541*4845412,是怎么算,的。我们发现它的原型就是先进行小整数乘以大整,数，再把它们的和加起来的过程。其根本思想就,是：,设两个大整数分别为,a,，,b(,都已反向存储了,),。,将,b,按,10,进制展开，,b=b0+10*b1+100*b2,+,bn,*10n,。其中,bi,为小于,10,的非负整,数。,则,a*b=a*b0+a*b1*10+a*b2*100+a*,bn,*10n,。,而,a*,bi,就是小整数乘以大整数。,(,后面乘,10k,，,只要进行移位就可以实现了,),高精度乘法,高精度乘法算法流程如下：,读入被乘数,s1,，乘数,s2,把,s1,、,s2,分成,n,位一段，转成数值反向存在数组,a,b,中；记下,b,的长度,m,i=0;,从,b,中取出第,i,位与,a,相乘，累加到另一数组,c,中；（注意：累加时错开的位数应是多少位）,i+,；检测,i,值：大于,m,则转,否则转,打印结果,为什么结果存放在这一位？,高精度乘法程序,M = 10000;,p =,大整数,a,的“位数”,;/,这里的位数是指多位存储时的位数,q =,大整数,b,的“位数”,;,for (i=0; ip; i+) ,flag = 0;,for (j=0; j=0),?,在,R,后面加上,bj,，转,4,：,转,7,；,输出商数,Q,及余数,R,。,高精度除法,这里就不给出除法的程序了。,但在实现时需要注意,1.,除法可以反向除也可以正向存储，只要做相应调整就可以,2.,实现时需要定义一个函数来比较两个大整数的大小，同时要用到大整数减法,3.,多位存储还是可以运用的。但细节上要小心,习题,四川大学,Online Judge 1003,、,1004,北京大学,Online Judge 1001, For Attention,