时间戳

首页 > 解决方案 > 整数溢出的奇怪行为

c++ - 整数溢出的奇怪行为

问题描述

我创建了以下代码来寻找硬币问题的答案。这涉及找到给定 k 面额的硬币的最小数量（其中每个这样的硬币都是无限供应的）以形成目标总和 n。特别是，我研究了k=5, denominations = {2,3,4,5,6}and target sum的情况n=100。

代码：

#include<iostream>
#include<algorithm>
using namespace std;

int coins[5] = {2,3,4,5,6};
int values[101];
int n=100;
int k=5;
int INF = INT_MAX;

int main()
{
    for (int x=1;x<=n;x++)
    {
        values[x] = INF;
        for (int j=1;j<=k;j++)
        {
            if (x-coins[j-1]>=0)
            {
                values[x] = min(values[x],values[x-coins[j-1]]+1);
            }
        }
    }
    cout<<values[100];

    return 0;
}

我收到的此代码的输出是-2147483632. 显然，必须发生某种溢出，所以我决定输出INF+1. 我得到INT_MIN了答案。但我也记得，在输出一些超出 int 范围的数字时，通常不会出现这样的问题。

我决定输出1e11，令我惊讶的是答案仍然是1e11. 为什么会出现这种情况，请帮忙。

标签： c++c++14integer-overflow

解决方案

这里：

 values[x] = min(values[x],values[x-coins[j-1]]+1);

例如，对于x=3and coins[0]=2，您添加values[1] + 1.

然而， values[1] = INT_MAX. 然后，在执行此计算时会出现未定义的行为。

你可以解决这个问题INF = INT_MAX - 1;

推荐阅读