PSJay Blog

#FIXME, seriously

C语言大整数相加

| Comments

今天无聊的时候做了一道自认为很简单的ACM题,却遇到了很多问题。题目如下:

Problem Description

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

Input

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

Output

For each test case, 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 int the equation. Output a blank line between two test cases.

Sample Input

2

1 2

112233445566778899 998877665544332211

Sample Output

Case 1:

1 + 2 = 3

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

简单说来,其实就是一个大整数相加问题,很容易想到用字符模拟手算这种方法。于是写出了如下代码:

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
71
72
73
74
75
76
77
78
79
80
81
******************************************
      大整数相加
      author:PSJay
      date:2010-07-16
******************************************/
#include "stdio.h"
#include "string.h" 

main() {
  char a[1001],b[1001],ta[1001],tb[1001],c[1001] = {'\0'};
  int n,k,temp,aLen,bLen,i,tpa,tpb,tp,tpt = 0;

  while(scanf("%d", n) != EOF) {
      for(k = 0;k < n;k++) {
          scanf("%s%s",a,b);
          aLen = strlen(a);
          bLen = strlen(b);

          strcpy(ta,a);
          strcpy(tb,b);

          //若b的位数比a大则相互交换
          if(bLen > aLen) {
              char tempStr[1001];
              strcpy(tempStr,a);
              strcpy(a,b);
              strcpy(b,tempStr);
              //更新变量
              aLen = strlen(a);
              bLen = strlen(b);
          }

          //位数对齐
          if(aLen > bLen) {
              int moreBit;
              moreBit = aLen - bLen;
              for(i = bLen ;i >= 0;i--) {
                  b[i + moreBit] = b[i];
              }
              //补前导零
              for(i = 0;i < moreBit;i++) {
                  b[i] = '0';
              }
          }

          //进行加法运算
          for(i = aLen - 1;i >= 0;i--) {
              tpa = a[i] - '0';
              tpb = b[i] - '0';

              tp = tpa + tpb + tpt;
              tpt = 0;

              if(tp > 9) {
                  tpt = (tp - tp % 10) / 10;
              }

              c[i] = (tp % 10) + '0';

              //进一位
              if(i == 0 && tp > 9) {
                  for(i = aLen;i >= 0;i--) {
                      c[i+1] = c[i];
                  }
                  c[0] = tpt + '0';

              }
          }

          //输出
          if(k+1 < n)
              printf("Case %d:\n%s + %s = %s\n\n",k+1,ta,tb,c);
          else
              printf("Case %d:\n%s + %s = %s\n",k+1,ta,tb,c);

          //清理
          memset(c,0,1001);
          tpt = 0;
      }
  }
}

由于忘了写77行和52行,导致了进位有问题,浪费了不少时间,并且因为没有看到“You may assume the length of each integer will not exceed 1000.”这句话,折腾了许久(开始给字符数组定义的长度是100)。另外,格式方面也浪费了很多时间(最后一个case的output居然不需要多空出一行)。值得一提的是,把数位多的大整数作为a是不必要的,只是因为开始写的时候是这样,因为无关紧要,所有后来也没有改了。

Comments