高精度计算的应用

什么是高精度算法？它是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数。但近几年的CSPJ/S复赛貌似从未单独考过高精度算法，但有时会和其他算法一起考。所以还是有学习的必要。

一、高精度计算

高精度计算是指参与运算的数的范围大大超出了标准数据类型能表示的范围的运算。如100位数字和100位数字的加减乘除运算。为处理高精度计算，我们使用数字数组来表示高精度数字。

二、数字数组

数字数组：第0位置保存数字位数，而后从低位到高位保存各位数字，每个数组元素保存一位数字。

数字数组必须初始化为0，因为进行高精度计算时，会默认数字数组各位都为0。

(以下N为常量，表示高精度数字最大位数)

将数组元素初始化为0的几种写法：

（1）设为全局变量: int a[N];

（2）设为局部变量: int a[N] = {};

（3）需要时，将数组各元素设为0：memset(a, 0, sizeof(a));

高精度计算使用数字数组模拟各种计算过程，完成各种计算。

三、代码风格

主要有三种风格：数组与函数，结构体与函数，类中重载运算符

四、 解题过程

面对高精度问题时，可以先将各个量当成低精度数字，写出代码。然后再将代码转为高精度计算。以下介绍中，会给出每个高精度运算中的操作在如果是在低精度运算中的等价代码。

五、高精度算法的思路

（1）高精度加法：用字符串输入两个数，再导入数组，然后每位相加，如果某位数字>10，则此位模10，下一位加一，最后用while循环去除前导零再输出即可。

代码如下：

#include<iostream>
#include<string>
using namespace std;
int a[301],b[301],c[302];
int init(int a[])
{
	string s;
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++)
		a[i]=s[len-1-i]-'0';
	return len;
}
int main()
{
	int lena=init(a);
	int lenb=init(b);
	int lenc=max(lena,lenb);
	for(int i=0;i<lenc;i++)
	{
		c[i]+=a[i]+b[i];
		if(c[i]>=10)
		{
			c[i+1]++;
			c[i]%=10;
		}
	}
	while(c[lenc]==0 && lenc>=0)
		lenc--;
	for(int i=lenc;i>=0;i--)
		cout<<c[i];
	return 0;
}

（2）高精度减法：用字符串输入两个数，再导入数组，判断是否后数比前数，如果是则输出负号再交换数组。然后按位相减不够借1，最后用while循环去除前导零再输出即可。

#include<iostream>
#include<string>
using namespace std;
int a[301],b[301],c[301];
int init(int a[],string &s)
{
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++)
		a[i]=s[len-1-i]-'0';
	return len;
}
int main()
{
	string s1,s2;
	int lena=init(a,s1);
	int lenb=init(b,s2);
	int lenc=max(lena,lenb);
	if(lena<lenb || (lena==lenb && s1<s2))
	{
		swap(a,b);
		cout<<"-";
	}
	for(int i=0;i<lenc;i++)
	{
		c[i]+=a[i]-b[i];
		if(c[i]<0)
		{
			c[i+1]--;
			c[i]+=10;
		}
	}
	lenc--;
	while(c[lenc]==0 && lenc>0)
		lenc--;
	for(int i=lenc;i>=0;i--)
		cout<<c[i];
	return 0;
}

（3）高精度乘法：导入方法与前面一样，导入后按乘法竖式思路相乘，再按常规思路进位。最后去除前导零就行了。

#include<iostream>
#include<string>
using namespace std;
int a[301],b[301],c[601];
int init(int a[])
{
	string s;
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++)
		a[i]=s[len-1-i]-'0';
	return len;
}
int main()
{
	int lena=init(a);
	int lenb=init(b);
	int lenc=lena+lenb;
	for(int i=0;i<lena;i++)
		for(int j=0;j<lenb;j++)
			c[i+j]+=a[i]*b[j];
	for(int i=0;i<lenc;i++)
		if(c[i]>=10)
		{
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	while(c[lenc]==0 && lenc>0)
		lenc--;
	for(int i=lenc;i>=0;i--)
		cout<<c[i];
	return 0;
}

（4）高精度除法

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    char str[100];
    int a[100],b,c[100];
    int lena,lenc;
    int x=0;
    int i;
 
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
 
    cin>>str;
    cin>>b;
    
    lena=strlen(str);
    for(i=0;i<lena;i++)
        a[i+1]=str[i]-'0';
 
    for(i=1;i<=lena;i++)
    {
        c[i]=(x*10+a[i])/b;
        x=(x*10+a[i])%b;
    }
    
    lenc=1;
    while(c[lenc]==0&&lenc<lena)
        lenc++;
        
    for(i=lenc;i<=lena;i++)
        cout<<c[i];
    cout<<endl;
    
    return 0;
}