根据最小总和查找数组的元素

I've written a loop in C++ to give me 6 random numbers and store them in an array. What I would like to do is to sum the elements of the array until I get a value larger than a number, "x", but I would like to do this without necessarily adding all the elements. The objective is to find the first elements which sum to the value of x.

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

For example, array is [1,2,3,4,5,6], and x = 6, so what I would be looking for are the elements [1,2,3].

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

I've looked at the standard library and have tried using the sum function from "valarray" but this just gives the sum of all the elements. Any ideas on how to code this successfully would be greatly appreciated.

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

9 个解决方案

#1

Write a functor that does the addition.

写一个加法器的函子。

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

#2

I'm assuming you just want the first X elements in the array, up until their sum meets or exceeds a threshold (the question was a little vague there).

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

If so, I don't know how to do that without your own loop:

如果是这样,我不知道如何在没有自己的循环的情况下这样做:

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

Now "i" contains the index at which the sum met or exceeded your threshold.

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

#3

Avoid the answers that suggest using find_if with a stateful predicate. Stateful predicates are dangerous as the STL algorithms assume it is safe to copy predicates. In this case, if copies are made of the predicate then each will have a different 'running total' and will not necessarily act on all values, or in the correct order.

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

Especially avoid the solution that implements its predicate's operator() member as a const member function but labels its members as mutable as this is fooling you into thinking it is not a stateful predicate, which is bad.

特别是避免将谓词的operator()成员实现为const成员函数的解决方案,但将其成员标记为可变,因为这会让你误以为它不是有状态谓词,这很糟糕。

I'd suggest using either one of the answers that simply loops to find the answer, or the answer that uses an accumulator, as that is the most correct way to do it (even if the code looks a little unwieldy.

我建议使用其中一个简单循环来找到答案的答案,或使用累加器的答案,因为这是最正确的方法(即使代码看起来有点笨拙。

Note that the warnings may well not apply to C arrays and find_if; I just don't want you to learn that stateful predicates are the right way to solve your problem since you may end up using that incorrect solution in a situation where it is dangerous in future.

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

Reference: C++ Coding Standards: 101 Rules, Guidelines, and Best Practices, Item 87

参考:C ++编码标准:101规则,指南和最佳实践,第87项

#4

Here's a slightly more generic version:

这是一个稍微更通用的版本:

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

#5

Substract the numbers from x one by one, until you reach 0 or lower.

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

No additions, as you wished :)

没有添加,如你所愿:)

#6

Here's hoping this works:

这是希望这个工作:

/* 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;
}

#7

would be something like:

会是这样的:

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

#8

Well, i would use a vector

好吧,我会使用矢量

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 would need operator+ and operator< to be defined.

T需要定义operator +和operator <。

#9

You could use std::find_if() along with a functor that maintains a running total, and only returtn true from the functor when you have found the element that puts you at or over the top.

您可以使用std :: find_if()以及一个保持运行总计的仿函数,并且当您找到将您置于顶部或顶部的元素时,只能从仿函数中返回true。

For example:

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

#1