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

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...