1.導論
當我們利用計算機進行數(shù)值計算，有時候會遇到這樣的問題： n！的精確結(jié)果是多少？
當n小于30的時候，我們當然可以通過電腦自帶的計算器計算出來。但是當我們遇到 100! 的時候就沒有辦法直接計算出精確的結(jié)果。再比如，求兩個20000位的數(shù)的和。
那怎么解決精度缺失的問題？
高精度算法（High Accuracy Algorithm） 是處理大數(shù)字的數(shù)學計算方法。
- 在一般的科學計算中，會經(jīng)常算到小數(shù)點后幾百位或者更多，當然也可能是幾千億幾百億的大數(shù)字。一般這類數(shù)字我們統(tǒng)稱為高精度數(shù)，高精度算法是用計算機對于超大數(shù)據(jù)的一種模擬加，減，乘，除，乘方，階乘，開方等運算。對于非常龐大的數(shù)字無法在計算機中正常存儲。
- 于是，將這個數(shù)字拆開，拆成一位一位的，或者是四位四位的存儲到一個數(shù)組中， 用一個數(shù)組去表示一個數(shù)字，這樣這個數(shù)字就被稱為是高精度數(shù)。
- 高精度算法就是能處理高精度數(shù)各種運算的算法，但又因其特殊性，故從普通數(shù)的算法中分離，自成一家。
- 高精度處理，實際上就是模擬法，模擬手算，它的原理與我們用豎式計算時一樣的，不過在處理過程中要注意高精度數(shù)據(jù)的讀入、轉(zhuǎn)換儲存、數(shù)據(jù)的計算、結(jié)果位數(shù)的計算、輸出等幾個問題。
2.高精度+低精度
有一個很大的數(shù)，例如 99999999999999999；一個小的數(shù)6666。如何把這兩個數(shù)加起來呢？
高精度的加法思想
-
把大數(shù)存到字符串;
-
字符串的每個字符數(shù)字都通過ASCII轉(zhuǎn)換存到數(shù)組,
注意的是要低位存在數(shù)組開頭:a[i] = s[len-i-1]-‘0’; -
加法進位的算式:
① a[i+1] += a[i]/10;
② a[i] %= 10; -
數(shù)字溢出，長度+1;
-
反向輸出結(jié)果;
來看下我們怎么做的，以C++語言編程為例子。
#include<iostream>
#include<string>
using namespace std;
string s1;
int a[1000],b;
int main(){
cin>>s1>>b; // 1.輸入數(shù)值
代碼中，s1數(shù)組存的是大數(shù)，b整數(shù)存小數(shù)。
① 1234 + 66
② 123456 + 99
按照數(shù)學加法運算，是先個位數(shù)與個位數(shù)相加，也就是
① s1[3] + 6
② s1[5] + 9
由上面可知，個位數(shù)+個位數(shù)的索引下標不一致，會增加編程難度。那可以考慮把數(shù)組倒序存儲！個位數(shù)放到數(shù)組開頭位置也就是s1[0]，那無論數(shù)值多大，數(shù)組下標都是s1[0] 開始進行加法的。
// s1存到數(shù)組a里面，記得轉(zhuǎn)為整數(shù)
int len1 = s1.size(); //獲取長度
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
因為s1是字符串要通過ASCII碼表轉(zhuǎn)成整數(shù)，所以要減掉 -‘0’。
好，上面我們已經(jīng)完成把大數(shù)存到數(shù)組里了，接著要進行加法運算。
- 把小數(shù)先加到a[0]位置:
a[0] +=b;例如 1234 + 89 =》a[0] = 1323; - 接著把新的個位數(shù)留在a[0]，其他位數(shù)進行 進位操作。
a[0+1] += a[0] /10; // a[1] = 3+132 = 135
a[0] = a[0] % 10; // a[0] = 3
- 以此類推，更新十位數(shù)，其他位數(shù)進位操作。
//3.進行加法運算。
a[0]+=b; // 5+9999 10004
//4.進位操作
for(int i=0;i<len1;i++){
a[i+1] += a[i] / 10;
a[i] = a[i] % 10;
}
加法運算后，要考慮到數(shù)子溢出的情況； 例如 999 +11 == 1010 多出來了千位數(shù)。解決這個問題簡單，判斷最高位是否不為0，滿足條件就再一次進行進位操作！
//5.考慮到數(shù)字溢出
while(a[len1]){
a[len1+1] += a[len1]/10;
a[len1] %= 10;
len1++;
}
最后輸出結(jié)果，記得要反向，因為前面我們a[0] 是最低位，輸出從左到右是高位到低位的。
//6.反向輸出
for(int i=len1-1;i>=0;i--){
cout<<a[i];
}
高精度+低精度完整代碼如下：
#include<iostream>
#include<string>
using namespace std;
string s1;
int a[1000],b;
int main(){
cin>>s1>>b;
// s1存到數(shù)組a里面，記得轉(zhuǎn)為整數(shù)
int len1 = s1.size();
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
//3.進行加法運算。
a[0]+=b; // 5+9999 10004
//4.進位操作
for(int i=0;i<len1;i++){
a[i+1] += a[i] / 10;
a[i] = a[i] % 10;
}
//5.考慮到數(shù)字溢出
if(a[len]){
len++;
}
//6.反向輸出
for(int i=len1-1;i>=0;i--){
cout<<a[i];
}
}
3.高精度+高精度
跟上面步驟相似。
高精度的加法思想：
- 把大數(shù)存到字符串;
- 字符串的每個字符數(shù)字都通過ASCII轉(zhuǎn)換存到數(shù)組,
注意的是要低位存在數(shù)組開頭:a[i] = s[len-i-1]-‘0’; - 獲取最大的數(shù)長度:max(len1,len2) ;
- 加法進位的算式:
① a[i+1] += a[i]/10;
② a[i] %= 10; - 數(shù)字溢出，長度+1;
- 反向輸出結(jié)果;
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[100001];
int main(){
// 1.輸入值，長度
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
// 2.把字符轉(zhuǎn)為整數(shù)存到數(shù)組
// 注意要個位存到數(shù)組開頭
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
兩個大數(shù)都要存到字符串，再轉(zhuǎn)為整數(shù)。然后按照位數(shù)，數(shù)組下標依次相加，也就是a[i]+b[i]。加到什么時候停止是由長度最大的數(shù)決定的，所以我們要求最大的數(shù)長度，再進行加法。
// 3.獲取最大的數(shù)。
int len = max(len1,len2);
// 對各個位數(shù)進行相加并把最新的值存到輸出C里面。
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
通過c[i] = a[i]+b[i]; 可能會出現(xiàn)例如 c[0] = 11，大于10的情況，需要進位！
//4.進位
for(int i=0;i<len;i++){
c[i+1] += c[i]/10;
c[i] %= 10;
}
還是一樣的，進位后考慮到溢出問題，然后反向輸出
//6.考慮到數(shù)字溢出
if(a[len]){
len++;
}
//7.反向輸出
for(int i=len-1;i>=0;i--){
cout<<a[i];
}
高精度+高精度完整代碼：
/*
高精度的加法思想
1.把大數(shù)存到字符串;
2.字符串的每個字符數(shù)字都通過ASCII轉(zhuǎn)換存到數(shù)組,
注意的是要低位存在數(shù)組開頭:a[i] = s[len-i-1]-'0';
3.獲取最大的數(shù)長度:max(len1,len2) ;
4.把a,b值加入到c數(shù)組： c[i] = a[i]+b[i];
5.c數(shù)組加法進位的算式:
① c[i+1] += c[i]/10;
② c[i] %= 10;
6.數(shù)字溢出，長度+1;
7.反向輸出結(jié)果;
*/
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[100001];
int main(){
// 1.輸入值，長度
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
// 2.把字符轉(zhuǎn)為整數(shù)存到數(shù)組
// 注意要個位存到數(shù)組開頭
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
// 3.獲取最大的數(shù)。
int len = max(len1,len2);
// 對各個位數(shù)進行相加
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
//4.進位
for(int i=0;i<len;i++){
c[i+1] += c[i]/10;
c[i] %= 10;
}
//5.溢出
while(c[len]==0 && len>0){
len--;
}
if(c[len]>0){
len++;
}
//6.反向輸出
for(int i=len-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
4.高精度減法
減法是這樣要求的，當兩數(shù)相減<0，要輸出帶負 ‘-’ 號！
高精度減法的思想：
-
輸入兩個大數(shù);
-
判斷大小，固定s1恒大于s2:
-
獲取長度;
-
字符變整數(shù)：a[i] = s1[len1-i-1]-‘0’;
-
減法運算:
① if(a[i]<b[i]){
a[i+1]–; //上位–
a[i]+=10; // 本位+10
}
② c[i] = a[i]-b[i]; -
去除前導零;
-
反向輸出;
看下，輸入值，輸入第一個代表減數(shù)，第二個代表被減數(shù)；我們知道減法是會有負數(shù)情況的，所以要考慮到減數(shù)<被減數(shù)情況。也就是 減數(shù)長度 < 被減數(shù)長度 或者 長度相等情況 減數(shù)值 < 被減數(shù)值。那我們就輸出 ‘-’ 號，和交換兩個的值。永久實現(xiàn)減數(shù) 恒大于 被減數(shù)！??！
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[10000];
int main(){
// 1.輸入值
cin>>s1>>s2;
// 2.判斷大小,固定s1恒大于s2
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交換值
cout<<"-";
}
// 3.獲取長度
int len1 = s1.size();
int len2 = s2.size();
// 4.字符變整數(shù)
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
轉(zhuǎn)為整數(shù)存到數(shù)組里面后，進行減法運算，根據(jù)減法規(guī)則，不夠減的要借位+10，被借位的要減1。例如 1234 - 66。 如果 a[0] - b[0] < 0，就要借位+10，也就是 a[0] + 10 后再減 b[0]；然后被借位 a[0+1]–；
//5.減法運算
for(int i=0;i<len1;i++){
if(a[i]<b[i]){
a[i+1]--; //被借位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i]; //相減結(jié)果存到數(shù)組c
}
要注意的是：123 -120 = 003，前面的零要消除掉。然后再反向輸出。
//6.去除前導零
while(c[len1-1]==0 && len1>1){
len1--;
}
//7.反向輸出
for(int i=len1-1;i>=0;i--){
cout<<c[i];
}
高精度減法完整代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-599102.html
/*
高精度減法的思想
1.輸入大數(shù);
2.判斷大小,固定s1恒大于s2:
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交換值
cout<<"-";
}
3.獲取長度;
4.字符變整數(shù)：a[i] = s1[len1-i-1]-'0';
5.減法運算:
if(a[i]<b[i]){
a[i+1]--; //上位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i];
6.去除前導零;
while(c[len1-1]==0 && len1>1){
len1--;
}
7.反向輸出;
*/
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[10000];
int main(){
// 1.輸入值
cin>>s1>>s2;
// 2.判斷大小,固定s1恒大于s2
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交換值
cout<<"-";
}
// 3.獲取長度
int len1 = s1.size();
int len2 = s2.size();
// 4.字符變整數(shù)
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
//5.減法運算
for(int i=0;i<len1;i++){
if(a[i]<b[i]){
a[i+1]--; //上位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i];
}
//6去除前導零
while(c[len1-1]==0 && len1>1){
len1--;
}
//7.反向輸出
for(int i=len1-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-599102.html
到了這里，關(guān)于C++基礎(chǔ)算法①——高精度加減法計算的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
