Algorithmus Verbessern??

BorisDieKlinge

oh sorry es sollte : 14,10,8,5 rauskommen!! aulso immer aufsummiert!

CStoll

Die harte Version ist wohl, bei jedem Einfügen den neuen Summanden auf alle bisherigen Vektor-Elemente zu addieren. Wenn du erst viele Daten eingeben und dann die Summen ausgegeben haben willst, kannst du das Summieren auch auf später verschieben - partial_sum() (in deinem Fall wohl mit Reverse-Iteratoren) ist ideal dafür.

Konrad Rudolph

void Push(vector<int>& vec, int elem)
{
    for_each(vec.begin(), vec.end(), bind2nd(plus<int>(), elem));
    vec.push_back(elem);
}

Ungetestet (Header <functional> + <algorithm>).

BorisDieKlinge

@Konrad: Was macht der code genau?

otze

BorisDieKlinge schrieb:

@Konrad: Was macht der code genau?

wenn das element eingefügt werden soll, wird zuerst auf jedes element im vector der wert aufaddiert.

CStoll

Vermutlich nicht das richtige (for_each() wirkt vor allem durch die Nebeneffekte seines Funktors - und plus<> hat keinen Nebeneffekt). Wenn, dann wäre eher transform() geeignet:

transform(vec.begin(),vec.end(),vec.begin(),bind2nd(plus<int>,elem));

Und mit dieser Anpassung bewirkt der Code, daß der neue Summand auf jedes bisher vorhandene Element aufaddiert wird.

BorisDieKlinge

ok, und dies ist schneller wenn ich das mit nem normalen iterator mache und jedes elem += hochaddiere?

Meep Meep

mein vorschlag waere:

class Vector
{
   public:
      Vector(void) : result(0) { vec.push_back(result); }
      void push_back(int x)
      {
         vec.push_back(result += x);
      }
      int operator[](std::size_t pos)
      {
         return vec.back() - vec[pos];
      }
      std::size_t size(void) const { vec.size() - 1; }
      void clear(void)
      {
         vec.clear();
         vec.push_back(result = 0);
      }

   private:
      std::vector<int> vec;
      int result;
};

der zugriff dauert zwar bissl laenger, jedoch ersparst du dir das aufsummieren der einzelnen werte im vector.

Meep Meep

Konrad Rudolph

CStoll schrieb:

Wenn, dann wäre eher transform() geeignet:

Arg. Es ist nicht nur "geeignet" sondern war auch gemeint.

Konrad Rudolph

BorisDieKlinge schrieb:

ok, und dies ist schneller wenn ich das mit nem normalen iterator mache und jedes elem += hochaddiere?

Für nichttriviale Typen ist das manuelle Durch-Iterieren eventuell schneller, weil man eben '+=' statt '+' verwenden kann und somit das Anlegen temporärer Objekte verhindert. Für 'int' sollte es relativ egal sein.

CStoll

BorisDieKlinge schrieb:

ok, und dies ist schneller wenn ich das mit nem normalen iterator mache und jedes elem += hochaddiere?

Komplexitätstheoretisch dürfte das keinen Unterschied bringen. Die einzige echte Verbesserung (jenseits von Mikro-Optimierung), die mir hier einfällt, ist Lazy Evaluation (das bringt aber nur dann etwas, wenn du erst alle Werte einliest und das Aufsummieren auf Später verschiebst):

for(...)
{
  cin>>val;
  vec.push_back(val);//hier sammeln wir nur die Elemente, ohne zu summieren
}
partial_sum(vec.rbegin(),vec.rend(),vec.rbegin());//damit summierst du alle oben eingelesenen Elemente auf

Wenn du immer abwechselnd Werte eingeben und Zwischensummen berechnen willst, wird der Verwaltungsaufwand für diesen Ansatz vermutlich zu hoch.