c++ - 在 SPOJ 上提交代码会导致运行时错误 (SIGABRT)

Question

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

---

问题陈述如下:

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 运行时错误，尽管我的代码在 Windows 编译器 (G++ 14) 和 Linux 编译器中都能顺利运行(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()，我们可以测试越界访问。访问导致问题的函数中的 vector 。

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

#include <random>
#include <algorithm>
#include <vector>
//...
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];
}

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

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

这里是 Live Example .

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

---

因此，如果我们的 friend 比苹果多，问题就会出现在我们越界的地方。我不会尝试解决此问题，但您现在有一个输入失败的测试用例。

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

编辑:更新了 std::transform 中的 lambda仅替换 0在 Price vector 。

---

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

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

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