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

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

  • S

    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;
}
    0
  • S

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

    0
  • V

    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.

    0
  • ?

    Sone schrieb:

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

    Jetzt hast du O(n2).

    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(n2) 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.

    0
  • S

    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:

    0
  • V

    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.

    0
  • M

    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;
}
    0
  • V

    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.

    0
  • S

    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.

    0
  • S

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

    0
  • S

    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:

    V0 = 1V_0 ~=~ 1
    V_a = V_a−1∗n−a+1aV\_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. 🤡

    0
  • M

    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 (n0),…,(nn)\binom{n}{0},\ldots,\binom{n}{n} ausgeben. Der erste Term ist 1 und jeden weiteren erhälst du durch Einsetzen der Definition: (nk+1)=n!(k+1)!(n−k−1)!=n!k!(n−k)!⋅n−kk+1=(nk)n−kk+1\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}.

    0
  • S

    Michael E. schrieb:

    (nk+1)=(nk)n−kk+1\binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1}.

    Prinzipiell was ich "entdeckt" hab, oder?

    0
  • M

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

    0
  • S

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

    0
  • ?

    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';
    0
  • S

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

    0
Anmelden zum Antworten