增强算法
增强算法
提问于 2017-05-07 17:17:34
我正在寻找一个算法来实现以下行为。如果当前和后续元素的求和小于或等于前一个元素，则将该和添加到新向量中。以下是一些例子：
例1：
original vector: 17 | 10 | 6 | 3 | 2
new vector: 17 | 16 | 5例2：
original vector: 41 | 15 | 10 | 5 | 2
new vector: 41 | 32例3：
original vector: 1 | 1 | 1 | 1 | 1
new vector: 1 | 1 | 1 | 1 | 1下面的代码可以工作，但可能会出现此代码失败的情况。我非常肯定，一个月后，我会忘记我自己代码的细节。我想使用可靠的代码。是否有标准的算法，也许在std或boost中做我提到的？
#include<vector>
#include<iostream>
void augmented_sort(const std::vector<double>& invec, std::vector<double>& outvec)
{
if (invec.empty()) return;
outvec.push_back(invec[0]);
auto augment = [&invec](double& current, double previous, int& ai)
{
if (ai >= invec.size()) return false;
int start = ai;
current = invec[ai];
int ri = 1;
while(true)
{
current += invec[start+ri];
std::cout << "previous = " << previous << std::endl;
std::cout << "current = " << current << std::endl;
if (current <= previous)
{
++ri;
ai += 2;
std::cout << "ri = " << ri << std::endl;
std::cout << "ai = " << ai << std::endl;
if (start+ri >= invec.size())
return true;
}
else if (ai == start)
return false;
else
{
current -= invec[start+ri];
return true;
}
}
};
int ai = 1; // absolute index. start from second element.
double current;
double previous = invec[ai-1];
while (ai < invec.size())
{
bool success = augment(current, previous, ai);
if (success)
{
outvec.push_back(current);
previous = current;
}
else
{
outvec.push_back(invec[ai]);
previous = invec[ai];
ai += 1;
}
}
}
int main ()
{
//std::vector<double> invec = {17, 10, 6, 3, 2};
//std::vector<double> invec = {41, 15, 10, 5, 2};
std::vector<double> invec = {1, 1, 1, 1, 1};
std::vector<double> outvec;
augmented_sort(invec, outvec);
for (double d: outvec)
std::cout << "d = " << d << std::endl;
return 0;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2017-05-07 19:32:25
我可能是错的，但你的问题似乎太利基，没有一个标准的算法。
但是，这里有一些简单得多的代码，它涉及在跟踪当前和的同时遍历输入向量一次，如果将当前元素添加到输出向量中会导致比最后添加的元素更大的和，则只将其放入输出向量中：
void augmented_sort(const std::vector<double>& input, std::vector<double>& output)
{
if (input.empty())
return;
output.push_back(input[0]);
int sum = 0;
for (int i = 1; i < input.size(); i++)
{
if (sum + input[i] > output.back())
{
output.push_back(sum);
sum = 0;
}
sum += input[i];
}
if (input.size() > 1)
output.push_back(sum);
}如果您希望它在降序向量之外的任何东西上工作，则需要进行一些更改(正如所述的那样，要求似乎将预期的行为留给这种不明确的行为)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43834423
复制相关文章
相似问题
腾讯云开发者
