HDU 1002 (高精度加法运算）

A + B ProblemII

Time Limit: 2000/1000 MS(Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 317773 Accepted Submission(s):61748

Problem Description

I have a verysimple problem for you. Given two integers A and B, your job is to calculatethe Sum of A + B.

Input

The first line ofthe input contains an integer T(1<=T<=20) which means the number of testcases. Then T lines follow, each line consists of two positive integers, A andB. Notice that the integers are very large, that
means you should not processthem by using 32-bit integer. You may assume the length of each integer willnot exceed 1000.

Output

For each testcase, you should output two lines. The first line is "Case #:", #means the number of the test case. The second line is the an equation "A +B = Sum", Sum means the result of A + B. Note there are some
spaces intthe equation. Output a blank line between two test cases.

Sample Input

1 2

112233445566778899998877665544332211

Sample Output

Case 1:

1 + 2 = 3

Case 2:

112233445566778899+ 998877665544332211 = 1111111111111111110

题意简述

首先输入一个数字T(1 <= T <= 20)代表输入的数据组数，其次下边有T行，每行有2个欲求和的数字，并且每个数字不超过1000位。

题意分析

这是一道高精度数字计算的题目，unsigned long long double 是不能满足所需要的数字位数的，所以需要别的方法进行计算。

解题思路

1. 首先用2个字符串接受并储存要输入的2个加数；

2. 去掉前导零；

3. 按照ASCII的关系，让字符串的每个字符减去字符0，获得数值并且倒置存储在2个数组中；

4. 模拟加法运算，并储存在另一个数组中；

5. 按要求输出结果；

6. 初始化各个数据；

测试数据补充

0001 1000

0 0

000 0000

9999 1

1 9999

99900 00999

00999 99900

当然还有大位数的极端数据，这些能过基本上就不会WA了。

代码总览

#include<stdio.h>

#include<string.h>

#define max(x,y)  ( x>y?x:y )

#define n 1010

int main()

{

	//freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

	char a1[n]={0};

	char b1[n]={0};

	int a2[n]={0}, b2[n]={0};

	int num ,n1,n2,j,digit,k,i,m1,m2;

	scanf("%d", &num);

	for(i = 1; i <=num; i++){

		//n1 = n2 = j = digit = k = m1 = m2 = 0;

		scanf("%s %s",a1,b1);

		n1 = strlen(a1);

		n2 = strlen(b1);

		for(j = 0 ; j < n1; j++){

			if(a1[j] != '0'&& a1[j] != NULL){

				m1 = j;

				break;

			}else if(a1[j] == '0' && j == n1-1){

				m1 = 0;

				n1 = 1;

				break;

			}

		}

		for(j = 0 ; j < n2; j++){

			if(b1[j] != '0' && b1[j] != NULL){

				m2 = j;

				break;

			}else if(b1[j] == '0' && j == n2-1){

				m2 = 0;

				n2 = 1;

				break;

			}

		}

		for(j = n1-1,k = 0;j >=m1 ;j--,k++){

			a2[k] = a1[j] - '0';

		}

		for(j = n2-1,k = 0;j >=m2 ;j--,k++){

			b2[k] = b1[j] - '0';

		}

		digit = max(n1-m1,n2-m2);

		int c2[n] = {0};

		for(j = 0; j < digit ; j++){

			c2[j] = a2[j] + b2[j] + c2[j];

			c2[j+1] = c2[j] / 10;

			c2[j] = c2[j] % 10;

		}

		if(c2[digit] == 0) digit--;

		printf("Case %d:\n",i);

		for(j = m1; j<n1;j++){

			printf("%c",a1[j]);

		}

		printf(" + ");

		for(j = m2; j<n2;j++){

			printf("%c",b1[j]);

		}

		printf(" = ");

		for(j = digit; j>= 0; j--) printf("%d",c2[j]);

		if(i != num) {

			printf("\n\n");

		}else{

			printf("\n");

		}

		for(j = 0; j<=digit; j++){

			a2[j] = b2[j] = 0;

		}

	}

	//fclose(stdin);

    //fclose(stdout);

	return 0;

}

重难点详解

1. 前导零的去除

for(j = 0 ; j< n1; j++){

if(a1[j]!= '0'&& a1[j] != NULL){

m1 =j;

break;

}elseif(a1[j] == '0' && j == n1-1){

m1 =0;

n1 =1;

break;

}

因为下一步要进行倒置处理，所以不妨从字符串的第一个字符开始遍历，遇到‘0’跳过，并使变量指向下一个字符，直到遍历到第一个不为零的字符，或者是遍历完整个字符串（说明全都是‘0’）。

如字符串0302，遍历到第一个字符‘0’m1 为0，第二个字符不为0，所以m1为1，那么倒置字符串从第1位也就是3开始，这样就过滤了前导零。

当然还有极端情况，就是0000…都为0的情况，这样当遍历完整个字符串后发现都是0，那么就规定m1为0，n1为1，进行下面的操作。

2. 倒置

for(j = n1-1,k = 0;j >=m1 ;j--,k++){

a2[k] =a1[j] - '0';

}

很简单，字符减去字符0储存在一个新的数组中，不过注意下标的关系。我这里是从字符串的最后一位开始取储存在数组的第一位中。

3. 模拟加法运算

digit =max(n1-m1,n2-m2);

int c2[n] = {0};

for(j = 0; j < digit ; j++){

c2[j] = a2[j] + b2[j] + c2[j];

c2[j+1] = c2[j] / 10;

c2[j] = c2[j] % 10;

}

Digit变量是两个数组中位数较大的一个，因为要进行足够次数的加法算。新令一个数组来储存同一位的数字之和。并让下一位等于本位除以10（模拟进位），本位取10的余数。

巴特西

HDU 1002 (高精度加法运算）

最新文章

热门文章