Encontre os elementos de uma matriz com base no montante mínimo

Question

Eu escrevi um loop em C ++ para me dar 6 números aleatórios e armazená-los em uma matriz. O que eu gostaria de fazer é somar os elementos do array até que eu obter um valor maior do que um número, "x", mas eu gostaria de fazer isso sem necessariamente adicionar todos os elementos. O objetivo é encontrar os primeiros elementos que soma ao valor de x.

Por exemplo, array é [1,2,3,4,5,6] e x = 6, então o que eu estaria procurando são os elementos [1,2,3].

Eu olhei para a biblioteca padrão e tentei usar a função soma de "valarray", mas isso só dá a soma de todos os elementos. Todas as ideias sobre a forma de código este sucesso seria muito apreciada.

Answer 1

Escrever um functor que faz a adição.

#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

Eu estou supondo que você quer apenas os primeiros elementos X na matriz, até sua soma atende ou excede um limite (a pergunta era um pouco vago lá).

Se assim for, eu não sei como fazer isso sem o seu próprio loop:

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

Agora "i" contém o índice no qual a soma cumpriu ou excedeu seu limite.

Answer 3

Evite as respostas que sugiro usar find_if com um predicado stateful. predicados stateful são perigosos como os algoritmos STL assumir que é seguro para cópia predicados. Neste caso, se as cópias são feitas do predicado, em seguida, cada um terá um diferente 'correndo total' e não necessariamente agir sobre todos os valores, ou na ordem correta.

Especialmente evitar a solução que implementos de seu predicado operator () membro como uma função membro const, mas rotula seus membros como mutável como este é enganar em pensar que não é um predicado de estado, o que é ruim.

Eu sugiro usar qualquer uma das respostas que simplesmente loops para encontrar a resposta, ou a resposta que utiliza um acumulador, uma vez que é a maneira mais correta de fazê-lo (mesmo que o código parece um pouco pesado.

Note que as advertências pode muito bem não se aplica a matrizes C e find_if; Eu só não quero que você aprenda que os predicados stateful são o caminho certo para resolver seu problema, pois você pode acabar usando essa solução incorreta em uma situação onde é perigoso no futuro.

Referência: C ++ Coding Standards: 101 Regras, diretrizes e melhores práticas, ponto 87

Answer 4

Aqui está uma versão ligeiramente mais 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

Subtraia os números de x , um por um, até chegar a 0 ou diminuir.

Não há adições, como você desejou:)

Answer 6

Aqui está esperando que isso 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

seria algo 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

Bem, eu usaria um 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 precisaria operador + e operador

Answer 9

Você pode usar std :: find_if (), juntamente com um functor que mantém uma execução total, e só returtn verdadeiro do functor depois de ter encontrado o elemento que coloca em ou por cima.

Por exemplo:

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