C++高精度算法的实现

做ACM题的时候经常遇到大数的加减乘除乘幂阶乘的计算这时给定的数据类型往往不够表示最后结果这时就需要用到高精度算法。高精度算法的本质是把大数拆成若干固定长度的块然后对每一块进行相应的运算。这里以考虑4位数字为一块为例且输入的大数均为正整数也可以考虑其他位但要注意在每一块进行相应运算时不能超出数据类型的数值范围有负整数的话读入时判断一下正负号在决定运算。1. 高精度加法以3479957928375817 897259321544245为例3479957928375817897259321544245437612172499110062进位0进位1进位0进位14377217249920062C语言实现代码如下12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include stdio.h#include stdlib.h#include string.h#define N 200//整数乘幂运算函数intPow(inta,intb){inti 0, result 1;for(i 0; i b; i){result * a;}returnresult;}//High Precision Of Additionintmain(){charstra[N], strb[N];//字符串数组以字符形式储存两个大数inti 0, step 4, carry 0;//step表示块长carry为进位位intlengtha, lengthb, maxlength, resultsize;//maxlength表示stra和strb二者长度较大的那个intnuma[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);return0;}2. 高精度减法与加法类似不同的是要注意正负号和显示位数的变化。以99999037289799 - 100004642015000为例先判断被减数和减数哪个大显然这里减数大故输出结果为负数。在用大数减去小数若某一块相减为负数则要向高位块借位如下表100004642015000-99-9990-3728-97991564735201借位0借位1借位0借位10564725201C语言实现代码如下1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include stdio.h#include stdlib.h#include string.h#define N 200//整数乘幂运算函数intPow(inta,intb){inti 0, result 1;for(i 0; i b; i){result * a;}returnresult;}//High Precision Of Subtractionintmain(){charstra[N], strb[N];//字符串数组以字符形式储存两个大数inti 0, step 4, borrow 0, mark 0;//step表示块长borrow为借位位, mark为结果符号位intlengtha, lengthb, maxlength, resultsize;//maxlength表示stra和strb二者长度较大的那个intnuma[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;}elseif(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);return0;}3. 高精度乘法乘法可以看作是乘数每一位与被乘数相乘后再相加以4296556241 x 56241为例被乘数4296556241乘数56241被乘数x乘数4296556241142965562414168*1038620*1024964*10284*10019310*10012482*1006252*100057930*100037446*10005210*1000048275*1000031205*10000累加和2362122543006855351000081进位从低位向高位2415430435100积241642619550081C语言实现代码如下1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include stdio.h#include stdlib.h#include string.h#define N 200//整数乘幂运算函数intPow(inta,intb){inti 0, result 1;for(i 0; i b; i){result * a;}returnresult;}//High Precision Of Multiplicationintmain(){charstra[N], strb[N];//字符串数组以字符形式储存两个大数inti 0, j 0, k 0, step 4, carry 0;//step表示块长carry为进位位intlengtha, lengthb, resultsize, tmpsize, eachnum;//resultsize储存块的总数eachnum用来储存乘数的每一位intnuma[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[jk] 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);return0;}4. 高精度除法高精度除法有两种一种是高精度除以低精度另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可后者则考虑用高精度减法来实现即每次减去高精度除数直到减到小于除数则减的次数即为商剩余的即为余数。高精度除以低精度以9876342876 / 343为例被除数9876342876除数343向低位块进位98137190商028794002余数190C语言代码实现如下123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include stdio.h#include stdlib.h#include string.h#define N 200//整数乘幂运算函数intPow(inta,intb){inti 0, result 1;for(i 0; i b; i){result * a;}returnresult;}//High Precision Of division//(1)高精度除以低精度intmain(){charstra[N];//字符串数组以字符形式储存高精度被除数inti 0, step 4, carry 0;//step表示块长carry为高位向低位进位位intlengtha, resultsize;intnuma[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);return0;}高精度除以高精度以176342876 / 3453452为例被除数176342876- (51 x 除数)51 x 3453452余数216824商51C语言代码实现如下123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109#include stdio.h#include stdlib.h#include string.h#define N 200//整数乘幂运算函数intPow(inta,intb){inti 0, result 1;for(i 0; i b; i){result * a;}returnresult;}//High Precision Of division//(2)高精度除以高精度intmain(){charstra[N], strb[N];//字符串数组以字符形式储存两个大数inti 0, step 4, borrow 0;//step表示块长borrow为进位位intlengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;//maxlength表示stra和strb二者长度较大的那个intnuma[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;}elseif(numd[i] numb[i]){mark -1;break;}}//判断是否余数已经小于除数if(!(mark1))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);return0;}以上就是本文的全部内容希望对大家的学习有所帮助