Trouver les éléments d'un tableau en fonction de la somme minimum

Question

J'ai écrit une boucle en C ++ pour me donner 6 nombres aléatoires et les stocker dans un tableau.  Ce que je voudrais faire est de résumer les éléments du tableau jusqu'à ce que je reçois une valeur supérieure à un certain nombre « x », mais je voudrais le faire sans nécessairement ajouter tous les éléments. L'objectif est de trouver les premiers éléments qui somme à la valeur de x.

Par exemple, un tableau est [1,2,3,4,5,6] et x = 6, donc ce que je rechercherai sont les éléments [1,2,3].

Je l'ai regardé la bibliothèque standard et ont essayé d'utiliser la fonction de somme de « valarray », mais cela donne juste la somme de tous les éléments. Toutes les idées sur la façon de coder cela avec succès grandement apprécié.

Answer 1

Ecrire un foncteur qui fait l'addition.

#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

Je suppose que vous voulez juste les premiers éléments de X dans le tableau, jusqu'à leur somme atteint ou dépasse un seuil (la question était un peu là vague).

Si oui, je ne sais pas comment faire sans votre propre boucle:

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

« i » contient l'indice auquel la somme a atteint ou dépassé le seuil.

Answer 3

Contournez les réponses qui suggèrent d'utiliser le find_if avec un prédicat stateful. prédicats stateful sont dangereuses que les algorithmes de STL supposent qu'il est sûr de copier prédicats. Dans ce cas, si les copies sont faites du prédicat alors chacun aura un autre « total en cours d'exécution » et agit pas nécessairement sur toutes les valeurs, ou dans l'ordre correct.

Surtout éviter la solution qui implémente son Membre opérateur prédicat () en fonction membre const mais les étiquettes de ses membres mutable que cela vous tromper en pensant que ce n'est pas un prédicat stateful, ce qui est mauvais.

Je suggère d'utiliser l'une des réponses que les boucles simplement pour trouver la réponse ou la réponse qui utilise un accumulateur, car c'est la façon la plus correcte de le faire (même si le code semble un peu difficile à manier.

Notez que les avertissements pourraient bien ne pas appliquer des tableaux C et find_if; Je ne veux pas vous apprendre que prédicats stateful sont la bonne façon de résoudre votre problème puisque vous pouvez finir par utiliser cette solution incorrecte dans une situation où il est dangereux à l'avenir.

Référence: C ++ Normes de codage: 101 règles, lignes directrices et les meilleures pratiques, l'article 87

Answer 4

Voici une version légèrement plus générique:

#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

Soustraire les nombres de x un par un, jusqu'à ce que vous atteignez 0 ou moins.

Aucun ajout, que vous désiriez:)

Answer 6

En espérant que cela fonctionne:

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

serait quelque chose comme:

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

Eh bien, j'utiliser un vecteur

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 aurait besoin opérateur + et l'opérateur <à définir.

Answer 9

Vous pouvez utiliser std :: find_if () avec un foncteur qui maintient un total de fonctionnement, et seulement returtn vrai du foncteur lorsque vous avez trouvé l'élément qui vous met à ou sur le dessus.

Par exemple:

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