做 ACM 题的时候, 经常遇到大数的加减乘除, 乘幂, 阶乘的计算, 这时给定的数据类型往往不够表示最后结果, 这时就需要用到高精度算法. 高精度算法的本质是把大数拆成若干固定长度的块, 然后对每一块进行相应的运算. 这里以考虑 4 位数字为一块为例, 且输入的大数均为正整数 (也可以考虑其他位, 但要注意在每一块进行相应运算时不能超出数据类型的数值范围; 有负整数的话读入时判断一下正负号在决定运算).
1. 高精度加法
以 3479957928375817 + 897259321544245 为例:
3479 | 9579 | 2837 | 5817 |
---|---|---|---|
+897 | +2593 | +2154 | +4245 |
= | = | = | = |
4376 | 12172 | 4991 | 10062 |
进位 0 | 进位 1 | 进位 0 | 进位 1 |
4377 | 2172 | 4992 | 0062 |
C 语言实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 200
- // 整数乘幂运算函数
- int Pow(int a, int b)
- {
- int i = 0, result = 1;
- for(i = 0; i <b; ++i)
- {
- result *= a;
- }
- return result;
- }
- //High Precision Of Addition
- int main()
- {
- char stra[N], strb[N]; // 字符串数组, 以字符形式储存两个大数;
- int i = 0, step = 4, carry = 0; //step 表示块长, carry 为进位位;
- int lengtha, lengthb, maxlength, resultsize; //maxlength 表示 stra 和 strb 二者长度较大的那个;
- int numa[N], numb[N],numc[N]; // 依次储存被加数, 加数, 和;
- memset(numa, 0, sizeof(numa));
- memset(numb, 0, sizeof(numb));
- memset(numc, 0, sizeof(numc)); // 初始化为零;
- scanf("%s%s", stra, strb);
- lengtha = strlen(stra);
- lengthb = strlen(strb); // 计算两个大数的长度
- // 字符数字转为四位一块的整数数字
- for(i = lengtha-1; i>= 0; --i)
- {
- numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
- }
- for(i = lengthb-1; i>= 0; --i)
- {
- numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
- }
- maxlength = lengtha> lengthb ? lengtha : lengthb;
- // 逐块相加, 并进位
- for(i = 0; i <= maxlength/step; ++i)
- {
- numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry; // 计算和
- carry = (numa[i] + numb[i])/Pow(10, step); // 计算进位
- }
- // 计算最后和的块的总数
- resultsize = numc[maxlength/step]> 0 ? maxlength/step : maxlength/step - 1;
- printf("%d", numc[resultsize]);
- for(i = resultsize-1; i>= 0; --i)
- {
- printf("%04d", numc[i]); // 右对齐, 补零输出;
- }
- printf("\n");
- return 0;
- }
2. 高精度减法
与加法类似, 不同的是要注意正负号和显示位数的变化. 以 99999037289799 - 100004642015000 为例:
先判断被减数和减数哪个大, 显然这里减数大, 故输出结果为负数. 在用大数减去小数,(若某一块相减为负数, 则要向高位块借位) 如下表
100 | 0046 | 4201 | 5000 |
---|---|---|---|
-99 | -9990 | -3728 | -9799 |
1 | 56 | 473 | 5201 |
借位 0 | 借位 1 | 借位 0 | 借位 1 |
0 | 56 | 472 | 5201 |
C 语言实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 200
- // 整数乘幂运算函数
- int Pow(int a, int b)
- {
- int i = 0, result = 1;
- for(i = 0; i <b; ++i)
- {
- result *= a;
- }
- return result;
- }
- //High Precision Of Subtraction
- int main()
- {
- char stra[N], strb[N]; // 字符串数组, 以字符形式储存两个大数;
- int i = 0, step = 4, borrow = 0, mark = 0; //step 表示块长, borrow 为借位位, mark 为结果符号位;
- int lengtha, lengthb, maxlength, resultsize; //maxlength 表示 stra 和 strb 二者长度较大的那个;
- int numa[N], numb[N],numc[N], *maxnum, *minnum; // 依次储存被减数, 减数, 和;
- memset(stra, 0, sizeof(stra));
- memset(strb, 0, sizeof(strb));
- memset(numa, 0, sizeof(numa));
- memset(numb, 0, sizeof(numb));
- memset(numc, 0, sizeof(numc)); // 初始化为零;
- scanf("%s%s", stra, strb);
- lengtha = strlen(stra);
- lengthb = strlen(strb); // 计算两个大数的长度
- maxlength = lengtha>= lengthb ? lengtha : lengthb;
- // 字符数字转为四位一块的整数数字
- for(i = lengtha-1; i>= 0; --i)
- {
- numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
- }
- for(i = lengthb-1; i>= 0; --i)
- {
- numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
- }
- // 找出较大的数
- maxnum = numa;
- minnum = numb;
- mark = 1;
- for(i = (maxlength-1)/step; i>= 0; --i)
- {
- if(numa[i]> numb[i])
- {
- maxnum = numa;
- minnum = numb;
- mark = 1;
- break;
- }
- else if(numa[i] <numb[i])
- {
- maxnum = numb;
- minnum = numa;
- mark = -1;
- break;
- }
- }
- // 逐块相减, 并借位
- for(i = 0; i <= maxlength/step; ++i)
- {
- numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step); // 计算差
- borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; // 计算借位
- }
- // 计算最后和的块的总数
- resultsize = maxlength/step;
- while(!numc[resultsize]) --resultsize;
- printf("%d", mark*numc[resultsize]);
- for(i = resultsize-1; i>= 0; --i)
- {
- printf("%04d", numc[i]); // 右对齐, 补零输出;
- }
- printf("\n");
- return 0;
- }
3. 高精度乘法
乘法可以看作是乘数每一位与被乘数相乘后再相加, 以 4296556241 x 56241 为例:
被乘数 | 42 | 9655 | 6241 |
---|
乘数 | 5 | 6 | 2 | 4 | 1 |
---|
被乘数 x 乘数 | 42 | 9655 | 6241 |
---|---|---|---|
1 | 42 | 9655 | 6241 |
4 | 168*10 | 38620*10 | 24964*10 |
2 | 84*100 | 19310*100 | 12482*100 |
6 | 252*1000 | 57930*1000 | 37446*1000 |
5 | 210*10000 | 48275*10000 | 31205*10000 |
累加和 | 2362122 | 543006855 | 351000081 |
进位(从低位向高位) | 241 | 54304 | 35100 |
积 | 241 | 6426 | 1955 | 0081 |
---|
C 语言实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 200
- // 整数乘幂运算函数
- int Pow(int a, int b)
- {
- int i = 0, result = 1;
- for(i = 0; i <b; ++i)
- {
- result *= a;
- }
- return result;
- }
- //High Precision Of Multiplication
- int main()
- {
- char stra[N], strb[N]; // 字符串数组, 以字符形式储存两个大数;
- int i = 0, j = 0, k = 0, step = 4, carry = 0; //step 表示块长, carry 为进位位;
- int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize 储存块的总数, eachnum 用来储存乘数的每一位
- int numa[N], numb[N], numc[N], tmp[N]; // 依次储存被乘数数 & 积, 乘数;
- memset(numa, 0, sizeof(numa));
- memset(numb, 0, sizeof(numb));
- memset(numc, 0, sizeof(numc)); // 初始化为零;
- scanf("%s%s", stra, strb);
- lengtha = strlen(stra);
- lengthb = strlen(strb); // 计算两个大数的长度
- // 将被乘数字符数字转为四位一块的整数数字
- for(i = lengtha-1; i>= 0; --i)
- {
- numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
- }
- // 将乘数数字字符数字转为一位一块的整数数字
- for(i = lengthb-1; i>= 0; --i)
- {
- numb[lengthb-1-i] = strb[i]-'0';
- }
- resultsize = tmpsize = (lengtha-1)/step;
- // 取乘数的每一位与被乘数的逐块相乘, 并进位;
- for(i = 0; i <lengthb; ++i)
- {
- memcpy(tmp, numa, sizeof(numa)); // 将 numa 数组赋值给 tmp 数组;
- k = i/step; //k 储存每一块需要向高位块移动的次数;
- if(k)
- {
- for(j = tmpsize; j>= 0; --j)
- {
- tmp[j+k] = tmp[j];
- tmp[j] = 0;
- }
- tmpsize += k;
- }
- // 乘以乘数每一位扩展成的块;
- eachnum = numb[i]*Pow(10, i%step);
- for(j = 0; j <= tmpsize; ++j)
- {
- tmp[j] *= eachnum;
- }
- // 大数相加
- carry = 0; // 进位置零;
- for(j = 0; j <= resultsize; ++j)
- {
- numc[j] += tmp[j] + carry;
- carry = numc[j]/Pow(10,step);
- numc[j] %= Pow(10, step);
- }
- if(carry)
- {
- ++resultsize;
- numc[j] += carry;
- }
- }
- // 输出
- printf("%d", numc[resultsize]);
- for(i = resultsize-1; i>= 0; --i)
- {
- printf("%04d", numc[i]); // 右对齐, 补零输出;
- }
- printf("\n");
- return 0;
- }
4. 高精度除法
高精度除法有两种, 一种是高精度除以低精度, 另一种是高精度除以高精度. 前者只需将每一块除以低精度除数即可; 后者则考虑用高精度减法来实现, 即每次减去高精度除数, 直到减到小于除数, 则减的次数即为商, 剩余的即为余数.
高精度除以低精度
以 9876342876 / 343 为例:
被除数 | 98 | 7634 | 2876 |
---|
除数 | 343 |
---|
向低位块进位 | 98 | 137 | 190 |
---|---|---|---|
商 | 0 | 2879 | 4002 |
余数 | 190 |
---|
C 语言代码实现如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 200
- // 整数乘幂运算函数
- int Pow(int a, int b)
- {
- int i = 0, result = 1;
- for(i = 0; i <b; ++i)
- {
- result *= a;
- }
- return result;
- }
- //High Precision Of division
- //(1) 高精度除以低精度
- int main()
- {
- char stra[N]; // 字符串数组, 以字符形式储存高精度被除数;
- int i = 0, step = 4, carry = 0; //step 表示块长, carry 为高位向低位进位位;
- int lengtha, resultsize;
- int numa[N], numb, numc[N], numd; // 依次储存被除数, 除数, 商, 余数;
- memset(numa, 0, sizeof(numa));
- memset(numc, 0, sizeof(numc)); // 初始化为零;
- scanf("%s%d", stra, &numb);
- lengtha = strlen(stra); // 计算被除数的长度
- // 字符数字转为四位一块的整数数字
- for(i = lengtha-1; i>= 0; --i)
- {
- numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
- }
- carry = 0; // 高位向低位进位位置零
- resultsize = (lengtha-1)/step;
- // 逐块相除, 高位向低位进位
- for(i = resultsize; i>= 0; --i)
- {
- numc[i] = (numa[i] + carry*Pow(10,step))/numb; // 计算商
- carry = (numa[i] + carry*Pow(10,step))%numb; // 计算进位
- }
- numd = carry; // 最低位块的余数即为整个除法的余数
- // 计算最后和的块的总数
- while(!numc[resultsize]) --resultsize;
- // 输出商
- printf("%d", numc[resultsize]);
- for(i = resultsize-1; i>= 0; --i)
- {
- printf("%04d", numc[i]); // 右对齐, 补零输出;
- }
- // 输出余数
- printf("\n%d\n", numd);
- return 0;
- }
高精度除以高精度
以 176342876 / 3453452 为例:
被除数 | 176342876 |
---|---|
- (51 x 除数 ) | 51 x 3453452 |
余数 | 216824 |
商 | 51 |
C 语言代码实现如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 200
- // 整数乘幂运算函数
- int Pow(int a, int b)
- {
- int i = 0, result = 1;
- for(i = 0; i <b; ++i)
- {
- result *= a;
- }
- return result;
- }
- //High Precision Of division
- //(2) 高精度除以高精度
- int main()
- {
- char stra[N], strb[N]; // 字符串数组, 以字符形式储存两个大数;
- int i = 0, step = 4, borrow = 0; //step 表示块长, borrow 为进位位;
- int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark; //maxlength 表示 stra 和 strb 二者长度较大的那个;
- int numa[N], numb[N], numc[N], numd[N]; // 依次储存被除数数, 除数数, 商, 余数;
- memset(stra, 0, sizeof(stra));
- memset(strb, 0, sizeof(strb));
- memset(numa, 0, sizeof(numa));
- memset(numb, 0, sizeof(numb));
- memset(numc, 0, sizeof(numc));
- memset(numd, 0, sizeof(numd)); // 初始化为零;
- scanf("%s%s", stra, strb);
- lengtha = strlen(stra);
- lengthb = strlen(strb); // 计算两个大数的长度
- // 字符数字转为四位一块的整数数字
- for(i = lengtha-1; i>= 0; --i)
- {
- numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
- }
- for(i = lengthb-1; i>= 0; --i)
- {
- numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
- }
- memcpy(numd, numa, sizeof(numa));
- numbsize = (lengthb-1)/step;
- numcsize = 0;
- numdsize = (lengtha-1)/step;
- do
- {
- maxsize = numdsize> numbsize ? numdsize : numbsize;
- // 计算剩余数是否小于除数
- mark = 1;
- for(i = maxsize; i>= 0; --i)
- {
- if(numd[i]> numb[i])
- {
- mark = 1;
- break;
- }
- else if(numd[i] <numb[i])
- {
- mark = -1;
- break;
- }
- }
- // 判断是否余数已经小于除数
- if(!(mark+1)) break;
- borrow = 0; // 借位置零;
- // 逐块相减, 并借位
- for(i = 0; i <= maxsize; ++i)
- {
- tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step); // 计算差
- borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; // 计算借位
- numd[i] = tmpnum;
- }
- while(!numd[numdsize]) --numdsize;
- // 每减一个除数, 商加一;
- borrow = 1;
- for(i = 0; i <= numcsize; ++i)
- {
- numc[i] += borrow;
- borrow = numc[i]/Pow(10,step);
- numc[i] %= Pow(10,step);
- }
- if(borrow)
- {
- ++numcsize;
- numc[i] += borrow;
- }
- }while(1);
- printf("%d", numc[numcsize]);
- for(i = numcsize-1; i>= 0; --i)
- {
- printf("%04d", numc[i]); // 右对齐, 补零输出;
- }
- printf("\n");
- printf("%d", numd[numdsize]);
- for(i = numdsize-1; i>= 0; --i)
- {
- printf("%04d", numd[i]); // 右对齐, 补零输出;
- }
- printf("\n");
- return 0;
- }
来源: https://www.cnblogs.com/BlueHeart0621/p/12238176.html