问题描述
我已经在SPOJ上进行了锻炼来练习高级算法.
I have done an exercise on SPOJ to practice advanced algorithms.
问题陈述如下:
这是我用来解决问题的代码:
This is the code I used to solve the problem:
#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如下:
I/O of the code is as follows:
约束:
Constraints:
但是，当我提交代码时，尽管我的代码在 Windows编译器(G ++ 14)和 Linux编译器中都能顺利运行，但我仍然收到消息.我尝试调试，但失败了.可能是什么问题? SIGABRT运行时错误(G ++ Clang 9)
But as I submitted my code, I received a message SIGABRT runtime error although my code ran smoothly in both Windows compiler (G++ 14) and Linux Compiler (G++ Clang 9). I have tried to debug but I failed. What might be wrong?
推荐答案
由于这是一个SPOJ问题，并且没有给出测试数据，因此您应该做的是将测试随机化，直到失败为止.这样，您可能可以获得失败的示例案例.这称为模糊化，并且是一种可以在您的问题中使用的技术.
Since this is a SPOJ question, and you're not given the test data, what you should do is to randomize the tests until you get a failure. That way, you may be able to get a sample case that fails. This is called fuzzing, and is a technique that can be used in your question.
以下内容适用于导致分段错误的情况，并且在某些情况下，可以验证给定输出是否与预期输出匹配.换句话说，与其尝试找出测试数据，不如让计算机为您生成测试.
The following will work for the cases that cause segmentation faults, and in some cases, to verify if a given output matches the expected output. In other words, instead of trying to figure out the test data, let the computer generate the tests for you.
执行此操作的方法是查看问题所给您的约束，并生成适合约束的随机数据.由于它们都是整数，因此可以使用< random> 标头并使用 uniform_int_distribution .
The way you do this is to look at the constraints that the question gives you, and generate random data that fits the constraints. Since they are all integers, you can do this by using the <random> header, and using a uniform_int_distribution.
以下是使用以下针对 N ， K 和价格数据的约束对数据进行模糊处理的示例:
Here is a sample of fuzzing the data using the following constraints for N, K, and the data for prices:
Constraints:
0 < N <= 100
0 < K <= 100
0 < price <= 1000
好的，因此，在获得此信息之后，我们可以获取您的准确代码，删除 cin 语句，并使用符合约束条件的随机数据替换所有内容.此外，如果我们使用 at()来访问导致问题的函数中的向量，则可以测试越界访问.
OK, so given this information, we can take your exact code, remove the cin statements, and replace everything with randomized data that fit the constraints. In addition, we can test for an out-of-bounds access if we use at() to access the vectors in the function that causes the issue.
鉴于所有这些信息，我们可以从更改 main 开始以生成适合问题约束的随机数据:
Given all of this information we can start with changing main to produce random data that fit the constraints of the question:
#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():
Given all of this, we can change the BuyingApple function by replacing [ ] with 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];
}
现在，我们有了一个自动案例生成器，它将捕获并显示可能导致引导程序出现问题的所有案例.注意，我们一直循环直到得到一个崩溃"的测试用例.然后，我们输出崩溃的案例，现在可以使用这些值来调试问题.
Now we have an automatic case generator, and will catch and display any cases that could cause an issue with the vectors. Note that we keep looping forever until we get a test case that "crashes". We then output the crashed case and can now use those values to debug the issue.
我们使用 std :: generate 和 std :: transform 来说明如何填充向量(或测试使用的任何序列容器)，以及如何专门进行测试(例如确保 Price 没有任何 0 值).另一个SPOJ问题可能需要其他专业知识，但希望您能掌握基本概念.
We used std::generate and std::transform as an illustration of how to populate a vector (or any sequence container your test uses), and how to specialize the test (like making sure that Price has no 0 values). Another SPOJ question may need other specializations, but hopefully you get the basic idea.
这是一个实时示例.
我们看到一个测试用例导致抛出 out-of-range 异常. main 函数具有一个 try/catch 来处理此错误，我们可以看到导致该问题的数据.
We see that a test case caused an out-of-range exception to be thrown. The main function has a try/catch to process this error, and we can see the data that caused the issue.
所以看来，如果我们的朋友多于苹果，那么问题出在我们越界的地方.我不会尝试解决此问题，但是您现在有一个测试案例，其中输入失败.
So it seems that if we have more friends than apples, the issue occurs where we go out-of-bounds. I will not attempt to fix the issue, but you now have a test case where the input fails.
通常，您可以将此技术与很多(如果不是大多数)在线判断"工具一起使用.网站，如果该网站没有显示失败的测试用例.
In general, you can use this technique with many, if not most of the "online judge" sites if the site doesn't show you failing test cases.
修改:更新了 std :: transform 中的lambda，以仅替换 Price 向量中的 0 .
Updated the lambda in the std::transform to only replace 0 in the Price vector.
这是一个随机的字符串模糊器，可以产生模糊的字符串数据.
您可以控制字符串的数量，每个字符串的最小和最大大小以及生成每个字符串时将使用的字母字母.
You can control the number of strings, the minimum and maximum size of each string, and the alphabet of characters that will be used when generating each string.
#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)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！