整数总结算法 第1篇

首先我问一个问题，十六进制和二进制的转化是怎么样的？

没错，四位二进制表示一位十六进制，于是计算机中的表示总是A9FD CFFF这种形式，那对于一个很大的整数，我们是不是也可以思考这种方法呢？

从而我们很自然地得出：用int类型的数组，每个元素内存放四位数字。

顺序：内部都是正序，但是总体是逆序的

比如12345786328

所以先处理读入：

//PS：这个我写的代码已经找不到，出于省时，我这里复制了高精度4位压缩法原理xxx实现_挽颜__-CSDN博客他的代码。

int StrToNum(const char str[], int num[])//从字符串的最后一位xxx序向，int数组正序方向赋值（int数组是xxx序的大数） {     int len=strlen(str),i,j=0;     for(i=len-1;i>2;i-=4)//xxx序每4个数字存放一个单位内     {         if(i-3>=0)             num[j++]=(str[i-3]-'0')*1000+(str[i-2]-'0')*100+(str[i-1]-'0')*10+(str[i]-'0');     }     if(i==0)//如果xxx1个数字         num[j++]=str[0]-'0';     else if(i==1)//xxx2个数字         num[j++]=(str[0]-'0')*10+(str[1]-'0');     else if(i==2)//xxx3个数字         num[j++]=(str[0]-'0')*100+(str[1]-'0')*10+(str[2]-'0');         while(j>0&&num[j-1]==0)    //j返回num的长度             j--;     return j; }

int Add(int num1[],int num2[],int num3[],int len1,int len2,int& num3_begin)//加法  num1，num2是原始数据的数组，num3用来存放结果 {     int i=0,j=len1>len2?len1:len2;     

  //len1，len2分别代表数组num1，num2的长度，num3_beginxxx果中数值开始的下标。     if(len1==0&&len2==0)     

//原始数据是0的情况讨论。  0：num1、num2都是0；   1：num1是0    2：num2是0         return 0;     else if(len1==0)         return 1;     else if(len2==0)         return 2;     else     {         while(i=10000)        //xxx数值大于进制进行进位操作                 num3[i+1]+=num3[i]/10000,num3[i]%=10000;             i++;         }         if(num3[i]==0)//xxx果中数值开始的下标             num3_begin=i-1;         else             num3_begin=i;     }     return -1; } 

这里给大家讲解一下，核心的思路同第一部分的传统法，便是分位然后分别进行计算，同时处理好借位和进位的问题，无非一个只分了高低位，而这里是分了许多位，每一位存了四个数字，同时需要关注最后可能存的不是四位数。

乘法：

和传统法一样，不过我个人认为他的代码里面，对于四位数的乘法可以多用一个模来处理可能会更好。

整数总结算法 第2篇

先从一个形象的例子说起：P1005 [NOIP2007 提高组] 矩阵取数游戏

PS:高精度其实远远不仅限于oi，它作为一种重要的数据结构，在编程应用里面也是很重要的。

 这道题其实主要是一个简单的动态规划，那我们具体的主要=题不是它，我们需要注意的是，根据数据的范围，发现最大数为80x1000x(2^81-1)，显然超了Long int但是不会超过128位。这就需要我们对高精度做一个简单的处理。

key:

1.用储存a的高位，储存a的低位。高位显然不会溢出（因为只有2^81-1），所以将低位的1e18空出，防止两数相加时溢出.

2.输出时要格外注意：当高位为零时直接输出低位；当高位不为零时直接输出高位，低位位数不足18位要补零.

struct int128//结构体更自然  {     long long hig;     long long low; };//定义int128,最简单的雏形就有了

高精度加法，就是把低位和高位分开，低位高位分别相加，然后处理一下进位

int128 operator + (int128 a,int128 b)//重载运算符 {     int128 k;     ;     ;     ;//防止溢出,两个数加没问题，主要是怕后面很多加起来      ;     return k; }

高精度乘法也是，这里因为是最简单的结构，int128里面都是longlong的low high,不涉及数组，字符串等，我们也只要简单地把高位低位分开乘就行了，并且考虑进位

int128 operator * (int128 a,int b) {     int128 k;     ;     *b;     *;//xxx上同理，乘法就是加法      ;     return k; }

顺带提一下，使用模的思想在更复杂的时候会利于你的思路的整理

const long long p=1e18;//作mod用，10的18次方

大家可以通过这个十分简单的例子发现一个重要的思想，这也是传统的高精度算法核心：把一个超出long long或者由于需求，不想用太大的Longlong的时候，我们就把一个大数分为高位和低位，通过小学计算的思路，对高位低位分别进行操作，同时考虑模和进位的问题。

这就是最基本的思路，尤其使用于加减法，我们知道乘法和除法可以用一些更高级的算法来优化，但是加减法却是永远离不开这个思路。

当然出于题目的完整性，稍微提一下这里的dp思想，并给一个完整代码

PS：

f[l][l+len][i] 表示左端点为l，右端点为l+len,第i行取数所能获得的最大值（状态） f[l][l+len][i]=max(2*f[l+1][l+len][i]+2*a[i][l],2*f[l][l+len-1][i]+2*a[i][l+len]);（状态转移方程）

当然其实这道题还有一个两点是区间DP,有上下两行都要同时dp，然后状态方程使用了一个更为抽象的，对于每一行来说，f[1][m][]就是这一行所加数的最大值。

而这只是一个引入，下面让我们从数据结构和编程的角度去看高精度的事情

第一步：对数字进行处理，而我们往往需要对其反向reverse读入（当然不反向的也会在乘法里给）

struct bign{     int d[1000];     int len;     //下面定义构造函数，用来初始化！      bign(){         memset(d,0,sizeof(d));         len=0;     } };  //一般来说，大整数一般是使用字符串输入的，下面将字符串储存的大整数 //xxx结构体中 bign change(char str[]){     bign a;     (str);     for(int i=0;i

这样就完成一个转化，这里采取int数组是为了方便基础的计算，如果使用字符串操作也可行，但是要注意一个是字符中ascii码和xxx制转化的问题，然后还有输入的判断等，and可能还需要自己构建出一个字符串加减乘除（此内容以后有空我也会写）

第二步，既然读好了，那么大整数也已经出现了，我们可以先给一个比较函数，这对于后续加减以及debug都是很有帮助的

int compare(bign a,bign b){     if(;)return 1;//a大于b     else if(=0;i++){             if([i]>[i])return 1;             else if([i]

第三步，就按照上面的核心思想，很自然地给出加法和减法

bign add(bign a,bign b){     bign c;     int carry=0;//这里的carry表示进位     for(int i=0;i

同样根据小学计算规则，加法可能出现在第一位进位，需要单独判断。

对于减法，其实就是加法的附庸，两个正数相减，实质上就是一个正数加上一个负数

当然也要处理好借位到第一位，第一位变0的情况

bign sub(bign a,bign b){     bign c;     for(int i=0;i0){                          [i+1]--;             [i]+=10;          }         }         []=[i][i];     }     while(;=1&&[]==0){         ;     }//去除高位为0的！同时保留一个最低位      return c; } 

第四步，关注一下乘除法，其实也依旧是竖式的方法一个个乘过去（不会有人想ab用b个a加起来实现吧，不会吧不会吧）

bign multi(bign a,int b){     bign c;     int carry=0;     for(int i=0;i

除法也一样

//高精度xxx低精度的除法 bign divide(bign a,int b,int &r){//r为余数，这里表示为引用     bign c;     ;     for(int i=;i>=0;i--){         r=r*10+[i];         if(r=1&&[]==0){         ;     }     return c; } 

但是！通过上面两个代码，大家有没有发现，诶，这都是一个大整数和一个正常的整数计算呢，我想要大整数和大整数计算行不行呢？

答案当然是可以的，_只是一般来说这几个例子其实已经可以应付大部分情况了，而两个大整数的乘除也可以通过加减法实现......_这就是我去年的想法。课实际上，当我们仔细去思考的时候，通过加减实现，是怎么个实现呢？我曾一度以为就是一位一位乘然后一个一个加，或者一位一位除，但是这样子，如果144444444444乘15555555555，你算算要加多少次，显然这个时候会超时，因此我把高阶的乘法放在了第三模块，小伙伴们可以去看看。不过首先，这上面的几个基础方法要掌握。

整数总结算法 第3篇

这也算是写这篇博客的动因了吧，在上文中我已经提到了，如果两个大整数的结构体之类的东西相互做乘除法，如果还是用那么朴素的加变乘就会出现一些问题，所以需要我们对计算作出一些处理。

先给出一个类的定义

我们只关注最后两个加法和乘法的重载，以及private元素的定义是int数组

还是一样，加法想必大家现在已经能轻松地给出了，无非需要讨论几个特殊点，已经两个加数的长度什么的。为利于理解，我改了一下，三种情况用if分开了

 然后关键点来了，乘法！

先给大家看一段超时的代码

...找不到了...好吧给大家讲一下：我们假设14乘以12，那么我们根据竖式，14在上，12在下，于是竖式下面第一行计算2*14=28，第二行计算1*14=14,又因为是第二行，于是乎乘10^(i-1)，i代表第几行，所以结果是140+28=168.那么我们无非就是用加法模拟一下这个过程，14个2加起来.......

所以这个是比较慢的

那快的代码是什么呢？是不用竖式吗？不，依旧是用竖式，但是在进位和分行算的问题上进行了优化。

先贴出来

 其实很多人看了这个代码就应该明白了吧，但我知道这个的时候还是呆了一下，使用这里还要根据宿舍同学的解释哈哈，当然，今天是我解释给你们听

首先最外圈的循环，就是循环一个数的长度，随便哪一个，反正谁做乘数谁做被乘数一样的。

cur就代表位数，high代表行数，给xxx图：

但是我们要注意在算法中，是把各个行数，每一列上的进位等等都是同时做处理的

 [cur] = [cur] + (a[j]*[i]) % 10;这一句就是说，[i]第i列上的最终结果

[cur + 1] = [cur + 1] + (a[j] * [i]) /10;是第i+1列最终结果，这里同时处理了进位

if ([cur] > 9)这个意思是，比如我这一列有0 1 2 3 四行，0行上是9,1行上是8,，2行是1，3行是0 ，8+9=17显然不能在一位中表示出来，所以也要进位，最后这一列的结果是7+1+0=8

所以接下来的就很明显了，多了一个restt只是为了处理多一位的问题罢了

好啦，这就是今天的内容啦，天呐学校又感觉要封校了......周末出游计划又泡汤了.....

有错误的地方欢迎大家指正。

                                                                                                                                    21计科xxx

打个小广告，今年高考即将来临，南大也即将迎来百廿周年，欢迎报考南京大学！