C/C++高精度算法的实现

2023-08-02 12:54:04 134

做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
#include
#include
#defineN200

//整数乘幂运算函数
intPow(inta,intb)
{
inti=0,result=1;
for(i=0;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为例：

先判断被减数和减数哪个大，显然这里减数大，故输出结果为负数。在用大数减去小数，（若某一块相减为负数，则要向高位块借位）如下表

100	0046	4201	5000
-99	-9990	-3728	-9799
1	56	473	5201
借位0	借位1	借位0	借位1
0	56	472	5201

C语言实现代码如下：

#include
#include
#include
#defineN200

//整数乘幂运算函数
intPow(inta,intb)
{
inti=0,result=1;
for(i=0;i=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]=0;--i)
{
printf("%04d",numc[i]);//右对齐，补零输出；
}
printf("\n");
return0;
}

3.高精度乘法

乘法可以看作是乘数每一位与被乘数相乘后再相加，以4296556241x56241为例：

被乘数	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
#include
#include
#defineN200

//整数乘幂运算函数
intPow(inta,intb)
{
inti=0,result=1;
for(i=0;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=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");
return0;
}

4.高精度除法

高精度除法有两种，一种是高精度除以低精度，另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可；后者则考虑用高精度减法来实现，即每次减去高精度除数，直到减到小于除数，则减的次数即为商，剩余的即为余数。

高精度除以低精度
以9876342876/343为例：

被除数	98	7634	2876

除数	343

向低位块进位	98	137	190
商	0	2879	4002

余数	190

C语言代码实现如下：

#include
#include
#include
#defineN200

//整数乘幂运算函数
intPow(inta,intb)
{
inti=0,result=1;
for(i=0;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
-(51x 除数)	51x3453452
余数	216824
商	51

C语言代码实现如下：

#include
#include
#include
#defineN200

//整数乘幂运算函数
intPow(inta,intb)
{
inti=0,result=1;
for(i=0;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]=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;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C/C++高精度算法的实现

热门推荐

随机推荐