vector<int> getRow(int rowIndex) {
vector<int> result;
if(rowIndex < 0) return result;
if(rowIndex == 0){
result.push_back(1);
return result;
}
for(int i = 0; i < rowIndex+1; i++){
if(i == 0) result.push_back(1);
else{
result.push_back(result[i-1] * (rowIndex+1-i)/i);
}
}
return result;
}
int main()
{
vector<int> tmp = getRow(30);
for(int i = 0; i < tmp.size(); i++){
cout << tmp[i] << " ";
}
cout << endl;
return 0;
}
这是 LeetCode 的 Pascal 三角形编码问题,要求输出 Pascal 三角形的第 n 行。使用 rowIndex=30
,输出如下:
1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 -131213633 -123012780 -101304642 -73164463 -46209134 -25415023 -12102391 -4950978 -1722079 -502273 -120545 -23181 -3434 -367 -25 0
很明显,存在溢出问题。现在要解决这个问题,我将行 result.push_back(result[i-1] * (rowIndex+1-i)/i);
修改为 result.push_back((double)result [i-1] * (double)(rowIndex+1-i)/i);
.它会产生正确的输出:
1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 155117520 145422675 119759850 86493225 54627300 30045015 14307150 5852925 2035800 593775 142506 27405 4060 435 30 1
有人能解释一下这里到底是什么问题吗?
我们知道有符号整数值的范围是 -2147483648 到 2147483647。如果不进行转换,为什么值 155117520
会打印为溢出 -131213633
?
最佳答案
我的表达方式
result[i-1] * (rowIndex+1-i)/i
乘法先发生,结果溢出:
result[i-1] * (rowIndex + 1-i)
然后结果除以 i
,产生负输出。
顺便说一句,如果您决定转换,请避免转换为 double
,因为可能存在舍入问题。您可以尝试使用 long
,但一开始使用可能更好
vector<long>
甚至
vector<unsigned long>
或者,感谢 @WorldSEnder,
vector<unsigned long long>
不过,请注意该标准并不保证 long
或 long long
比 int
长。它也不保证 int
在 [-2147483648, 2147483647]
范围内。
关于c++ - 整数溢出问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31329453/