Encontrar los elementos de una matriz a base de suma mínima

Question

He escrito un bucle en C ++ para darme 6 números al azar y almacenarlos en una matriz.  Lo que me gustaría hacer es sumar los elementos de la matriz hasta que tenga un valor mayor que un número "x", pero me gustaría hacer esto sin añadir necesariamente todos los elementos. El objetivo es encontrar los primeros elementos que suman al valor de x.

Por ejemplo, la matriz es [1,2,3,4,5,6], y x = 6, así que lo que estaría buscando son los elementos [1,2,3].

He mirado en la biblioteca estándar y han tratado de utilizar la función de suma de "valarray", pero esto sólo da la suma de todos los elementos. Cualquier ideas sobre cómo codificar esto con éxito serían muy apreciados.

Answer 1

Escribir un funtor que hace la adición.

#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

Estoy asumiendo que lo que desea es los primeros elementos de la matriz X, hasta que su suma cumple o excede un umbral (la pregunta era un poco vago allí).

Si es así, no sé cómo hacerlo sin su propio bucle:

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

Ahora "i" contiene el índice en el cual la suma alcanza o se supera el umbral.

Answer 3

Evitar las respuestas que sugieren usar find_if con un predicado de estado. predicados con estado son peligrosos ya que los algoritmos STL asumen que es seguro para copiar los predicados. En este caso, si se hacen copias del predicado entonces cada uno tendrá un 'total acumulado' diferente y no necesariamente actuar sobre todos los valores, o en el orden correcto.

Especialmente evitar la solución que implementa miembro de su predicado operador () como un método constante, pero las etiquetas de sus miembros como mutable ya que esto le está engañando al pensar que no es un predicado de estado, lo cual es malo.

Me gustaría sugerir el uso de cualquiera de las respuestas que simplemente bucles para encontrar la respuesta, o la respuesta que utiliza un acumulador, ya que es la forma más correcta de hacerlo (incluso si el código es un poco difícil de manejar.

Tenga en cuenta que las advertencias bien pueden no ser aplicables a matrices C y find_if; Es sólo que no quiero que aprendas que los predicados con estado son la manera correcta de resolver su problema, ya que puede terminar con esa solución incorrecta en una situación en la que es peligroso en el futuro.

Referencia: C ++ estándares de codificación: 101 Normas, directrices y mejores prácticas, Artículo 87

Answer 4

Esto es una versión ligeramente más genérico:

#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

Restar los números de x , uno por uno, hasta llegar a 0 o inferior.

No hay adiciones, como usted deseaba:)

Answer 6

Aquí está esperando que esto funciona:

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

sería algo así como:

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

Bueno, me gustaría utilizar un 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 necesitaría operador + y el operador

Answer 9

Se puede usar std :: find_if () junto con un funtor que mantiene un total acumulado, y sólo returtn verdadero de lo funtor cuando haya encontrado el elemento que lo pone en o sobre la parte superior.

Por ejemplo:

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