????????????????概念 ??????
????????在我們進(jìn)行計(jì)算的過(guò)程中，經(jīng)常會(huì)遇到幾十位，甚至幾百位的數(shù)字的計(jì)算問(wèn)題，也有可能會(huì)遇到小數(shù)點(diǎn)后幾十位，幾百位的情況，而我們面對(duì)這樣的情況下，?? 和 的數(shù)據(jù)范圍顯然是不夠使用的了。因此這時(shí)，我們就需要引入一個(gè)新的算法，叫做高精度算法 .
???????? 我們可以利用程序設(shè)計(jì)的方法去實(shí)現(xiàn)這樣的高精度計(jì)算 . 介紹常用的幾種高精度計(jì)算的方法 .
思想
????????高精度算法本質(zhì)上是用字符串模擬數(shù)字進(jìn)行計(jì)算，再利用類似于數(shù)學(xué)里的豎式的形式，一位一位進(jìn)行相關(guān)計(jì)算 .
處理
高精度計(jì)算中需要處理好以下幾個(gè)問(wèn)題：
1）數(shù)據(jù)的接收方法和存儲(chǔ)方法
??????? 數(shù)據(jù)的接收和存儲(chǔ)：當(dāng)輸入的數(shù)很長(zhǎng)時(shí)，可采用字符串方式輸入，這樣可輸入位數(shù)很長(zhǎng)的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位取出，存入數(shù)組中 .
void init(int a[]) { // 傳入數(shù)組
string s;
cin >> s;
len = s.length(); // s.length --> 計(jì)算字符串位數(shù)
for(int i=1; i<=len; i++)
a[i] = s[len -i] - '0'; //將字符串s轉(zhuǎn)換為數(shù)組a, 倒序存儲(chǔ)
}2）進(jìn)位、借位的處理.
// 加法進(jìn)位: c[i] = a[i] + b[i]
code: if(c[i] >= 10) {
c[i] %= 10;
++c[i++];
}
//減法借位: c[i] = a[i] - b[i]
code: if(a[i] < b[i]) {
--a[i+1];
a[i] += 10;
}
//乘法進(jìn)位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] % 10;高精度加法 +
????????輸入兩個(gè)數(shù)到變量中，然后用賦值語(yǔ)句求它們的和后輸出 . But，我們知道，在 C++ 語(yǔ)言中任何數(shù)據(jù)類型都有一定表示范圍. 當(dāng)兩個(gè)加數(shù)很大時(shí)，以前的算法顯然不能求出精確解，因此我們需要尋求另一種方法 .在讀小學(xué)時(shí)，我們做加法都采用豎式方法 . 這樣我們方便寫出兩個(gè)整數(shù)相加的算法 .
??????? 如果我們用數(shù)組分別儲(chǔ)存兩個(gè)加數(shù)，用數(shù)組 儲(chǔ)存結(jié)果。則上例有 :
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
char a1[5005], b1[5005]; //用字符存儲(chǔ)數(shù)字
int a[5005], b[5005], c[5005]; //c[i] 用來(lái)儲(chǔ)存每位相加的結(jié)果
int len_a, len_b, len_c = 1, x, i;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%s%s", a1, b1); //輸入兩個(gè)加數(shù)
len_a = strlen(a1);
len_b = strlen(b1);
for(i=0; i<len_a; i++) a[len_a - i] = a1[i] - '0'; // 將加數(shù)放進(jìn)a數(shù)組
for(i=0; i<len_b; i++) b[len_b - i] = b1[i] - '0'; // 將另一個(gè)加數(shù)放進(jìn)b數(shù)組
x = 0; // x為進(jìn)位
while(len_c <= len_a || len_c <= len_b) {
c[len_c] = a[len_c] + b[len_c] + x; // 兩數(shù)相加，再加上前兩個(gè)數(shù)進(jìn)位的
x = c[len_c] / 10; // 刷新進(jìn)位
c[len_c] %= 10; // 進(jìn)位后剩下的
len_c++; //位數(shù)加1
}
c[len_c] = x;
if(c[len_c] == 0) { //判斷首位是否為0
len_c--; // 不輸出此位
}
for(int i=len_c; i>=1; i--) {
printf("%d", c[i]); //輸出每一位的數(shù)
}
return 0;
}
高精度減法 -
??????? 類似加法，同樣使用豎式。在做減法運(yùn)算時(shí)，需要注意的是：需要有借位處理。
#include <iostream>
#include <cstring>
int main() {
int a[5005], b[5005], c[5005];
int lena, lenb, lenc, i;
char n[5005], n1[5005], n2[5005];
std::memset(a, 0, sizeof(a));
std::memset(b, 0, sizeof(b));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> n2; //輸入被減數(shù)和減數(shù)
lena = std::strlen(n1);
lenb = std::strlen(n2);
for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列
i = 1;
while(i <= lena || i <= lenb) {
if(a[i] < b[i]) {
c[i] = a[i] + 10 - b[i];
a[i+1]--; //借位處理
}
else {
c[i] = a[i] - b[i];
}
i++;
}
lenc = i;
while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0，是需要輸出的
lenc--; // 不輸出首位0
}
for(i=lenc; i>=1; i--) std::cout << c[i];
return 0;
}
高精度乘法 ×
??????? 類似加法，使用豎式。在做乘法時(shí)，同樣也有進(jìn)位。
??????? 分析 數(shù)組的下標(biāo)變化規(guī)律，可以寫出以下關(guān)系式:?????????
?????? 由此可見(jiàn)， 跟 乘積有關(guān)，跟上次的進(jìn)位有關(guān)，跟還原 的值有關(guān)，分析下標(biāo)規(guī)律，有 :
???????????????????????????????????????
#include <iostream>
#include <cstring>
int main() {
int a[105], b[105], c[10005];
char n1[105], n2[105], lena, lenb, lenc, j, i, x;
std::memset(a, 0, sizeof(a));
std::memset(b, 0, sizeof(b));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> n2;
lena = std::strlen(n1);
lenb = std::strlen(n2);
for(i=0; i<=lena-1; i++) a[lena - i] = n1[i] - 48;
for(i=0; i<=lenb-1; i++) b[lenb - i] = n2[i] - 48; // 倒序儲(chǔ)存
for(i=1; i<=lena; i++) {
x = 0;
for(j=1; j<=lenb; j++) {
c[i + j - 1] = c[i + j - 1] + x + a[i] * b[j];
x = c[i + j - 1] / 10; // 進(jìn)位
c[i + j - 1] %= 10; // 剩余
}
c[i + lenb] = x; // 進(jìn)位的數(shù)
}
lenc = lena + lenb;
while(c[lenc] == 0 && lenc > 1) {
lenc--; // 刪除前導(dǎo)0
}
for(i=lenc; i>=1; i--) {
std::cout << c[i];
} // 輸出每一位
std::cout << std::endl;
return 0;
} 除法 ÷
1）高精除以低精
??????? 做除法時(shí)，每一次的商值都在 0~9 之間，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時(shí)，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。當(dāng)然，為了程序簡(jiǎn)潔，可以避免高精度乘法，用 0~9 次循環(huán)減法取代得到商的值。采用按位相除法。
#include <iostream>
int main(){
char n1[100];
int a[100], c[100], lena, i, x = 0, lenc, b;
std::memset(a, 0, sizeof(a));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> b;
lena = strlen(n1);
for(i=1; i<=lena; i++) {
a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
}
//-------------------------初始化------------------------------
for(i=1; i<=lena; i++) {
c[i] = (a[i] + x * 10) / b; // 算上上一位剩下的繼續(xù)除
x = (a[i] + 10 * x) % b; // 求余
}
lenc = 1;
while(c[lenc] == 0 && lenc < lena) {
lenc++;
}
for(i=lenc; i<lena; i++) std::cout << c[i];
return 0;
}2）高精除以高精
??????? 高精除以低精是對(duì)被除數(shù)的每一位（這里的"一位"包含前面的余數(shù)，以下都是如此）都除以除數(shù)，而高精除以高精則使用減法模擬除法，對(duì)被除數(shù)的每一位都減去除數(shù)，一直減到當(dāng)前位置的數(shù)字（包含前面的余數(shù)）小于除數(shù)（由于每一位的數(shù)字小于10，所以對(duì)每一位最多進(jìn)行10次運(yùn)算），代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-409219.html
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int a[50005], b[50005], c[50005], d;
void init(int a[]) {
char s[50005];
cin >> s;
a[0] = strlen(s); // 字符串存儲(chǔ)，表示位數(shù)
for (int i=1; i<=a[0]; i++) {
a[i] = s[a[0]-i] - 48; // 正序儲(chǔ)存
}
}
void print(int a[]) {
if (a[0] == 0) {
cout << 0 << endl;
return; // 位數(shù)為0，輸出0
}
for (int i=a[0]; i>=1; i--) {
cout << a[i]; // 輸出函數(shù)
}
cout << endl;
return;
}
int compare(int a[], int b[]) {
if (a[0] > b[0]) {
return 1; // 被減數(shù)大于減數(shù)
}
if (a[0] < b[0]) {
return -1; // 被減數(shù)小于減數(shù)
}
for (int i=a[0]; i>=1; i--) {
if (a[i] > b[i]) {
return 1;
}
if (a[i] < b[i]) {
return -1;
} // 位數(shù)相同，找到第一位不同的進(jìn)行比較
}
return 0;
}
void numcpy(int p[], int q[], int det) {
for (int i=1; i<=p[0]; i++) {
q[i+det-1] = p[i]; //復(fù)制p數(shù)組到q數(shù)組從det開(kāi)始的地方
}
q[0] = p[0] + det - 1;
}
void jian(int a[], int b[]) {
int flag = compare(a, b);
if (flag == 0) {
a[0] = 0;
return;
}
if (flag == 1) {
for (int i=1; i<=a[0]; i++) {
if (a[i] < b[i]) {
a[i+1]--;
a[i] += 10;
}
a[i] -= b[i];
}
while (a[0]>0 && a[a[0]]==0) {
a[0]--;
}
return;
}
} // 高精減法
void chugao(int a[], int b[], int c[]) {
int tmp[50005];
c[0] = a[0] - b[0] + 1;
for (int i=c[0]; i>0; i--) {
memset(tmp, 0, sizeof(tmp));
numcpy(b, tmp, i);// 清零
while (compare(a, tmp) >= 0) {
c[i]++;
jian(a, tmp); // 用減法模擬
}
}
while (c[0] > 0 && c[c[0]] == 0) {
c[0]--;
}
return;
}
int main() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
init(a);
init(b);
chugao(a,b,c);
print(c);
return 0;
}如果這篇文章對(duì)你有幫助的話，請(qǐng)來(lái)個(gè)三連~~你們的支持是對(duì)我max（鼓 勵(lì)）??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-409219.html
到了這里，關(guān)于C++ 算法 高精度（較詳細(xì).）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
