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

Question

Я написал цикл на C ++, чтобы дать мне 6 случайных чисел и сохранить их в массиве. То, что я хотел бы сделать, это суммировать элементы массива, пока я не получу значение больше, чем число, «х», но я бы хотел сделать это без необходимости добавления всех элементов. Цель состоит в том, чтобы найти первые элементы, которые суммируются со значением 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 предполагают, что копировать предикаты безопасно. В этом случае, если копии сделаны из предиката, тогда у каждого будет свой «промежуточный итог», и он не обязательно будет действовать на все значения или в правильном порядке.

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

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

Обратите внимание, что предупреждения могут не относиться к массивам 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

Вычтите числа от x по одному, пока не достигнете 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

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

Answer 8

будет что-то вроде:

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 9

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

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