做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为例:
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/483681.html