expandierte Form des Ausdrucks (a+b)^n ausgeben

volkard

Michael E. schrieb:

volkard schrieb:

Hab's übrigens gerade in O(n) hinbekommen. Da hätte ich aber nicht daran gedacht, wenn schmerzmittel nicht gesagt hätte, daß es geht.

Hmm? Übersehe ich was oder sollte das nicht ziemlich einfach gehen?

Du hast nichts übersehen. Ich sage ja nicht, daß es schwierig war. Aber es sprang mir nicht von allein ins Auge.

Sone

Ich hab hier grad eine Viertelstunde im Wahnsinn gesucht und geformelt, dann bin ich auf ein Muster gestoßen:

#include <iostream>
#include <iterator>
#include <vector>
#include <numeric>

int main()
{
    unsigned const N = *std::istream_iterator<unsigned>(std::cin);

    std::vector<int> v( N + 1 );
    v[0] = 1;

    int const half = (N + 2) / 2;

    for( int a = 1; a < N + 1 ; ++a )
        v[a] = v[a - 1] * (N - a + 1) / a;

    for( unsigned counter = 0; counter < N + 1; ++counter )
        std::cout << '\n' << v[counter] << " a^" << N-counter << " b^" << counter;
}

Man beachte die Zeile 16...
Edit: Falsche Zeile.

Sone

Für Michael ist es ein Kinderspiel! Wie doof muss ich erst sein?

Sone

Das Muster:

Sei die Reihe V die in dem Pascalschen Dreieck in der Reihe n stehende Reihe, und die Spalte in der wir uns befinden a, dann lässt sich die Reihe wie folgt erzeugen:

$V_0 ~=~ 1$
$V\_a ~=~ V\_{a - 1} * \frac{n - a + 1}{a}$

Wenn wir davon ausgehen, dass die erste Zeile/Spalte/Reihe Index 0 hat.

Ja, zum Spaß kann ich auch mal absichtlich unleserlich schreiben.

Also hatte ich Recht. Du kleiner Schlawiner.

Michael E.

Sone schrieb:

Für Michael ist es ein Kinderspiel! Wie doof muss ich erst sein?

Das hat nichts mit Doofsein zu tun, sondern mit Übung mit den Binomialkoeffizienten. Das können nämlich ganz schön biestige Viecher sein. Naja, hier willst du $\binom{n}{0},\ldots,\binom{n}{n}$ ausgeben. Der erste Term ist 1 und jeden weiteren erhälst du durch Einsetzen der Definition: $\binom{n}{k+1} = \frac{n!}{(k+1)!(n-k-1)!} = \frac{n!}{k!(n-k)!}\cdot\frac{n-k}{k+1} = \binom{n}{k}\frac{n-k}{k+1}$ .

Sone

Michael E. schrieb:

$\binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1}$ .

Prinzipiell was ich "entdeckt" hab, oder?

Michael E.

Ja, wenn man a := k+1 setzt, steht da dasselbe.

Sone

Und was ist jetzt die Laufzeitklasse meiner letzten Version? Ist das schon O(n)?
Edit: Müsste es sein.. ist prinzipiell nur eine Schleife mit N Durchläufen.

Da fällt mir auf, µ hätte mir, wie war das, "auf die Finger geschlagen", wenn ich über Laufzeitklassen rede...

Sone schrieb:

Und was ist jetzt die Laufzeitklasse meiner letzten Version? Ist das schon O(n)?
Edit: Müsste es sein.. ist prinzipiell nur eine Schleife mit N Durchläufen.

Du hast es verstanden. Es sind 2 Schleifen mit N und N+1 Durchläufen, also insgesamt O(n+(n+1)+c) bzw. O(n).

Vollständiger Code:

std::cout << "1*a^0*b^" << n;
for (int i=1, c=n; i<=n; c*=n-i,c/=++i)
  std::cout << " + " << c << "*a^"<< n-i << "*b^" << i;
std::cout << '\n';

Sone

Ach klar, man kann natürlich auch ohne Pufferung machen...