高精度減法
簡介
用于計算含有超過一般變量存放不下的非負(fù)整數(shù)
高精度加法這個過程是模擬的小學(xué)豎式減法計算
注：在本文中，我們默認(rèn)輸入的第一個數(shù)為被減數(shù)抢呆，且被減數(shù)大于減數(shù)
原理基本上與高精度加法相同浓恳，僅在核心代碼處有些區(qū)別才写，因此本文較為簡略，建議先閱讀文章《高精度加法(C++實現(xiàn))》
主要步驟
- 清零
- 逆置
- 轉(zhuǎn)換
- 相減計算（包含退位）
代碼實現(xiàn)
逆置
因為數(shù)組存放的元素順序與我們計算的順序是相反的奖蔓，在豎式計算中我們是將其右對齊（個位對個位，十位對十位讹堤，以此類推）吆鹤，而讀取數(shù)字后的兩個數(shù)組是左對齊的，因此我們要將里面的元素逆置
//參數(shù)：需要逆置的數(shù)組洲守，數(shù)組長度
void invertElem(char s[], size_t n)
{
size_t len = n-1;
for(size_t i=0,j=len;i<j;i++,j--)
{
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
轉(zhuǎn)換
為了方便計算和進(jìn)位疑务，我們需要將字符型的數(shù)字轉(zhuǎn)化成實際數(shù)字
注意：這里的轉(zhuǎn)換不是類型轉(zhuǎn)換，例如字符類型8梗醇，我們要讓它自減48知允，轉(zhuǎn)化成ASCII碼為8的對應(yīng)的字符，存放元素的數(shù)組的類型并沒有改變
轉(zhuǎn)換必須在逆置之后叙谨。如果轉(zhuǎn)換在前逆置在后温鸽，則逆置時分不清末尾的0是數(shù)字的一部分還是結(jié)束符轉(zhuǎn)換后的數(shù)字
//參數(shù)：數(shù)組，長度
void charInt(char s[], size_t n)
{
for(size_t i=0; i<n; i++)
s[i]-=48;
}
相減
int main()
{
while(1)
{
char a[1024];
char b[1024];
char c[2049];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
if(scanf("%s%s",a,b)==EOF) break;
size_t len_a = strlen(a);
size_t len_b = strlen(b);
size_t max_len = len_a>len_b?len_a:len_b;
invertElem(a,len_a);
invertElem(b,len_b);
charInt(a,len_a);
charInt(b,len_b);
//這部分是高精度減法的核心
int carry = 0;
for(size_t i=0; i<=max_len; i++)
{
c[i] = (a[i]-carry<b[i])?(10+a[i]-carry-b[i]):(a[i]-carry-b[i]);
carry = (a[i]-carry<b[i])?1:0;
}
int i;
for(i=max_len; i>=1&&c[i]==0; i--);
for(; i>=0; i--)
printf("%d", c[i]);
printf("\n");
}
return 0;
}
完整代碼
#include <bits/stdc++.h>
using namespace std;
//逆置
void invertElem(char s[], size_t n)
{
size_t len = n-1;
for(size_t i=0,j=len;i<j;i++,j--)
{
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
//轉(zhuǎn)換
void charInt(char s[], size_t n)
{
for(size_t i=0; i<n; i++)
s[i]-=48;
}
int main()
{
while(1)
{
char a[1024];
char b[1024];
char c[2049];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
if(scanf("%s%s",a,b)==EOF) break;
size_t len_a = strlen(a);
size_t len_b = strlen(b);
size_t max_len = len_a>len_b?len_a:len_b;
invertElem(a,len_a);
invertElem(b,len_b);
charInt(a,len_a);
charInt(b,len_b);
//這部分是高精度減法的核心
int carry = 0;
for(size_t i=0; i<=max_len; i++)
{
c[i] = (a[i]-carry<b[i])?(10+a[i]-carry-b[i]):(a[i]-carry-b[i]);
carry = (a[i]-carry<b[i])?1:0;
}
int i;
for(i=max_len; i>=1&&c[i]==0; i--);
for(; i>=0; i--)
printf("%d", c[i]);
printf("\n");
}
return 0;
}
