Hi~?o(*￣▽￣*)ブ，今天來一起看看c++算法之高精度
之后會持續(xù)更新有關c++算法系列，歡迎觀看！(#^.^#)
文章來源地址http://www.zghlxwxcb.cn/news/detail-816563.html
目錄
前言
使用高精度的目的：
基本方法介紹：?
?一、A+B?problem
基本思路解析：
具體步驟：
代碼如下：
二、A-B problem
基本思路解析：
?編輯
具體步驟:
?代碼如下：
?三、A*B problem
基本思路解析：
具體步驟（多一步去零）?
代碼如下：
?四、A/B problem
基本思路解析：
具體步驟（多一步去零）?
?代碼如下：
總結(jié)
前言
使用高精度的目的：
簡單來說，當一個數(shù)足夠大時，甚至超過longlong范圍，這個時候我們就可以用上高精度算法，對這些數(shù)進行加減乘除操作了
基本方法介紹：?
該算法最主要的就是數(shù)組了，我們把大數(shù)看作字符再存入數(shù)組中，再用數(shù)組記錄結(jié)果，最后用數(shù)組輸出，同時因為加減乘除運算的獨特性，還會對數(shù)組進行逆序輸出，排序等一系列操作
?
?一、A+B?problem
基本思路解析：
補充說明對a,b數(shù)組的操作 ：
| a[100000] | 由于是從個位加起，所以我們會將對a數(shù)組的錄入反過來，例如這里會有a[1]=8,a[2]=8,a[3]=1(從1開始還是從0開始都可以） |
| b[10000] | 由于是從個位加起，所以我會將對b數(shù)組的錄入反過來，例如里面會有b[1=8,b[2]=8,b[3]=1(從1開始還是從0開始都可以） |
具體步驟：
1.字符串讀入
string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
cin>>x>>y;
la=x.length();
lb=y.length();2.字符串轉(zhuǎn)數(shù)組
這里解釋一下，因為加法是從個位開始的，所以我們讓字符串的最后一位存到數(shù)組的第一個去
for(int i=0;i<la;i++)
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)
{
b[lb-i]=y[i]-'0';
}3.豎式加法?
lc=max(la,lb);//找到兩數(shù)間的最大值，最大的那個是結(jié)果的長度（或者是結(jié)果長度-1）
for(int i=1;i<=lc;i++)
{
c[i]+=a[i]+b[i];//注意這里的+=，這里+的是兩個數(shù)和前面進位的
c[i+1]=c[i]/10;//往前進一位
c[i]%=10;//進位后剩下的
} 4.倒序輸出
?
if(c[lc+1]>0)lc++;//最高位仍然進位，所以長度++
for(int i=lc;i>=1;i--)//逆序輸出
cout<<c[i];代碼如下：
#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
cin>>x>>y;
la=x.length();
lb=y.length();
for(int i=0;i<la;i++)//將大數(shù)轉(zhuǎn)化為一個個數(shù)字并且存入數(shù)組中順便進行逆存
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)//同上
{
b[lb-i]=y[i]-'0';
}
lc=max(la,lb);//找到兩數(shù)間的最大值，最大的那個是結(jié)果的長度（或者是結(jié)果長度-1）
for(int i=1;i<=lc;i++)
{
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]%=10;
}
if(c[lc+1]>0)lc++;//最高位仍然進位，所以長度++
for(int i=lc;i>=1;i--)//逆序輸出
cout<<c[i];
return 0;
}二、A-B problem
基本思路解析：
具體步驟:
1.字符串讀入
string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
cin>>x>>y;
la=x.length();
lb=y.length();?2.字符串轉(zhuǎn)數(shù)組
和之前一樣，因為減法是從個位開始的，所以我們讓字符串的最后一位存到數(shù)組的第一個去
for(int i=0;i<la;i++)
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)
{
b[lb-i]=y[i]-'0';
}3.豎式減法?
for(int i=1;i<=la;i++)
{
if(a[i]<b[i])//減數(shù)小了
{
a[i]+=10;//往前借位
a[i+1]-=1;//前一位減一
}
c[i]=a[i]-b[i];//照常計算
}4.倒序輸出
for(int i=la;i>=1;i--)
{
cout<<c[i];
}?代碼如下：
#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[100000],b[100000],c[100000],la,lb;
int main()
{
cin>>x>>y;
la=x.size();
lb=y.size();
if(la<lb||la==lb&&x<y)
{
swap(la,lb);
swap(x,y);
cout<<'-';
}
for(int i=0;i<la;i++)
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)
{
b[lb-i]=y[i]-'0';
}
for(int i=1;i<=la;i++)
{
if(a[i]<b[i])//減數(shù)小了
{
a[i]+=10;//往前借位
a[i+1]-=1;//前一位減一
}
c[i]=a[i]-b[i];//照常計算
}
for(int i=la;i>=1;i--)
{
cout<<c[i];
}
return 0;
}
?
?三、A*B problem
基本思路解析：
具體步驟（多一步去零）?
1.字符串讀入
string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
cin>>x>>y;
la=x.length();
lb=y.length();?2.字符串轉(zhuǎn)數(shù)組
和之前一樣，因為乘法也是從個位開始的，所以我們讓字符串的最后一位存到數(shù)組的第一個去
for(int i=0;i<la;i++)
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)
{
b[lb-i]=y[i]-'0';
}3.豎式乘法
for(int i=1;i<=la;i++)
{
for(int j=1;j<=lb;j++)
{
c[i+j-1]+=a[i]*b[j];//正常相除，c[i]中結(jié)果的位數(shù)可以通過觀察總結(jié)
c[i+j]+=c[i+j-1]/10;//向前進位
c[i+j-1]%=10;//進位剩下的
}
}4.去零
去零指在特殊情況中如003*25=0075需要去除結(jié)果需要去除結(jié)果中的零
lc=la+lb;//兩數(shù)相乘的最大位數(shù)
while(c[lc]==0&&lc>1)lc--; 5.倒序輸出
?
for(int i=la;i>=1;i--)
{
cout<<c[i];
}
?代碼如下：
#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[100000],b[100000],c[100000],la,lb,lc;
int main()
{
cin>>x>>y;
la=x.size();
lb=y.size();
for(int i=0;i<la;i++)
{
a[la-i]=x[i]-'0';
}
for(int i=0;i<lb;i++)
{
b[lb-i]=y[i]-'0';
}
for(int i=1;i<=la;i++)
{
for(int j=1;j<=lb;j++)
{
c[i+j-1]+=a[i]*b[j];//正常相除，c[i]中結(jié)果的位數(shù)可以通過觀察總結(jié)
c[i+j]+=c[i+j-1]/10;//向前進位
c[i+j-1]%=10;//進位剩下的
}
}
lc=la+lb;//兩數(shù)相乘的最大位數(shù)
while(c[lc]==0&&lc>1)lc--;
for(int i=lc;i>=1;i--)
{
cout<<c[i];
}
return 0;
}?四、A/B problem
基本思路解析：
?
具體步驟（多一步去零）?
1.字符串讀入
string a1;
long x=0,la,lc,a[100000],c[100000],b1;
int main()
{
cin>>a1>>b1;
la=a1.size();?2.字符串轉(zhuǎn)數(shù)組
和之前不同，因為除法是從最高位開始的，所以我們讓字符串的第一位存到數(shù)組的第一個去
for(int i=0;i<la;i++)
{
a[i]=a1[i-1]-'0';
}?3.除法
for(int i=1;i<=la;i++)
{
c[i]=(x*10+a[i])/b1;//除不盡的*10再加上下一位
x=(x*10+a[i])%b1;//除不盡剩下的
}
lc=1;4.去零
while(c[lc]==0&&la>lc)lc++;5.直接輸出
這里不用逆序
for(int i=lc;i<=la;i++)
{
cout<<c[i];
}?代碼如下：
#include <bits/stdc++.h>
using namespace std;
string a1;
long x=0,la,lc,a[100000],c[100000],b1;
int main()
{
cin>>a1>>b1;
la=a1.size();
for(int i=0;i<la;i++)
{
a[i]=a1[i-1]-'0';
}
for(int i=1;i<=la;i++)
{
c[i]=(x*10+a[i])/b1;//除不盡的*10再加上下一位
x=(x*10+a[i])%b1;//除不盡剩下的
}
lc=1;
while(c[lc]==0&&la>lc)lc++;
for(int i=lc;i<=la;i++)
{
cout<<c[i];
}
return 0;
}總結(jié)
①前面的字符串讀入和字符串轉(zhuǎn)換加減乘是一樣的
②去零操作存在于減乘除中
③注意+=和=的區(qū)別
④謝謝大家耐心看完，希望能幫助到您??！(#^.^#)文章來源：http://www.zghlxwxcb.cn/news/detail-816563.html
到了這里，關于【c++】算法：高精度（經(jīng)典加減乘除）{含解析（圖解）}的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
