4

我用 C++ 编写了一个循环来给我 6 个随机数并将它们存储在一个数组中。我想做的是对数组的元素求和，直到我得到一个大于数字“x”的值，但我想这样做而不必添加所有元素。目标是找到总和为 x 值的第一个元素。

例如，数组是[1,2,3,4,5,6]，和x = 6，所以我要寻找的是元素[1,2,3]。

我查看了标准库并尝试使用“valarray”中的 sum 函数，但这只是给出了所有元素的总和。任何关于如何成功编码的想法将不胜感激。

4

9 回答 9

13

编写一个进行加法的函子。

#include <algorithm>
struct SumToo
{
     SumToo(int val):m_val(val),m_sum(0) {}
     int m_val;
     int m_sum;

     bool operator()(int next)
     {
         m_sum += next;
         return m_sum >= m_val;
     }
 };

 int main()
 {
       int data[] = {1,2,3,4,5,6};

       int* find = std::find_if(data,data+6,SumToo(6));
 }
于 2009-05-12T14:21:54.367 回答
8

我假设您只想要数组中的第一个 X 元素，直到它们的总和达到或超过阈值（那里的问题有点模糊）。

如果是这样，如果没有您自己的循环，我不知道该怎么做：

int sum = 0;
int i = 0;
for( ; i < len; ++i ) {
    sum += array[i];
    if( sum >= 6 ) {
        break;
    }
}

现在“i”包含总和达到或超过阈值的索引。

于 2009-05-12T14:18:24.483 回答
3

避免建议将 find_if 与有状态谓词一起使用的答案。有状态的谓词是危险的，因为 STL 算法假定复制谓词是安全的。在这种情况下，如果对谓词进行复制，则每个谓词将具有不同的“运行总计”，并且不一定对所有值或以正确的顺序起作用。

尤其要避免将其谓词的 operator() 成员实现为 const 成员函数但将其成员标记为可变的解决方案，因为这会让您误以为它不是有状态的谓词，这是不好的。

我建议使用简单循环查找答案的答案之一，或者使用累加器的答案，因为这是最正确的方法（即使代码看起来有点笨拙。

请注意，警告可能不适用于 C 数组和 find_if；我只是不希望您知道有状态谓词是解决问题的正确方法，因为您最终可能会在将来危险的情况下使用不正确的解决方案。

参考：C++ 编码标准：101 条规则、指南和最佳实践，第 87 条

于 2009-05-13T10:03:43.500 回答
2

从x中逐个减去数字，直到达到 0 或更低。

没有添加，如你所愿:)

于 2009-05-12T15:53:20.067 回答
2

这是一个更通用的版本：

#include <iostream>
#include <algorithm>

// return an iterator _Last such that sum 
// of all elements in the range [_First, _Last)
// satisfies the predicate Func
template<class InIt,
class Ty,
class Fn> inline
InIt accumulate_if(InIt First, InIt Last, Ty Val, Fn Func)
{   
    for (; Func(Val) && First != Last; ++First)
        Val = Val + *First;
    return (First);
}

int main() {
    int num[] = {1, 2, 3, 4, 5, 6};
    int *last = accumulate_if(num, num + sizeof num / sizeof num[ 0 ], 
                              0, std::bind2nd(std::less<int>(), 6));
    std::copy(num, last, std::ostream_iterator<int>(std::cout, "\n"));
    return 0;
}
于 2009-05-12T19:54:20.347 回答
0

好吧，我会使用矢量

T addUntil(T array[],size_t len,T thres){
    vector<T> vec = vector_from_array(array,len)
    T sum;
    for (size_t i=0;i< vec.size(),sum<thresh;i++){
          sum+= vec[i];
    }
    return sum;
}

T 需要定义 operator+ 和 operator<。

于 2009-05-12T14:21:03.200 回答
0

会是这样的：

struct StopAtValue{
  StopAtValue(int sum) : m_sum(sum), m_accumulated(0){}
  bool operator()(int val){
    m_accumulated += val;
    return m_accumulated >= sum;
  }
  int m_sum;
  int m_accumulated;
}


int* pos = std::find_if(&array[0], &array[n], StopAtValue(6));
于 2009-05-12T14:23:41.463 回答
0

希望这有效：

/* Returns an index i, given array valarray[0,1..n] and number x where i is an index to valarry such that sum over j of valarray[j] for j = 0 to i > x */
int getFirstSum(int *valarray, int n, int x)
{
   int i = 0;
   int sum = x;
   while(sum > x && i < n)
   {
      i++;
      sum -= valarray[i];
   }
   return i;
}
于 2009-05-13T09:53:16.247 回答
-1

您可以将 std::find_if() 与保持运行总数的函子一起使用，并且仅当您找到使您处于或超过顶部的元素时，才从函子返回 true。

例如：

#include <cstdlib>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

// functor returns true when the running total >= findVal
struct running_total : public unary_function<int, bool>
{
    running_total(int findVal) : findVal_(findVal), runningTtl_(0) {};
    bool operator()(int rhs) const
    {
        runningTtl_ += rhs;
        if( runningTtl_ >= findVal_ )
            return true;
        else
            return false;
    }
private:
    mutable int runningTtl_;
    const int findVal_;
};

int main()
{

    int nums[] = {1, 2, 3, 4, 5, 6};
    size_t count = sizeof(nums)/sizeof(nums[0]);

    const int scanTtl = 6;  // running total to scan to
    int * pos = find_if(&nums[0], &nums[0]+count, running_total(scanTtl));

    cout << "Elements Totaling " << scanTtl << " : ";
    copy(&nums[0], pos+1, ostream_iterator<int>(cout, ", "));

    return 0;
}
于 2009-05-12T14:29:39.780 回答