九度OJ-1198：a+b (高精度整数加法)

84 阅读 0 评论 56 点赞

我是靠谱客的博主奋斗水池，这篇文章主要介绍九度OJ-1198：a+b (高精度整数加法)，现在分享给大家，希望可以做个参考。

　　此题是高精度整数的第一题，可作为范版。　　

Debug记录：

　　这题debug了好半天，出现了两个问题：

　　①当sumInt中某个存储单元非4位数时，输出会不满4位，应当加上前导0。这个bug很快就找到了

　　②最恶心的问题出在加法函数中一种临界情况时对进位ｃ的处理上：当两个加数的size相等时，若首部单元相加产生进位，要做一个if判断来特殊处理，否则c则被遗漏，出错。这个找了整整一个小时才找出来

题目描述：

实现一个加法器，使其能够输出a+b的值。

输入：

输入包括两个数a和b，其中a和b的位数不超过1000位。

输出：

可能有多组测试数据，对于每组数据，
输出a+b的值。

样例输入：

复制代码

1
2
2 6
10000000000000000000 10000000000000000000000000000000

样例输出：

复制代码

1
2
8
10000000000010000000000000000000

来源：

2010年华中科技大学计算机研究生机试真题

答疑：

解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-7921-1-1.html

复制代码

#include <iostream> 
#include <cstring>
#include <iomanip>
using namespace std;

struct BigInteger{//1 int per 4digit 
	int digit[1000];
	int size;
		
	bool initInteger(){
		for (int i=0;i<1000;i++){
			digit[i]=0;
		}
		size=0;
		return true;
	}
	bool char2Integer(char a[]){
		int temp,weight;
		initInteger();
		for (int i=strlen(a)-1;i>=0;i-=4){
			temp=0;//initiate temp
			weight=1;//initiate weight
			for (int j=i;j>i-4&&j>=0;j--){
				temp+=(a[j]-'0')*weight;
				weight*=10;
			}
			digit[size]=temp;
			size++;
		}
		return true;
	}
	bool printInteger(){
		for (int i=size-1;i>=0;i--){
			cout<<setfill('0')<<setw((i==size-1?0:4))<<digit[i];
		}
		cout<<endl;
		return true;
	}
	bool add(BigInteger &aInt,BigInteger &bInt,BigInteger &sumInt){//a b sum are in different memoryspace from each other
		//initiate 
		sumInt.initInteger();
		int c=0;
		//cal
		for (int i=0;i<aInt.size||i<bInt.size;i++){
			sumInt.digit[i]=aInt.digit[i]+bInt.digit[i]+c;
			c=sumInt.digit[i]/10000;
			sumInt.digit[i]%=10000;
		}
		sumInt.size=aInt.size>bInt.size?aInt.size:bInt.size;
		if (c!=0){
			sumInt.digit[sumInt.size]=c;
			sumInt.size++;
		}
		return true;
	}
};
int main(){
	char a[1500],b[1500];
	BigInteger aInt,bInt,sumInt;
	while (cin>>a>>b){
		//initiate
		//char2Integer
		aInt.char2Integer(a);
		bInt.char2Integer(b);
		aInt.add(aInt,bInt,sumInt);
		//output	
		sumInt.printInteger();		
	}
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream> 
#include <cstring>
#include <iomanip>
using namespace std;

struct BigInteger{//1 int per 4digit 
	int digit[1000];
	int size;
		
	bool initInteger(){
		for (int i=0;i<1000;i++){
			digit[i]=0;
		}
		size=0;
		return true;
	}
	bool char2Integer(char a[]){
		int temp,weight;
		initInteger();
		for (int i=strlen(a)-1;i>=0;i-=4){
			temp=0;//initiate temp
			weight=1;//initiate weight
			for (int j=i;j>i-4&&j>=0;j--){
				temp+=(a[j]-'0')*weight;
				weight*=10;
			}
			digit[size]=temp;
			size++;
		}
		return true;
	}
	bool printInteger(){
		for (int i=size-1;i>=0;i--){
			cout<<setfill('0')<<setw((i==size-1?0:4))<<digit[i];
		}
		cout<<endl;
		return true;
	}
	bool add(BigInteger &aInt,BigInteger &bInt,BigInteger &sumInt){//a b sum are in different memoryspace from each other
		//initiate 
		sumInt.initInteger();
		int c=0;
		//cal
		for (int i=0;i<aInt.size||i<bInt.size;i++){
			sumInt.digit[i]=aInt.digit[i]+bInt.digit[i]+c;
			c=sumInt.digit[i]/10000;
			sumInt.digit[i]%=10000;
		}
		sumInt.size=aInt.size>bInt.size?aInt.size:bInt.size;
		if (c!=0){
			sumInt.digit[sumInt.size]=c;
			sumInt.size++;
		}
		return true;
	}
};
int main(){
	char a[1500],b[1500];
	BigInteger aInt,bInt,sumInt;
	while (cin>>a>>b){
		//initiate
		//char2Integer
		aInt.char2Integer(a);
		bInt.char2Integer(b);
		aInt.add(aInt,bInt,sumInt);
		//output	
		sumInt.printInteger();		
	}
	return true;
}