高精度

阅读数: 10000次 2022-01-17

高精度运算

1
2
3

int a ;//数据类型的范围：-2^31~2^31-1,数量级为10^9
long long int ;//数据类型范围：-2^63~2^63-1,数量级为10^18
//由于进行较大的数运算时，无法用Int 和long long 所以下面需要学习高精度

一.高精度的加法

//算法核心；
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;

完整代码：

//代码
#include<iostream>
using namespace std;
#include<math.h>
#include<string.h>
int a[505],b[505],c[505];
char s1[505],s2[505];
int main()
{
	int la,lb,lc,i;
	cin>>s1>>s2;
	la=strlen(s1);
	lb=strlen(s2);//从s[0]开始储存 
	for(i=0;i<la;i++)
	 a[la-i]=s1[i]-'0';//将字符转换成数字，并将字符转置便于计算 
	for(i=0;i<lb;i++)
	 b[lb-i]=s2[i]-'0';//将字符转换成数字，并将字符转置便于计算 
	lc=max(la,lb)+1;//新数组的长度
	for(i=1;i<=lc;i++)
	{
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]=c[i]%10; 
	} 
	if(c[lc]==0 && lc>0) lc--;//删除前导零,同时lc的长度不能为0，所以要求lc>0 || lc>=1 
	for(i=lc;i>=1;i--)
	 cout<<c[i]; 
	return 0;
}

二.高精度的减法

//核心代码
if(a[i]<b[i])//如果该位的数小，需要向高位借位，那么高位将会减一，因为是十进制，所以地位会加10，然后再进行加法
{
    c[i+1]--;
    c[i]+=10;
}
c[i]=a[i]-b[i];

完整代码：

//代码
#include<iostream>
using namespace std;
#include<math.h>
#include<string.h>
int a[10086],b[10086],c[10086];
char s1[10086],s2[10086],s3[10086];

//比较函数
bool compare(char s1[],char s2[])
{
	int m=strlen(s1),n=strlen(s2);
	if(m!=n) return m>n;//不同长度 
	for(int i=0;i<m;i++)//同等长度下 
	{
		if(s1[i]!=s2[i]) return s1[i]>s2[i];
	}
	return true;
} 
int main()
{
	int la,lb,lc,i,flag;
	cin>>s1>>s2;
	if(!compare(s1,s2))//ifcompare(s1,s2)为false才会执行,此时s1<s2,需要交换 
	{
		flag=1;
		strcpy(s3,s1);
		strcpy(s1,s2);
		strcpy(s2,s3);
	}
	la=strlen(s1);
	lb=strlen(s2);//从s[0]开始储存 
	for(i=0;i<la;i++)
	    a[la-i]=s1[i]-'0';//将字符转换成数字，并将字符转置便于计算 
	for(i=0;i<lb;i++)
	    b[lb-i]=s2[i]-'0';
	lc=max(la,lb);
	for(i=1;i<=lc;i++)
	{
		if(a[i]<b[i])
		{
			a[i+1]--;
			a[i]+=10;
		}
		c[i]=a[i]-b[i];
	}
	while(c[lc]==0 && lc>1) lc--;
	if(flag==1) cout<<"-";
	for(i=lc;i>0;i--)
	 cout<<c[i];
	return 0;
}

三.高精度的乘法

//核心算法
c[i+j-1] +=a[i]*a[j];
c[i+j] +=c[i+j-1]/10;
c[i+j-1] %=10;

完整代码：

#include<iostream>
using namespace std;
#include<math.h>
#include<string.h>
int a[2005],b[2005],c[2005];
char s1[2005],s2[2005];
int main()
{
	int la,lb,lc,i;
	cin>>s1>>s2;
	la=strlen(s1);
	lb=strlen(s2);//从s[0]开始储存 
	for(i=0;i<la;i++)
	    a[la-i]=s1[i]-'0';//将字符转换成数字，并将字符转置便于计算 
	for(i=0;i<lb;i++)
	    b[lb-i]=s2[i]-'0';
	lc=la+lb;//最长的长度小于等于两数长度之和 
	for(i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			c[i+j-1] +=a[i]*a[j];
			c[i+j] +=c[i+j-1]/10;
			c[i+j-1] %=10; 
		}
	} 
	if(c[lc]==0 && lc>0) lc--;
	for(i=lc;i>0;i--)
	 cout<<c[i];
	return 0;
}

四.高精度除法

高精度除以低精度

//核心代码
c[i]=(x*10+a[i])/b;
x=(x*10+a[i])%b;

完整代码：

#include<iostream>
#include<string.h> 
using namespace std;
char s1[5005];
long long b,c[5005],x,a[5005],la,lc;
//高精度除以低精度 
int main()
{
	cin>>s1>>b;//读入被除数和除数
	la=strlen(s1);
	for(int i=1;i<=la;i++)//将被除数一位一位放入数组 
	 a[i]=s1[i-1]-'0';
	for(int i=1;i<=la;i++)
	{
		c[i]=(x*10+a[i])/b;//得到可以整除的后的整数
		x=(x*10+a[i])%b;//为了得到余数
	}
	lc=1;
	while(c[lc]==0 && lc<la) lc++;
	for(int i=lc;i<=la;i++)
	 cout<<c[i];
	return 0;
}

高精度除以高精度

完整代码：

#include<iostream>
#include<string.h> 
using namespace std;
char s1[305],s2[305];
int a[305],b[305],c[305],tmp[305];//a为被除数，b为除数，c为商 
void init(int *x)
{
	char s[305];
	cin>>s;
	x[0]=strlen(s);//为字符串的长度 
	for(int i=0;i<x[0];i++)
	{
		x[x[0]-i]=s[i]-'0';//为了便于计算，将字符串转换为数字，并且倒序储存 
	}
}
void print(int a[])
{
	if(a[0]==0)
	{
		cout<<0;
		return;
	}
	for(int i=a[0];i>0;i--) cout<<a[i];
	return ;
}

int compare(int a[],int b[])
{//返回1代表a>b，返回0代表a=b。返回-1代表a<b 
	if(a[0]>b[0]) return 1;
	if(a[0]<b[0]) return -1;
	for(int i=a[0];i>0;i--)
	{
		if(a[i]>b[i]) return 1;
		if(a[i]<b[i]) return -1;
	}
	return 0;
}

void minu(int a[],int b[])//进行相减 
{
	for(int i=1;i<=a[0];i++)
	{
		if(a[i]<b[i])
		{
			a[i+1]--;
			a[i]+=10;
		}
		a[i]=a[i]-b[i];
	}
	while(a[a[0]]==0 && a[0]>0) a[0]--;
}
void numcpy(int p[],int q[],int n)//将p数组整体移动n位到q数组中 
{
	for(int i=1;i<=p[0];i++) q[i+n-1]=p[i];
	q[0]=p[0]+n-1;
}
	
	
int main()
{
	init(a);//输入a
	init(b);//输入b
	int i;
	c[0]=a[0]-b[0]+1;
	for(i=c[0];i>=1;i--)
	{
		memset(tmp,0,sizeof(tmp));
		numcpy(b,tmp,i);
		while(compare(a,tmp)>=0)
		{
			c[i]++;
			minu(a,tmp);
		}
    }
	while(c[c[0]]==0 && c[0]>0) c[0]--;
	print(c);
	cout<<endl;
	print(a);
	return 0; 
}