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

Skym0sh0

Allein das was bei Wikipedia steht zum Binomischen Lehrsatz ist total easy und cool, lol...

Muss sowas auch mal programmieren...

Sky, diemerste Summenformel,aus dem wikipedia Artikel ist doch gar nicht so schwer. Was daran ist das Problem?

Skym0sh0

Mein Beitrag war auch keine Ironie...
Ich hab in der Schule früher immer nur drüber nachgedacht, wie man eben das (a+b)^n schreiben kann, bzw wie das für verschiedene n's grösser 2 aussieht. Aber ich hab nie dazu was recherchiert oder gegoogelt.

Und ja, die Formel da bei wikipedia ist auch nicht schwer...

Sone

Das ist doch viel zu einfach. Rekursiv die einzelnen Koeffizienten berechnen und dann ist der Rest nur noch eine Schleife.

Das einzige was hier schmerzt ist die Performance, aber die Funktion kann man im Notfall auch endrekursiv machen.

#include <iostream>
#include <iterator>

unsigned getPascalTriangleNumber( unsigned row,
                                  unsigned column )
{
    if( column == 0
     || column == row )
        return 1;

    return getPascalTriangleNumber(row - 1, column - 1 ) + getPascalTriangleNumber(row - 1, column );
}

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

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

Aber volkard!! Das ist noch längst nicht 1337-mäßig genug. Da geht viel mehr. Zeig was du kannst!

Sone schrieb:

Das einzige was hier schmerzt ist die Performance, aber die Funktion sollte man endrekursiv machen können.

Auaaaaaaa
O(n·eⁿ), das tut echt weh. Die Performance ist schrecklich.
Im Optimalfall (und ich bin mir nicht sicher, ob ich dir das zutrauen darf) kann man deinen Ansatz auf O(n²) verbessern.

Dabei gibt es eine so schöne O(n)-Lösung.

Sone schrieb:

Aber volkard!! Das ist noch längst nicht 1337-mäßig genug. Da geht viel mehr. Zeig was du kannst!

Aber Sprüche reissen, das kannst du.

Sone

Ja, die Performance ist natürlich kacke, weil für jeden Koeffizient das komplette Dreieck hochgelaufen wird.
Es geht schöner. Wenn man nämlich das Dreieck vorher berechnet.

Besser?

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

int main()
{
    std::vector<int> v = {1}, v2{1, 1};

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

    for( int a = 0; a < N ; ++a )
    {
        v = v2;
        v2.push_back(1);
        std::adjacent_difference( v.begin(), v.end(), v2.begin(), std::plus<int>() );
    }

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

Sone

schmerzmittel schrieb:

Sone schrieb:

Aber volkard!! Das ist noch längst nicht 1337-mäßig genug. Da geht viel mehr. Zeig was du kannst!

Aber Sprüche reissen, das kannst du.

Wieso? volkard ist bekannt für seine IOCCC-reifen Wahnsinns-Dinger.

volkard

Sone schrieb:

schmerzmittel schrieb:

Sone schrieb:

Aber volkard!! Das ist noch längst nicht 1337-mäßig genug. Da geht viel mehr. Zeig was du kannst!

Aber Sprüche reissen, das kannst du.

Wieso? volkard ist bekannt für seine IOCCC-reifen Wahnsinns-Dinger.

Echt? Zeig mal ne Auswahl.

Sone schrieb:

Es geht schöner. Wenn man nämlich das Dreieck vorher berechnet.

Jetzt hast du O(n²).

Stell dir vor, du möchtest aus einer Liste das maximale Element bestimmen.
Dein Ansatz mit adjacent_difference entspricht Bubble-Sort auf die ganze Liste und am Schluss front() zurückgeben. Das ist O(n²) mit O(n) Memory.
Die Musterlösung wäre eine lineare Suche. O(n) Memory und O(1) Speicher.

So eine Musterlösung in O(n) gibt es auch für diese Aufgabe, etwas kürzerer Code und um einiges schneller.

Sone

volkard schrieb:

Sone schrieb:

schmerzmittel schrieb:

Sone schrieb:

Aber volkard!! Das ist noch längst nicht 1337-mäßig genug. Da geht viel mehr. Zeig was du kannst!

Aber Sprüche reissen, das kannst du.

Wieso? volkard ist bekannt für seine IOCCC-reifen Wahnsinns-Dinger.

Echt? Zeig mal ne Auswahl.

Du wahrst schon vor vielen Jahren dafür berühmt, da muss ich doch nix zeigen:
http://www.c-plusplus.net/forum/35483-full (Post von Gary)

Da fällt mir ein, da hab ich mich noch mit Pi gestritten! Ach, waren das Zeiten.... :schwelg'-in-schönen-Erinnerungen:

volkard

Sone schrieb:

Du wahrst schon vor vielen Jahren dafür berühmt, da muss ich doch nix zeigen:
http://www.c-plusplus.net/forum/35483-full (Post von Gary)

Hier ist die ursprüngliche Quelle:
http://www2.fh-augsburg.de/informatik/vorlesungen/XX/c_cplus/tutorial/henkel/else_if__Loesungsvorschlag.html
Beachte den letzten Satz.
Ja, zum Spaß kann ich auch mal absichtlich unleserlich schreiben.

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.

Michael E.

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?

int coefficient = 1;
for(int i = 0; i <= n; ++i)
{
	cout << coefficient << " ";
	coefficient *= n - i;
	coefficient /= i + 1;
}

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.