增強算法

Question

我正在尋找一種算法來實現以下行爲。如果當前元素和後續元素的總和小於或等於先前元素，則總和被添加到新矢量。下面是例子：

例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; 
} 

Answer 1

我可能是錯的，但是你的問題似乎有太小的標準算法。

但是，這裏有一些簡單的代碼，它涉及到在輸入向量上循環一次，同時跟蹤當前總和，並且只將其添加到輸出向量中，如果將當前元素添加到輸出向量將導致總和大於最後加入的元素：

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); 
} 

，如果你希望它在任何工作，但按降序排列向量這將需要一些改變（的要求，如前所述，似乎離開那個不清楚預期的行爲）。