1169：大整數減法

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 20463 ??? 通過數: 11820

【題目描述】

求兩個大的正整數相減的差。

【輸入】

共2行，第1行是被減數a，第2行是減數b(a > b)。每個大整數不超過200位，不會有多余的前導零。

【輸出】

一行，即所求的差。

【輸入樣例】

9999999999999999999999999999999999999 9999999999999

【輸出樣例】

9999999999999999999999990000000000000

【分析】

例如：123-89 運算過程：

? ? ? ? 從左到右計算的好處：（類似加法） 最高位退1位時，只需要往后面減去1位，假如依舊從右到左進行減法，那么最后需要減1位時需要把后面的數字都往前移一位，比較難以復雜和掌握。

? ? ? ? 大數減法基本思路： 1）將字符數組逆置賦給整型數組，并設狀態量決定輸出的字符串中是否需要加‘-’號；2）從左到右依次相減和退位 判斷最高位是否減1位，若是則數組長度減1；3）由狀態量判斷是否要在子串中加‘-’ 最后將整型數組逆置輸出。

【參考代碼】

C代碼：

#include <stdio.h>
#include <string.h>
#define N 10010

char s1[N],s2[N],tmp[N];
int a[N],b[N],c[N];

int main()
{
?? ?int i,lena,lenb;
?? ?
?? ?//讀入數據
?? ?scanf("%s %s",s1,s2);
?? ?
?? ?//判斷大小
?? ?lena=strlen(s1);
?? ?lenb=strlen(s2);
?? ?if(lena<lenb || lena==lenb && strcmp(s1,s2)<0)
?? ?{?? ?//減數小于被減數?
?? ??? ?printf("-");
?? ??? ?strcpy(tmp,s1);
?? ??? ?strcpy(s1,s2);
?? ??? ?strcpy(s2,tmp);
?? ??? ?lena=strlen(s1);
?? ??? ?lenb=strlen(s2);
?? ?}
?? ?
?? ?//倒序到數組里
?? ?for(i=0;i<lena;i++)
?? ?{
?? ??? ?a[i]=s1[lena-i-1]-'0';
?? ?}
?? ?for(i=0;i<lenb;i++)
?? ?{
?? ??? ?b[i]=s2[lenb-i-1]-'0';
?? ?}
?? ?
?? ?//模擬計算
?? ?for(i=0;i<lena;i++)
?? ?{
?? ??? ?if(a[i]<b[i])
?? ??? ?{
?? ??? ??? ?//借位
?? ??? ??? ?a[i+1]--;
?? ??? ??? ?a[i]+=10;?
?? ??? ?}
?? ??? ?c[i]=a[i]-b[i];
?? ?}
?? ?
?? ?//刪除前導零
?? ?for(i=lena-1;i>=0;i--)
?? ?{
?? ??? ?if(c[i]==0 && lena>1)
?? ??? ??? ?lena--;
?? ??? ?else
?? ??? ??? ?break;
?? ?}
?? ?
?? ?//輸出結果
?? ?for(i=lena-1;i>=0;i--)
?? ?{
?? ??? ?printf("%d",c[i]);
?? ?}
?? ?printf("\n");
?? ?
?? ?return 0;
}

C++代碼：

#include <iostream> #include <string> #include <vector>using namespace std;// C = A - B, 滿足A >= B, A >= 0, B >= 0 vector <int> sub(vector<int> &A, vector<int> &B) {vector <int> C;for(int i=0,t=0; i<A.size(); i++){t=A[i]-t;if(i<B.size())t-=B[i];C.push_back((t+10)%10);if(t<0)t=1;elset=0;}while(C.size()>1 && C.back()==0)C.pop_back();return C; }// 去除尾部的0 void trimZero(vector<int> &A) {while(A.back()==0 && A.size()>1)A.pop_back(); }int main() {bool flag=false;string a,b;vector <int> A,B;cin >> a >> b;for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');vector <int> C=sub(A, B);trimZero(C);for(int i=C.size()-1;i>=0;i--)cout << C[i];cout<<endl; return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1169

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1169：大整数减法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。