Найти элементы массива по минимальной сумме

Question

Я написал цикл на C++, который дает мне 6 случайных чисел и сохраняет их в массиве.Я хотел бы суммировать элементы массива до тех пор, пока не получу значение, превышающее число «x», но я хотел бы сделать это без обязательного добавления всех элементов.Цель состоит в том, чтобы найти первые элементы, сумма которых равна значению x.

Например, массив [1,2,3,4,5,6], и x = 6, поэтому я буду искать элементы [1,2,3].

Я просмотрел стандартную библиотеку и попробовал использовать функцию суммы из «valarray», но она просто дает сумму всех элементов.Будем очень признательны за любые идеи о том, как успешно это закодировать.

Answer 1

Напишите функтор, выполняющий сложение.

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

Answer 2

Я предполагаю, что вам просто нужны первые элементы X в массиве до тех пор, пока их сумма не достигнет порогового значения или не превысит его (вопрос был немного расплывчатым).

Если да, то я не знаю, как это сделать без вашего собственного цикла:

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

Теперь «i» содержит индекс, при котором сумма достигла или превысила ваш порог.

Answer 3

Избегайте ответов, в которых предлагается использовать find_if с предикатом с сохранением состояния.Предикаты с сохранением состояния опасны, поскольку алгоритмы STL предполагают, что копирование предикатов безопасно.В этом случае, если сделать копии предиката, каждый из них будет иметь разную «промежуточную сумму» и не обязательно будет действовать на все значения или в правильном порядке.

Особенно избегайте решения, которое реализует член оператора() своего предиката как константную функцию-член, но помечает его члены как изменяемые, поскольку это вводит вас в заблуждение, заставляя вас думать, что это не предикат с сохранением состояния, а это плохо.

Я бы предложил использовать либо один из ответов, который просто зацикливается для поиска ответа, либо ответ, который использует аккумулятор, поскольку это наиболее правильный способ сделать это (даже если код выглядит немного громоздким.

Обратите внимание, что предупреждения могут не относиться к массивам C и find_if;Я просто не хочу, чтобы вы узнали, что предикаты с сохранением состояния — это правильный способ решения вашей проблемы, поскольку вы можете в конечном итоге использовать это неправильное решение в ситуации, когда это будет опасно в будущем.

Ссылка:Стандарты кодирования C++:101 Правила, рекомендации и передовой опыт, пункт 87

Answer 4

Вот немного более общая версия:

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

Answer 5

Вычтите числа из Икс один за другим, пока не достигнете 0 или ниже.

Никаких дополнений, как вы и хотели :)

Answer 6

Надеюсь, это сработает:

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

Answer 7

было бы что-то вроде:

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

Answer 8

Ну, я бы использовал вектор

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 потребуется определить операторы+ и оператор<.

Answer 9

Вы можете использовать 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;
}