Coursera自动评卷机给出了未知信号11

Question

我在上算法课，现在我们要学习贪婪的算法。我的两个解决方案在一些测试用例上输出了"Uknown Signal 11“。

然而，我用尽可能大的输入将我的程序驱动到了极限。它在我的电脑上运行得很好。然而，在Coursera的评分器上，它抛出了未知信号11的隐秘信息。

例如，如果我改用Python，这个问题会消失吗？

以下是显示该问题的第一个代码：

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

bool sortAlg(pair<double, pair<uint64_t,uint64_t>> item1, pair<double, 
pair<uint64_t,uint64_t>> item2)
{
return (item1.first >= item2.first);
}
int main()
{
uint64_t n, index = 0;
double W, val;
cin >> n >> W;
pair<double, pair<uint64_t,uint64_t>> items[n];
for (int i=0; i <n; i++)
{
    cin >> items[i].second.first >> items[i].second.second;
    items[i].first =  (double)items[i].second.first / (double)items[i].second.second;
}
sort(items,items+n, sortAlg);

while(W > 0 && n > 0)
{
    if (items[index].second.second <= W)
    {

        val += items[index].second.first;
        W -= items[index].second.second;
        index++;
        n--;
    }
    else
    {
        val += items[index].first * W;
        W = 0;
        index++;
        n--;
    }
}
printf("%.4f",val);
return 0;
}

我认为这与while循环有关，但我想不出程序会使用index进行越界数组调用。

无论如何，它是一个部分背包实现。

下面是第二个代码，它也给出了未知信号11：

#include <iostream>
#include <string>
#include<vector>
#include <algorithm>
#include <utility>
using namespace std;

bool sortAlg(string num1, string num2)
{
    if (num1[0] > num2[0]) return true;
    else if (num1[0] < num2[0]) return false;
    else
{
    if (num1.size() == 1 && (num1[0] > num2[1])) return true;
    else if (num1.size() == 1 && (num1[0] < num2[1])) return false;
    else if (num2.size() == 1 && (num1[1] > num2[0])) return true;
    else if (num2.size() == 1 && (num1[1] < num2[0])) return false;
    else if (num1 == "1000" || num2 == "1000") return (num1 < num2);
    else
    {
        if (num1.size() == num2.size()) return (num1 > num2);
        else
        {
            return (num1[1] > num2[1]);
        }
    }
}
}

int main()
{
string num;
int n, n2 = 1;
cin >> n;
//int numbers[n];
vector<string> numbers2;
for (int i =0; i <n; i++)
{
    num = to_string(n2);
    cout << num << endl;
    numbers2.push_back(num);
    n2 += 10;
}
sort(numbers2.begin(), numbers2.end(), sortAlg);

for (auto number : numbers2)
{
    cout << number;
}
return 0;
}

我怀疑排序函数中使用的sortAlg函数，但在我的PC上它相对较快。问题语句需要一些奇怪的排序。

问题被赋予了一组数字，安排它们使最大的数字成为可能。

例如，如果给定9，98，2，23，21，它应该给我99823221。(9 > 98 > 23 >2> 21)所以我按第一个数字排序，然后按下一个数字排序，依此类推。

Answer 1

您有一个StackOverflow错误。

必要的堆栈大小取决于递归的深度、递归函数的参数数量以及每个递归调用中的局部变量数量。

在Python中，您必须设置必要的堆栈大小。Python 3中提供的starter文件将包含以下示例：

import threading

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
...
threading.Thread(target=main).start()

注意stack_size是如何分配的。

Answer 2

这只是一个与Coursera grader相关的附加信息。在第6周的同一课程中，如果你为动态编程问题声明了一个二维数组，评分器会给出信号11错误，即使程序在本地机器上工作得很好，程序也会失败。

上面问题的解决方案-用2D向量替换2D数组(在C++的情况下)，然后再次提交。分级器将接受代码解决方案，并且不会抛出信号11错误。