Finden Sie die Elemente eines Arrays auf Basis von Mindestsumme

Question

Ich habe eine Schleife in C ++ geschrieben, um mir 6 Zufallszahlen und speichert sie in einem Array.  Was würde ich gerne tun ist, um die Elemente des Arrays zu summieren, bis ich einen Wert größer als eine Zahl zu erhalten, „x“, aber ich würde dies tun, ohne notwendigerweise das Hinzufügen all Elemente. Das Ziel ist es, die ersten Elemente, die Summe auf den Wert von x zu finden.

Zum Beispiel Array ist [1,2,3,4,5,6] und x = 6, so etwas würde ich suchen sind die Elemente [1,2,3].

Ich habe schon in der Standardbibliothek gesucht und habe mit der Summenfunktion von „valarray“ versucht, aber das gibt nur die Summe aller Elemente. Alle Ideen, wie dies codieren erfolgreich werden würden sehr geschätzt werden.

Answer 1

Schreiben Sie einen Funktor, die die Addition der Fall ist.

#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

Ich nehme an, Sie sind die ersten X-Elemente im Array wollen, bis ihre Summe erreicht oder überschreitet einen Schwellenwert (die Frage war ein wenig vage dort).

Wenn ja, ich weiß nicht, wie das zu tun, ohne eigene Schleife:

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

„i“ enthält den Index, bei dem die Summe erreicht oder überschritten Ihre Schwelle.

Answer 3

Vermeiden Sie die Antworten, die mit einem Stateful Prädikat schlagen vor, mit find_if. Stateful Prädikate sind gefährlich, da die STL-Algorithmen annehmen, dass es sicher ist, Prädikate zu kopieren. In diesem Fall, wenn Kopien des Prädikats gemacht werden, dann wird jeweils eine unterschiedliche ‚laufende Summe‘ und wird auf allen Werten nicht unbedingt handeln, oder in der richtigen Reihenfolge.

Vor allem die Lösung zu vermeiden, die sein Prädikat des Operators () Element als eine konstante Elementfunktion implementiert, sondern markiert seine Mitglieder als wandelbar wie dies Sie in fooling denken, es ist kein Stateful Prädikat ist, was schlecht ist.

Ich würde vorschlagen, entweder eine der Antworten verwenden, die einfach Schleifen die Antwort zu finden, oder die Antwort, die einen Speicher verwendet, so dass die richtige Art und Weise ist, es zu tun (auch wenn der Code ein wenig sperrig aussieht.

Beachten Sie, dass die Warnungen können auch nicht auf C-Arrays und find_if anzuwenden; Ich möchte Dich nicht nur erfahren, dass Stateful Prädikate sind der richtige Weg, um Ihr Problem zu lösen, da Sie diese falsche Lösung in einer Situation am Ende mit, wo es gefährlich in Zukunft ist.

Referenz: C ++ Coding Standards: 101 Regeln, Richtlinien und Best Practices, Artikel 87

Answer 4

Hier ist eine etwas allgemeinere Version:

#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

subtrahieren die Zahlen von x eins nach dem anderen, bis Sie erreichen 0 oder niedriger ist.

Keine Zusätze, wie man will:)

Answer 6

Hier hofft, dass dies funktioniert:

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

wäre so etwas wie:

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

Nun, ich würde einen Vektor verwenden

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 Operator + brauchen würde und operator

Answer 9

Sie könnten std :: find_if () zusammen mit einem Funktor, der eine laufende Summe hält, und nur returtn wahr vom Funktors verwenden, wenn Sie das Element gefunden haben, die Sie auf oder über die Spitze setzt.

Zum Beispiel:

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