UVa 465 Overflow

Overflow

Write a program that reads an expression consisting of two non-negative integer and an operator. Determine if either integer or the result of the expression is too large to be represented as a ``normal'' signed integer (type integer if you are working Pascal, type int if you are working in C).

Input

An unspecified number of lines. Each line will contain an integer, one of the two operators + or *, and another integer.

Output

For each line of input, print the input followed by 0-3 lines containing as many of these three messages as are appropriate: ``first number too big'', ``second number too big'', ``result too big''.

Sample Input

300 + 3
9999999999999999999999 + 11

Sample Output

300 + 3
9999999999999999999999 + 11
first number too big
result too big

一道大数加法和乘法问题，给定一个算式，判断所给的两个数以及计算结果是否溢出了int的范围

WA了三次吧，第一次是乘法写错了，第二次以忘了删freopen……第三次是个坑，当两个数算乘法时，不能由一个乘数溢出而直接判断结果出是溢出的，因为另一个乘数可能是0

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 bool Judge(int length,int x[])
  9 {
 10     if(length>10)
 11         return true;
 12     if(length<10)
 13         return false;
 14     if(x[9]>2)
 15         return true;
 16     if(x[9]<2)
 17         return false;
 18     //2147483647
 19     if(x[8]>1)
 20         return true;
 21     if(x[8]<1)
 22         return false;
 23     if(x[7]>4)
 24         return true;
 25     if(x[7]<4)
 26         return false;
 27     if(x[6]>7)
 28         return true;
 29     if(x[6]<7)
 30         return false;
 31     if(x[5]>4)
 32         return true;
 33     if(x[5]<4)
 34         return false;
 35     if(x[4]>8)
 36         return true;
 37     if(x[4]<8)
 38         return false;
 39     if(x[3]>3)
 40         return true;
 41     if(x[3]<3)
 42         return false;
 43     if(x[2]>6)
 44         return true;
 45     if(x[2]<6)
 46         return false;
 47     if(x[1]>4)
 48         return true;
 49     if(x[1]<4)
 50         return false;
 51     if(x[0]>7)
 52         return true;
 53     return false;
 54 }
 55 
 56 int main()
 57 {
 58     char stringInput[10000];
 59     int a[100000],b[100000],c[100000];
 60     while(gets(stringInput))
 61     {
 62         int operatorPos;
 63         for(operatorPos=0;stringInput[operatorPos]!='+'&&stringInput[operatorPos]!='*';operatorPos++);
 64         int a_length=0,b_length=0;
 65         bool a_overflow=false,b_overflow=false,res_overflow=false;
 66         memset(a,0,sizeof(a));
 67         memset(b,0,sizeof(b));
 68         memset(c,0,sizeof(c));
 69         for(int i=operatorPos-1;i>=0;i--)
 70         {
 71             if(stringInput[i]>='0'&&stringInput[i]<='9')
 72                 a[a_length++]=stringInput[i]-'0';
 73         }
 74         for(;a[a_length-1]==0;a_length--);
 75         for(int i=strlen(stringInput)-1;i>operatorPos;i--)
 76         {
 77             if(stringInput[i]>='0'&&stringInput[i]<='9')
 78                 b[b_length++]=stringInput[i]-'0';
 79         }
 80         for(;b[b_length-1]==0;b_length--);
 81         a_overflow=Judge(a_length,a);
 82         b_overflow=Judge(b_length,b);
 83         if(stringInput[operatorPos]=='+')
 84         {
 85             int max_length=max(a_length,b_length);
 86             int up=0;
 87             for(int i=0;i<max_length+10;i++)
 88             {
 89                 c[i]=(a[i]+b[i]+up)%10;
 90                 up=(a[i]+b[i]+up)/10;
 91             }
 92 
 93         }
 94         else if(stringInput[operatorPos]=='*')
 95         {
 96             for(int i=0;i<b_length;i++)
 97             {
 98                 int up=0;
 99                 for(int j=0;j<=a_length||(c[j]!=0||up!=0);j++)
100                 {
101                     int tmp=c[i+j];
102                     c[i+j]=(a[j]*b[i]+up+c[i+j])%10;
103                     up=(a[j]*b[i]+up+tmp)/10;
104                 }
105             }
106         }
107         int c_length;
108         for(c_length=99999;c[c_length-1]==0;c_length--);
109         res_overflow=Judge(c_length,c);
110 
111         puts(stringInput);
112         if(a_overflow)
113             puts("first number too big");
114         if(b_overflow)
115             puts("second number too big");
116         if(res_overflow)
117             puts("result too big");
118     }
119 
120     return 0;
121 }

[C++]

后来网上看到了另一种思路，这个题可以直接把字符串转成double类型后直接算比较大小，不用大数加法乘法……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 
 6 #define MAX 2147483647
 7 
 8 using namespace std;
 9 
10 double trans(int length,int x[])
11 {
12     double res=0,ten=1;
13     for(int i=0;i<length;i++)
14     {
15         res+=x[i]*ten;
16         ten*=10;
17     }
18     return res;
19 }
20 
21 int main()
22 {
23     char stringInput[10000];
24     int a[100000],b[100000];
25 
26     while(gets(stringInput))
27     {
28         int operatorPos;
29         for(operatorPos=0;stringInput[operatorPos]!='+'&&stringInput[operatorPos]!='*';operatorPos++);
30         int a_length=0,b_length=0;
31         memset(a,0,sizeof(a));
32         memset(b,0,sizeof(b));
33         for(int i=operatorPos-1;i>=0;i--)
34         {
35             if(stringInput[i]>='0'&&stringInput[i]<='9')
36                 a[a_length++]=stringInput[i]-'0';
37         }
38         for(;a[a_length-1]==0;a_length--);
39         for(int i=strlen(stringInput)-1;i>operatorPos;i--)
40         {
41             if(stringInput[i]>='0'&&stringInput[i]<='9')
42                 b[b_length++]=stringInput[i]-'0';
43         }
44         for(;b[b_length-1]==0;b_length--);
45         double a_double=trans(a_length,a);
46         double b_double=trans(b_length,b);
47         double res_double;
48         if(stringInput[operatorPos]=='+')
49             res_double=a_double+b_double;
50         else
51             res_double=a_double*b_double;
52 
53         puts(stringInput);
54         if(a_double>MAX)
55             puts("first number too big");
56         if(b_double>MAX)
57             puts("second number too big");
58         if(res_double>MAX)
59             puts("result too big");
60     }
61 
62     return 0;
63 }

[C++]