Trova gli elementi di una matrice a base di somma minima

Question

Ho scritto un ciclo in C ++ mi di dare 6 numeri casuali e memorizzarli in un array.  Quello che vorrei fare è quello di sommare gli elementi dell'array fino a ottenere un valore più grande di un certo numero, "x", ma vorrei farlo senza necessariamente aggiungere tutti gli elementi. L'obiettivo è quello di trovare i primi elementi che somma al valore di x.

Per esempio, array è [1,2,3,4,5,6], e x = 6, quindi quello che sarebbe in cerca di sono gli elementi [1,2,3].

Ho guardato la libreria standard e provato con la funzione somma da "valarray", ma questo dà solo la somma di tutti gli elementi. Tutte le idee su come codificare questo successo sarebbe molto apprezzato.

Answer 1

Scrivi un funtore che fa l'aggiunta.

#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

sto supponendo che si desidera solo i primi elementi di X nella matrice, fino al loro somma raggiunge o supera una soglia (la domanda era un po 'vago lì).

Se è così, non so come fare senza il proprio ciclo:

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

Ora "i" contiene l'indice in cui la somma raggiunto o superato la soglia.

Answer 3

Evitare le risposte che suggeriamo di usare find_if con un predicato stateful. predicati stateful sono pericolosi come gli algoritmi STL assumono è sicuro di copiare predicati. In questo caso, se le copie sono fatte del predicato allora ciascuno avrà un diverso 'totale parziale' e non saranno necessariamente agire su tutti i valori o nell'ordine corretto.

In particolare evitare la soluzione che implementa membro del suo predicato dell'operatore () come una funzione membro const ma etichetta i suoi membri come mutevole come questo si sta prendendo in giro a pensare che non è un predicato stateful, che è male.

Io suggerirei utilizzando una delle risposte che loop semplicemente per trovare la risposta, o la risposta che utilizza un accumulatore, in quanto questo è il modo più corretto per farlo (anche se il codice sembra un po 'ingombrante.

Si noti che gli avvertimenti potrebbero non si applica alle matrici C e find_if; E 'solo che non voglio che tu impari che predicati stateful sono il modo giusto per risolvere il problema in quanto si può finire con questa soluzione non corretta in una situazione in cui è pericoloso in futuro.

Riferimento: C ++ norme di codifica: 101 regole, linee guida e best practice, punto 87

Answer 4

Ecco una versione leggermente più generico:

#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

Sottrarre i numeri da x uno per uno, fino a raggiungere 0 o inferiore.

Non ci sono aggiunte, come si voleva:)

Answer 6

Ecco sperando funziona:

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

sarebbe qualcosa come:

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

Bene, vorrei utilizzare un vettore

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 avrebbe bisogno dell'operatore + e l'operatore

Answer 9

È possibile utilizzare std :: find_if () insieme a un funtore che mantiene un totale parziale, e solo INDIETRO vero dal funtore quando avete trovato l'elemento che ti mette in corrispondenza o sopra le righe.

Ad esempio:

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