在 SPOJ 上提交代码会出现运行时错误 (SIGABRT)

Question

我在 SPOJ 上做了一个练习来练习高级算法。

---

问题陈述如下：

Harish 去超市为他的 'n' 个朋友买了正好 'k' 公斤的苹果。超市真的很奇怪。物品的定价是非常不同的。他去了苹果区询问价格。推销员给了他一张卡片，他在卡片上发现苹果的价格不是每公斤。苹果被装在盖子里，每个包含“x”公斤苹果，x > 0，“x”是一个整数。“x”公斤包裹的价值为“y”卢比。因此，标语牌包含一个表，其中条目“y”表示“x”公斤包的价格。如果 'y' 是 -1，则表示相应的数据包不可用。现在由于苹果只能以包形式提供，他决定最多为他的“n”个朋友购买“n”包，即他不会购买超过 n 包的苹果。Harish 非常喜欢他的朋友，所以他不想让他的朋友失望。

---

这是我用来解决问题的代码：

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::vector;
using std::endl;

int MinValueOf(int a, int b)
{
    return (a < b) ? a : b;
}
int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
{
    vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
    for(int i = 1; i <= Friends; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            Table[i][j] = INT32_MAX;
            if(j == 0)
                Table[i][0] = 0;
            else if(PriceaTag[j] > 0)
                Table[i][j] = MinValueOf(Table[i][j], Table[i - 1][i - j] +  PriceaTag[j]);
        }
    }
    return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
}
int main()
{
    vector<int> Price;
    int Friends, Kilogram, t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        cin >> Friends >> Kilogram;
        vector<int> Price(Kilogram + 1, 0);
        for(int i = 1; i <= Kilogram; i++)
        {
            cin >> Price[i];
        }
        cout << BuyingApple(Price, Friends, Price.size() - 1) << endl;
    }
    return 0;
}

---

代码的I/O如下：

输入的第一行将包含测试用例的数量 C。每个测试用例将包含两行。第一行包含 N 和 K，他拥有的朋友数量以及他应该购买的苹果数量（公斤）。第二行包含 K 个空格分隔的整数，其中第 i 个整数指定“i”公斤苹果包的价格。值为 -1 表示相应的数据包不可用。

每个测试用例的输出应该是一行，其中包含他必须为朋友花费的最低金额。如果他不可能满足他的朋友，则打印 -1。

---

约束：

0 < N <= 100
0 < K <= 100
0 < 价格 <= 1000

---

但是，当我提出我的代码，我收到一个消息SIGABRT runtime error，虽然我的代码中都顺利跑Windows compiler (G++ 14)和Linux Compiler (G++ Clang 9)。我试图调试但我失败了。可能有什么问题？

Answer 1

由于这是一个 SPOJ 问题，并且您没有获得测试数据，因此您应该做的是随机化测试，直到失败为止。这样，您可能会得到一个失败的示例案例。这称为模糊测试，是一种可用于您的问题的技术。

以下将适用于导致分段错误的情况，并在某些情况下验证给定的输出是否与预期的输出匹配。换句话说，与其试图找出测试数据，不如让计算机为您生成测试。

你这样做的方法是查看问题给你的约束，并生成符合约束的随机数据。由于它们都是整数，因此您可以通过使用<random>标头和使用uniform_int_distribution.

下面是使用以下约束模糊化的数据的样本N，K以及用于价格数据：

Constraints:

0 < N <= 100
0 < K <= 100
0 < price <= 1000

好的，根据这些信息，我们可以获取您的确切代码，删除cin语句，并用符合约束的随机数据替换所有内容。此外，如果我们使用at()访问导致问题的函数中的向量，我们可以测试越界访问。

鉴于所有这些信息，我们可以开始更改main以生成符合问题约束的随机数据：

#include <random>
#include <algorithm>
//...
int main()
{
    // random number generator
    std::random_device rd;
    std::mt19937 gen(rd());

    // Prices will be distributed from -1 to 1000
    std::uniform_int_distribution<> distrib(-1, 1000);

    // N and K are distributed between 1 and 100  
    std::uniform_int_distribution<> distribNK(1, 100);

    // This one will be used if we need to replace 0 in the Price vector with 
    // a good value 
    std::uniform_int_distribution<> distribPos(1, 1000);

    // our variables
    int Friends;
    int Kilogram;
    vector<int> Price;

    // we will keep going until we see an out-of-range failure
    while (true)
    {
        try
        {
            // generate random N and K values
            Friends = distribNK(gen);
            Kilogram = distribNK(gen);

            // Set up the Price vector
            Price = std::vector<int>(Kilogram + 1, 0);

            // Generate all the prices
            std::generate(Price.begin() + 1, Price.end(), [&]() { return distrib(gen); });

            // Make sure we get rid of any 0 prices and replace them with a random value
            std::transform(Price.begin() + 1, Price.end(), Price.begin() + 1, [&](int n)
                { if (n == 0) return distribPos(gen);  return n; });

            // Now test the function
            std::cout << BuyingApple(Price, Friends, Price.size() - 1) << std::endl;
        }

        catch (std::out_of_range& rError)
        {
            std::cout << rError.what() << "\n";
            std::cout << "The following tests cause an issue:\n\n";
            // The following tests cause an issue with an out-of-range.  See the data
            std::cout << "Friends = " << Friends << "\nK = " << Kilogram << "\nPrice data:\n";
            int i = 0;
            for (auto p : Price)
            {
                std::cout << "[" << i << "]: " << p << "\n";
                ++i;
            }
            return 0;
        }
    }
}

鉴于所有这些，我们可以BuyingApple通过替换[ ]为at()：

int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
{
    vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
    for (int i = 1; i <= Friends; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            Table.at(i).at(j) = INT32_MAX;
            if (j == 0)
                Table[i][0] = 0;
            else if (PriceaTag[j] > 0)
                Table[i][j] = MinValueOf(Table[i][j], Table.at(i - 1).at(i - j) + PriceaTag.at(j));
        }
    }
    return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
}

现在我们有了一个自动案例生成器，它将捕获并显示任何可能导致向量出现问题的案例。请注意，我们会一直循环下去，直到我们得到一个“崩溃”的测试用例。然后我们输出崩溃的案例，现在可以使用这些值来调试问题。

我们使用std::generate和std::transform作为如何填充向量（或您的测试使用的任何序列容器）以及如何专门化测试（例如确保Price没有0值）的说明。另一个 SPOJ 问题可能需要其他专业化，但希望您了解基本概念。

这是一个实时示例。

我们看到一个测试用例导致out-of-range抛出异常。该main函数有一个try/catch处理此错误，我们可以看到，导致问题的数据。

所以看起来如果我们的朋友比苹果多，问题就会出现在我们越界的地方。我不会尝试解决这个问题，但您现在有一个输入失败的测试用例。

一般来说，如果站点没有向您显示失败的测试用例，您可以将此技术用于许多（如果不是大多数）“在线判断”站点。

编辑： 更新了 lambda 中的 lambdastd::transform以仅0在Price向量中替换。

编辑：这是一个随机字符串模糊器，可以生成模糊字符串数据。

您可以控制字符串的数量、每个字符串的最小和最大大小以及生成每个字符串时将使用的字符字母表。

#include <random>
#include <string>
#include <vector>
#include <iostream>

struct StringFuzzer
{ 
    unsigned int maxStrings;  // number of strings to produce
    unsigned int minSize;     // minimum size of a string
    unsigned int maxSize;     // maximum size of the string
    bool fixedSize;           // Use fixed size of strings or random
    std::string alphabet;     // string alphabet/dictionary to use
    
public:
    StringFuzzer() : maxStrings(10), minSize(0), maxSize(10), fixedSize(true), alphabet("abcdefghijklmnopqrstuvwxyz")
    {}
    StringFuzzer& setMaxStrings(unsigned int val) { maxStrings = val; return *this; };
    StringFuzzer& setMinSize(unsigned int val) { minSize = val; return *this; };
    StringFuzzer& setMaxSize(unsigned int val) { maxSize = val; return *this; };
    StringFuzzer& setAlphabet(const std::string& val) { alphabet = val; return *this; };
    StringFuzzer& setFixedSize(bool fixedsize) { fixedSize = fixedsize; return *this; }

    std::vector<std::string> getFuzzData() const
    {
        // random number generator
        std::random_device rd;
        std::mt19937 gen(rd());

        // Number of strings produced will be between 1 and maxStrings
        std::uniform_int_distribution<> distribStrings(1, maxStrings);

        // string size will be distributed between min and max sizes
        std::uniform_int_distribution<> distribMinMax(minSize, maxSize);

        // Picks letter from dictionary
        std::uniform_int_distribution<> distribPos(0, alphabet.size() - 1);

        std::vector<std::string> ret;

        // generate random number of strings
        unsigned int numStrings = maxStrings;
        if ( !fixedSize)
           numStrings = distribStrings(gen);
           
        ret.resize(numStrings);

        for (unsigned int i = 0; i < numStrings; ++i)
        {
            std::string& backStr = ret[i];
            // Generate size of string
            unsigned strSize = distribMinMax(gen);
            for (unsigned j = 0; j < strSize; ++j)
            {
                // generate each character and append to string
                unsigned pickVal = distribPos(gen);
                backStr += alphabet[pickVal];
            }
        }
        return ret;
    }
};

int main()
{
    StringFuzzer info;
    auto v = info.getFuzzData();  // produces a vector of strings, ready to be used in tests
    info.setAlphabet("ABCDEFG").setMinSize(1);  // alphabet consists only of these characters, and we will not have any empty strings
    v = info.getFuzzData();  // now should be a vector of random strings with "ABCDEFG" characters
    for (auto s : v)
       std::cout << s << "\n";
}