题目
Given three integers A, B and C in [−263,263], you are supposed to tell whether A+B>C.
Input Specification:
The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
Output Specification:
For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).
Sample Input:
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0
Sample Output:
Case #1: false
Case #2: true
Case #3: false
变量溢出特性
由于不是科班出身,没学过计算机组成原理等等基础课,不了解变量存储机制。只能想到常规的大数运算的方法,也就是《算法笔记》中介绍的方法。
但是觉得这样一个题用那种方法总觉得挺麻烦,就去看了柳神的博客,发现是利用变量溢出的特性。于是去学习了一些计算机存储的相关知识——“原码、补码”。
异同点
他们都是把第一位作为符号位,0表示正,1表示负。
原码的数值位就是十进制数的二进制表示。
在计算机系统中,正整数的补码是其二进制表示,与原码相同;求负整数的补码,将其原码除符号位外的所有位取反(0变1,1变0,符号位为1不变)后加1。
目的
计算机数值一律用补码来存储,这么做是为了便于计算,因为原码的符号位会导致直接计算出错。如:-1(1000…001)+1(0000…001)= -2(1000…010),显然是错误的。
再看数据溢出
下图是以补码定义式为基础,沿数轴列出典型的真值、原码与补码表示。负数补码表示的范围比原码稍宽,多一种数码组合,是由于在补码表示中,数 0只有一种表示。因此,若n为整数,表示范围为(-2n~2n-1)。
这张图就解释了数据溢出的特性。比如int型,最大为231-1,其补码为0111…11,再加1就溢出,补码变成1000…00,表示-231。
回到本题
如果A > 0, B < 0 或者 A < 0, B > 0,A+B是不可能溢出的
如果A > 0, B > 0,sum可能会溢出,sum范围理应为(0, 264 – 2],溢出得到的结果应该是[-264, -2]是个负数,所以A+B < 0时候说明溢出了。
同理A<0, B<0时A+B>=0说明溢出。注意当A=B=−263时,A+B=0。
问题
写了如下代码但是有两个测试点不能通过。
#include<cstdio>
using namespace std;
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
long long a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
printf("Case #%d: ", i);
if (a > 0 && b > 0 && a+b < 0) printf("true\n");
else if (a < 0 && b < 0 && a+b >= 0) printf("false\n");
else printf("%s\n", a+b > c ? "true" : "false");
}
return 0;
}
然后看到别人的代码是另写了一个long long变量存储a+b,于是就AC了,但是不明白这是为什么…
#include<cstdio>
using namespace std;
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
long long a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
printf("Case #%d: ", i);
long long sum = a + b;
if (a > 0 && b > 0 && sum < 0) printf("true\n");
else if (a < 0 && b < 0 && sum >= 0) printf("false\n");
else printf("%s\n", sum > c ? "true" : "false");
}
return 0;
}
long double解法
但是也有博主认为上面的做法也不正确,因为题目给出的A,B,C的最大值已经超过了long long的范围,2^ 63是long long中无法正确解释的,被错误解释为-2^ 63。因此即使可以通过测试点,仍不是正确的做法。
例如输入:
0 9223372036854775808 1 会判断A + B < C;显然是不正确的。但可能由于测试数据并没有出现这样的数据,因此AC了。
可使用更大的long double类型存储,它有更高的精度和表示范围。
注: 输入输出时,使用格式字符%llf。
double和long double都是ANSI C标准的浮点数。但ANSI C并未规定long double的确切精度。所以对于不同平台可能有不同的实现。有的是8字节,有的是10字节,有的是12字节或更多。一般来说long double的精度要高于double, 至少相等,就像int和long int一样。但同一平台也可能不一样。
double类型的精度为15~16位,long double实际精度视编译环境或电脑系统而定。
所以这种解法可能不具有普适性。
#include <cstdio>
int main()
{
int n;
scanf("%d", &n);
for( int i = 1; i <= n; ++i )
{
long double A, B, C;
scanf("%llf %llf %llf", &A, &B, &C);
printf("Case #%d: %s\n", i, A + B > C ? "true":"false");
}
}
正在拼命学习的大学狗
发布了33 篇原创文章 · 获赞 5 · 访问量 2273
私信
关注