浅谈高精度算法(加减乘除)

2019-08-07| 发布者: admin| 查看: |

在c/c++中,不时会遇到限定数据范围的情况,我们先来看看常用的int和long long两种数据类型的范围吧。

c++标准规定,int占一个机器字长。在32位系统中int占32位,也就是4个字节,所以在32位系统中,int的范围是[-2^31,2^31-1],为10^9数量级;而long long的范围则是[-2^63,2^63-1],为10^18数量级,但当一些acm/oi题目中测试数据范围超过此范围,甚至超过double时,该怎么办?java有大数类,而python的整数也是不限制长度的,虽然c++的整数长度受到限制,但我们也有高精度算法,下面,我将介绍几种常见的高精度整算法。

一、高精度加法。

对于10^308以上的大数,确实不能用c++内置的数据类型直接处理,但回想我们曾经做过的小学算术问题,两个整数相加,先从个位算起,过十进位,依照这个思路,我们可以将大数存放在数组中,再利用数组去模拟加法运算的过程,代码如下:

#include iostream 
#include cstring 
using namespace std;
char 云顶娱乐平台手机版s1[505],s2[505];
int a[505],b[505],c[505];
int main{
 int m,n,v,t;
 std::ios::sync_with_stdio;
 cin s1 s2;
 m=strlen;
 n=strlen;
 memset);
 memset);
 for{
 a[m-1-i]=s1[i]-'0';
 for{
 b[n-1-i]=s2[i]-'0';
 m=max;
 m++;
 memset);
 for{ 
 v=a[i]+b[i];
 if 10)
 c[i]+=v;
 else{
 c[i+1]+=/10;
 c[i]=%10; 
 } 

//下面是一种更简单的做法,结果直接储存在a中 /*for{ a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; if m--; for cout c[i]; return 0; }


二、高精度减法。

和高精度加法的基本思路相同,不过在减法中,需要确定输入数字的相对大小来判断是否输出负号,还需要注意是否要"借位"。上代码:

#include iostream 
#include cstring 
using namespace std;
bool compare{
 int u=strlen,v=strlen;
 if
 return u 
 for
 if return s1[i] s2[i];
 return true;
} //比较两个数相对大小 
int main{
 std::ios::sync_with_stdio;
 int flag=1,i,j;
 char s1[100005],s2[100005],s3[100005]; //这里为节省空间考虑,直接用char数组运算 
 cin s1 s2;
 if);
 else{
 flag=-1;
 strcpy;
 strcpy;
 strcpy;
 int u=strlen,v=strlen;
 for{
 if{
 s1[i-1]-=1;
 s3[i]=s1[i]-s2[j]+10+'0';
 else s3[i]=s1[i]-s2[j]+'0';
 } //从最后一位向前减 
 for {
 if{
 s1[i-1]-=1;
 s3[i]=s1[i]+10;
 else s3[i]=s1[i];
 } //s1数位大,所以还有s1减'0' 
 for; //只到u-1的原因时 
 if cout '-';
 cout s3+i;
 return 0;
}

三、高精度乘法。

依旧是模拟算术做竖式乘法的过程,要注意进位,贴代码:

#include iostream 
#include cstring 
using namespace std;
char a[2005],b[2005];
int c[2005],d[2005],e[4005];
int u,v,w;
int main{
 int i,j;
 cin a b;
 u=strlen;
 v=strlen;
 memset;
 for
 c[u-1-i]=a[i]-'0';
 for
 d[v-1-i]=b[i]-'0';
 for{
 for{
 w=c[i]*d[j];
 if e[i+j]+=w;
 else{
 e[i+j+1]+=/10;
 e[i+j]=%10;
 for; //此处是为了不漏掉输出结果为0而将条件写为i 0 
 for cout e[i];
 return 0;
}

四、高精度除法。

高精度除法分两种,都是仿照竖式除法实现,一种是高精度除以低精度,较为容易实现,主要是利用一个数,在线处理:

#include iostream 
#include cstring 
#include string 
using namespace std;
char s1[5005];
int a[5005],b,c[5005],x=0;
int main{
 cin s1 b;
 a[0]=strlen;
 for a[i]=s1[i-1]-48;
 memset);
 for{
 c[i]=/b;
 x=%b; 
 } //核心部分
 x=1;
 while x++;
 for cout c[x]; 
 return 0;
}

另一种,是运用逐次相减的方法确定出商和余数,代码如下:

#include iostream 
#include cstring 
using namespace std;
int a[5005],b[5005],c[5005],d[5005];
bool compare{
 if return a[0] b[0];
 for{
 if return a[i] b[i];
 return true;
int main{
 std::ios::sync_with_stdio;
 string s1,s2;
 cin s1 s2;
 memset);
 memset);
 a[0]=s1.length;
 b[0]=s2.length;
 for a[i]=s1[a[0]-i]-'0';
 for b[i]=s2[b[0]-i]-'0';
 c[0]=a[0]-b[0]+1;
 for{ //c[0]代表最初a,b的数位差 
 memset);
 for
 d[j+i-1]=b[j];
 d[0]=b[0]+i-1; //先让b中存下的数与a在一个数量级 
 while){ //比较,如果a比较大,用a直接减去d,如果a比较小,下一次大循环中,d的位数会减一 
 c[i]++;
 for{
 a[i]-=d[i];
 if{
 a[i+1]--;
 a[i]+=10;
 while a[0]--;
 while c[0]--;
 cout "商:";
 for cout c[i];
 cout endl "余数:";
 for cout a[i]; //a中最后剩下的就是余数 
 return 0;
}

好的,高精度基础算法介绍完毕,大家不妨自行动手一试。