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

Question

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

问题陈述如下：

Harish went to a supermarket to buy exactly ‘k’ kilograms apples for his ‘n’ friends. The supermarket was really weird. The pricing of items was very different. He went to the Apples section and enquired about the prices. The salesman gave him a card in which he found that the prices of apples were not per kg. The apples were packed into covers, each containing ‘x’ kg of apples, x > 0 and ‘x’ is an integer. An ‘x’ kg packet would be valued at ‘y’ rupees. So, the placard contained a table with an entry ‘y’ denoting the price of an ‘x’ kg packet. If ‘y’ is -1 it means that the corresponding packet is not available. Now as apples are available only in packets, he decides to buy at most ‘n’ packets for his ‘n’ friends i.e he will not buy more than n packets of apples. Harish likes his friends a lot and so he does not want to disappoint his friends. So now, he will tell you how many friends he has and you have to tell him the minimum amount of money he has to spend for his friends.

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

#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的代码如下：

The first line of input will contain the number of test cases, C. Each test case will contain two lines. The first line containing N and K, the number of friends he has and the amount of Apples in kilograms which he should buy. The second line contains K space separated integers in which the ith integer specifies the price of a 'i' kg apple packet. A value of -1 denotes that the corresponding packet is unavailable.

The output for each test case should be a single line containing the minimum amount of money he has to spend for his friends. Print -1 if it is not possible for him to satisfy his friends.

限制条件：

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

但是当我提交我的代码时，我收到了一条消息 SIGABRT runtime error 尽管我的代码运行在 Windows compiler (G++ 14) 和 Linux Compiler (G++ Clang 9) 中都很顺利。我试过调试但失败了。可能出了什么问题？

Answer 1

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

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

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

来完成此操作

下面是使用以下约束对 N、K 和价格数据进行模糊测试的示例：

Constraints:

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

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

鉴于所有这些信息，我们可以开始更改 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;
        }
    }
}

鉴于所有这些，我们可以通过将 [ ] 替换为 at() 来更改 BuyingApple 函数：

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 问题可能需要其他专业知识，但希望您能掌握基本概念。

这是一个Live Example.

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

看来，如果我们的朋友多于苹果，问题就会出现在我们去的地方out-of-bounds。我不会尝试解决该问题，但您现在有一个输入失败的测试用例。

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

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

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

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

#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";
}

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

Code submission on SPOJ gives runtime error (SIGABRT)

c++

runtime-error

sigabrt