什么是高精度算法？它是處理大數(shù)字的數(shù)學(xué)計(jì)算方法。在一般的科學(xué)計(jì)算中，會(huì)經(jīng)常算到小數(shù)點(diǎn)后幾百位或者更多，當(dāng)然也可能是幾千億幾百億的大數(shù)字。一般這類(lèi)數(shù)字我們統(tǒng)稱(chēng)為高精度數(shù)。但近幾年的CSPJ/S復(fù)賽貌似從未單獨(dú)考過(guò)高精度算法，但有時(shí)會(huì)和其他算法一起考。所以還是有學(xué)習(xí)的必要。

一、高精度計(jì)算

高精度計(jì)算是指參與運(yùn)算的數(shù)的范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類(lèi)型能表示的范圍的運(yùn)算。如100位數(shù)字和100位數(shù)字的加減乘除運(yùn)算。為處理高精度計(jì)算，我們使用數(shù)字?jǐn)?shù)組來(lái)表示高精度數(shù)字。

二、數(shù)字?jǐn)?shù)組

數(shù)字?jǐn)?shù)組：第0位置保存數(shù)字位數(shù)，而后從低位到高位保存各位數(shù)字，每個(gè)數(shù)組元素保存一位數(shù)字。

數(shù)字?jǐn)?shù)組必須初始化為0，因?yàn)檫M(jìn)行高精度計(jì)算時(shí)，會(huì)默認(rèn)數(shù)字?jǐn)?shù)組各位都為0。

(以下N為常量，表示高精度數(shù)字最大位數(shù))

將數(shù)組元素初始化為0的幾種寫(xiě)法：

（1）設(shè)為全局變量: int a[N];

（2）設(shè)為局部變量: int a[N] = {};

（3）需要時(shí)，將數(shù)組各元素設(shè)為0：memset(a, 0, sizeof(a));

高精度計(jì)算使用數(shù)字?jǐn)?shù)組模擬各種計(jì)算過(guò)程，完成各種計(jì)算。

三、代碼風(fēng)格

主要有三種風(fēng)格：數(shù)組與函數(shù)，結(jié)構(gòu)體與函數(shù)，類(lèi)中重載運(yùn)算符

四、 解題過(guò)程

面對(duì)高精度問(wèn)題時(shí)，可以先將各個(gè)量當(dāng)成低精度數(shù)字，寫(xiě)出代碼。然后再將代碼轉(zhuǎn)為高精度計(jì)算。以下介紹中，會(huì)給出每個(gè)高精度運(yùn)算中的操作在如果是在低精度運(yùn)算中的等價(jià)代碼。

五、高精度算法的思路

（1）高精度加法：用字符串輸入兩個(gè)數(shù)，再導(dǎo)入數(shù)組，然后每位相加，如果某位數(shù)字>10，則此位模10，下一位加一，最后用while循環(huán)去除前導(dǎo)零再輸出即可。

代碼如下：

#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）高精度減法：用字符串輸入兩個(gè)數(shù)，再導(dǎo)入數(shù)組，判斷是否后數(shù)比前數(shù)，如果是則輸出負(fù)號(hào)再交換數(shù)組。然后按位相減不夠借1，最后用while循環(huán)去除前導(dǎo)零再輸出即可。

#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）高精度乘法：導(dǎo)入方法與前面一樣，導(dǎo)入后按乘法豎式思路相乘，再按常規(guī)思路進(jìn)位。最后去除前導(dǎo)零就行了。

#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;
}