Binomialkoeffizient
-
Also erstmal vorweg: Ich verstehe vieles von dem was Du schreibst nicht. Ich weiß weder wann ein Algorithmus logarithmisch ist (vielleicht logarithmische Laufzeit?) noch was eine "zu algorithmierende Summenformel" sein soll. Wenn ich also was schreibe was Du nicht brauchen kannst, dann ignoriere es einfach.
Wenn ich es recht verstanden habe möchtest Du
effizient auswerten. Also die Summe über alle Binomialkoeffizienten (n über k). Mit dem binomischen Satz kommt da einfach 2^n raus.
-
Danke shconmal im vorraus für die schnellen antworten. Also die Summenformell soll praktisch am ende des progarmms ausgeben:
n=2:
1 - 2 - 1n=3:
1 - 3 - 3 - 1n=4:
1 - 4 - 6 - 4 - 1n=5:
1 - 5 - 10 - 10 - 5 - 1n=6:
1 - 6 - 15 - 20 - 15 - 6 -1
usw..
Ich schreibe das der Logarithmus logarithmisch ist, da ich erst eine formel hatte die 2^n terme hatte. mit Hilfe des Pascallschen dreiecks habe ich nurnoch
n-terme. Aus dem Grund heraus:
Wenn ich n=5 habe, dann:
1 mal den 1. Term
5 mal den 2. Term
10 mal den 3. Term usw...Also wirklich das ganze dreieck. Ich hab mir auch grad überlegt, das es dann sicher auch einfacher geht, aber ich wüsst halt nicht wie ichs programmieren sollte.
-
Das ist alles ziemlich wirr. Nur das der Logarithmus logarithmisch ist, leuchtet mir auf eine geweisse Art und Weise ein
Also noch ein Versuch: Was soll dein Programm tun? Die n-te Zeile des Paskalschen Dreickes ausgeben, wobei der Benutzer die Zahl n selber wählt?
-
soll ich das komplette problem incl mathematischer herleitung und bisherigen sourcecode aufschreiben, um klarheit zu shcaffen, was ich will?
-
Ne, die Problemstellung einmal sauber und nötigenfalls mit Beispiel würde schon genügen. Wenn Du mit einigen Fachbegriffen unsicher bist, dann lasse sie lieber weg. Das verwirrt sonst mehr als es hilft.
-
ok ich werd das heute nacht oder morgen früh mit beispiel machen. Damit kein Doppelposting entsteht werde ich dann einfach diesen Beitrag hier editieren. Bis dahin...
-
Jester schrieb:
Ne, die Problemstellung einmal sauber und nötigenfalls mit Beispiel würde schon genügen. Wenn Du mit einigen Fachbegriffen unsicher bist, dann lasse sie lieber weg. Das verwirrt sonst mehr als es hilft.
Ich habe zwei mögliche Deutungen:
1. Er möchte einen Parser / Tachenrechner ( der es ausrechnet ):
Psydokode ( Legende: #Benutzerangabe#) > 1. Eingabe "Potenz": #2# > 2. Eingabe "term A": #6# > 3. Eingabe "term A": #7# > Ergebnis: <(6 + 7) ^2 => (13)^2 => 169 >2. Er möchte ein "Textausgeber" z.B. ( der nur den "String ausgibt"):
Psydocode: >1. Potenz: #4# >2. Term 1: #"b"# <= nur Zeichen eingeben >3. Term 2: #"c"# #Erebnis:# (Als Zeichenkette) "(b + c ) ^ 4 = ( b + c ) ^ 2 * ( b + c ) ^ 2 = b^4 +4*b^3*c + 6*b^2*c^2 + 4*b*c^3 + c^4"
-
Hallo Balkohol,
so richtig verstanden habe ich Deine Frage auch nicht. Wenn Du die Binomialkoeffizienten berechnen willst, so kannst Du es Dir zu Nutze machen, dass jeder sich leicht aus seinem Vorgänger bestimmen lässt. Ist
so ist
In C++ kannst Du das z.B. so umsetzen.
#include <iostream> struct BinomKoeff { explicit BinomKoeff( int n = 0 ) : m_val( 1 ), m_n( n ), m_k( 0 ) {} BinomKoeff& operator++() { m_val *= (m_n - m_k); m_val /= ++m_k; return *this; } int operator*() const { return m_val; } private: int m_val; int m_n, m_k; }; int main() { using namespace std; for( int n; cout << "n=", cin >> n; ) { BinomKoeff bk(n); for( bool strich = false; *bk; ++bk, strich = true ) { if( strich ) cout << " - "; cout << *bk; } cout << endl; } return 0; }Das erzeugt dann in etwa die Ausgabe, die Du oben angegeben hast.
Gruß
Werner
-
HEy genau das ist shconmal das richtige!!! Danke Schonmal. Naja und jetzt kommen noch meine restlichen noob-frage
Da ich wie gesagt erst seit kurzem c++ programmiere und ich fast direkt in c++ vom hallo welt zu diesem programm übergegangen bin hab ich diverse Syntax-probleme. Habe jetzt mal Das Programm von Werner mit meinem kombiniert. Und zwra möchte ich erstmal in diesem Programm bezwecken das das Programm (jetzt kommts) die n-te ableitung von der Funktionsin X * X^(4/7)
berechnet. Das ganze ist ja ein Produkt und eine Produktformel berechnet man ja durch u'*v+u*v' wenn man das ohne kürzen durchzieht hat man 2^n Terme. Ich hab nun mit einem Komilitonen von mir herausgefunden das wenn man die terme Allein ableitet und in eine n*2 Matrix schreibt (bzw eine tabelle mit n zeilen und 2 spalten) so ist Das kürzen bzw die gewünschte Multiplikation der auszuklammernden Terme das Pascalsche Dreieck Oo.
So Das hab ich Mathematsich jetzt und jetzt kommt der schwierige Part das in c++ umzusetzen. Ich gebe euch einfach mal den gesamten code:using namespace std; // Variablendefinition float potenz=-3.0/7.0, vorz=4.0/7.0; int zi=1, i=1, schalter=1, n, zi2; //---------------------------------------------------------------------------// struct BinomKoeff { explicit BinomKoeff( int n = 0 ) : m_val( 1 ), m_n( n ), m_k( 0 ) {} BinomKoeff& operator++() { m_val *= (m_n - m_k); m_val /= ++m_k; return *this; } int operator*() const { return m_val; } private: int m_val; int m_n, m_k; }; //---------------------------------------------------------------------------// void Termableitung(void) { // Arraydefinition int spalte1[n]; double spalte11[n]; double spalte12[n]; // Es Folgen Die Ableitungen der Einzelnen Terme do { // 1. Term wird "abgeleitet" und in array geschrieben switch(schalter) { case 1:spalte1[i]=1; break; //sin x case 2:spalte1[i]=2; break; // cos X case 3:spalte1[i]=3; break; // -sin X case 4:spalte1[i]=4; schalter=0; break; // -cos X } //2. term wird Berechnet vorz=vorz*potenz; potenz=potenz-1; // Vorzeichen und Potenz des 2. Terms wird je in ein Array geschrieben spalte11[i]=vorz; spalte12[i]=potenz; //Schrittweisen der Zählervariablen i++; schalter++; } while(n!=i); }; //---------------------------------------------------------------------------// void Ausgabe(void) { zi2=n-zi; //zi2 bewirkt, dass der 2. term verkehrtherum ausgelesen wird zi++; //produkt=fakul*spalte1[zi]*spalte2[zi2]; cout << " * ("; switch(spalte1[zi]) { case 1: cout << "sin X "; break; case 2: cout << "cox X "; break; case 3: cout << "-sin X "; break; case 4: cout << "-cos X "; break; } cout << " * "; cout << spalte11[zi2]; //Vorzeichen cout << " X ^ ("; cout << spalte12[zi2]; //Potenz cout << "))\n"; }; //---------------------------------------------------------------------------// int main(int argc, char *argv[]) { cout << "n=", cin >> n; BinomKoeff bk(n); for(bool strich = false; *bk; ++bk, strich = true ) { if( strich ) { Ausgabe(); } cout << *bk; } getch(); return(0); }Also er meckert halt rum das ich in der Funktion Termableitung die Array nicht so definieren kann - das soll er ja aber auch erst amchen wenn ich die Funktion aufrufe(!!).
-
Balkohol schrieb:
Da ich wie gesagt erst seit kurzem c++ programmiere und ich fast direkt in c++ vom hallo welt zu diesem programm übergegangen bin ...
Mutig, mutig!
Balkohol schrieb:
Also er meckert halt rum das ich in der Funktion Termableitung die Array nicht so definieren kann - das soll er ja aber auch erst amchen wenn ich die Funktion aufrufe(!!).
Ja, das ist richtig. In C++ kannst Du keine dynamischen Arrays auf den Stack legen. In diesem Fall kannst Du statt dessen std::vector<> benutzen. Also etwa so:
void Termableitung() { using namespace std; // Arraydefinition vector< int > spalte1(n); vector< double > spalte11(n); vector< double > spalte12(n); // Es Folgen Die Ableitungen der Einzelnen Terme // ...Dazu braucht man dann noch ein #include <vector> damit's funkt.
Im Übrigen würde ich Dir aber stark empfehlen einen anderen Ansatz zu benutzen. Die globale Variablen-Deklaration ist .. sagen wir leicht daneben.
Da ist doch das Produkt aus zwei Funktionen
deren Natur sich durch Ableiten nicht wesentlich verändert. Da ist es angebracht dafür eine Klasse zu schreiben.class Trigo // Funktion +/-sin(x) bzw. +/-cos(x) { public: enum { sin_x = 1, cox_x = 2 }; explicit Trigo( int typ = sin_x ) : m_typ( typ ) {} Trigo derivation() const { // Ableitung bestimmen int typ = 0; switch( m_typ ) { case sin_x: typ = cox_x; break; case cox_x: typ = -sin_x; break; case -sin_x: typ = -cox_x; break; case -cox_x: typ = sin_x; break; } return Trigo( typ ); } friend std::ostream& operator<<( std::ostream& out, const Trigo& trigo ) { using namespace std; if( trigo.m_typ < 0 ) out << "-"; if( abs( trigo.m_typ ) == Trigo::sin_x ) return out << "sin(x)"; return out << "cos(x)"; } private: int m_typ; };Ich weiß, Du bist Anfänger .. aber ich gehe gleich in die Vollen. Schau Dir erstmal die Anwendung an:
#include <iostream> // #include Trigo.h (s.o.) int main() { using namespace std; Trigo f( Trigo::sin_x ); cout << "Funktion " << f << endl; for( int n=1; n<=4; ++n ) cout << n << ".Ableitung: " << (f = f.derivation()) << endl; return 0; }Im Grunde besteht die Klasse Trigo nur aus einem int, was die Werte 1,2,-1 und -2 annehmen kann, genau wie Du das vorher mit den Werten 1 bis 4 gemacht hast. Nur das alles inklusive der Ableitung (Methode derivation()) und der Ausgabe (operator<<) in einer Klasse untergebracht wird.
Das gleiche für die andere Funktion
template< typename T > class X_hoch // Funktion fac*x^(exp) { public: typedef T value_type; X_hoch() : m_fac(0), m_exp(1) {} X_hoch( value_type fac, value_type exp ) : m_fac( fac ), m_exp( exp ) {} X_hoch derivation() const { // Ableitung bestimmen if( m_exp == value_type(0) ) // Sonderbehandlung für Konstante return X_hoch(); return X_hoch( m_exp * m_fac, m_exp - value_type(1) ); } friend std::ostream& operator<<( std::ostream& out, const X_hoch& xh ) { if( xh.m_fac == value_type(0) || xh.m_exp == value_type(0) ) return out << xh.m_fac; if( xh.m_fac == value_type(-1) ) out << "-"; else if( xh.m_fac != value_type(1) ) out << xh.m_fac; if( xh.m_exp == value_type(1) ) out << "x"; else out << "x^(" << xh.m_exp << ")"; return out; } private: value_type m_fac, m_exp; };Diesmal aber als Template. So kann man den Typ für den Exponenten frei wählen. Falls Du die boost-Library hast oder installierst, so kannst Du hier boost::rational verwenden. Ansonsten einfach double benutzen.
Wieder ein kleines Testprogramm
#include <iostream> #include <boost/rational.hpp> // #include "X_hoch.h" (s.o.) int main() { using namespace std; X_hoch< boost::rational< int > > f( 1, boost::rational< int >( 4, 7 ) ); // oder: X_hoch< double > f( 1, 4.0/7.0 ); cout << "Funktion " << f << endl; for( int n=1; n<=4; ++n ) cout << n << ".Ableitung: " << (f = f.derivation()) << endl; return 0; }Hier erhält man als Ausgabe:
Funktion x^(4/7) 1.Ableitung: 4/7x^(-3/7) 2.Ableitung: -12/49x^(-10/7) 3.Ableitung: 120/343x^(-17/7) 4.Ableitung: -2040/2401x^(-24/7)So jetzt noch eine kleine Funktion, die alle Ableitungen von 1 bis n erzeugt. Da die für beide Typen benötgt wird, das ganze wieder als Template:
template< typename F, typename SZ > std::vector< F > make_derivations( F funk, SZ n ) { std::vector< F > erg( 1, funk ); // Funktion selbst ist 0'te Ableitung for( ; n > 0; --n ) { funk = funk.derivation(); erg.push_back( funk ); } return erg; }Und dann das Ganze zusammenstecken und ausgeben
int main() { using namespace std; Trigo trigo( Trigo::sin_x ); X_hoch< boost::rational< int > > x_hoch( 1, boost::rational< int >( 4, 7 ) ); cout << "Gegeben ist die Funktion " << trigo << "*" << x_hoch << endl; cout << "Geben Sie den Grad der gewuenschten Abeitung ein. " << endl; for( int n; cout << "n=", cin >> n; ) { vector< Trigo > trigos = make_derivations( trigo, n ); vector< X_hoch< boost::rational< int > > > x_hochs = make_derivations( x_hoch, n ); vector< Trigo >::iterator i_trigo = trigos.begin(); vector< X_hoch< boost::rational< int > > >::reverse_iterator i_x_hoch = x_hochs.rbegin(); bool plus_sign = false; for( BinomKoeff bk(n); *bk; ++bk, ++i_trigo, ++i_x_hoch ) { if( plus_sign ) cout << " + "; else plus_sign = true; if( *bk != 1 ) cout << *bk << "*"; cout << *i_trigo << "*" << *i_x_hoch; } cout << endl; } return 0; }Und so sollte der Output aussehen:
Gegeben ist die Funktion sin(x)*x^(4/7) Geben Sie den Grad der gewuenschten Abeitung ein. n=2 sin(x)*-12/49x^(-10/7) + 2*cos(x)*4/7x^(-3/7) + -sin(x)*x^(4/7) n=0 sin(x)*x^(4/7) n=.. starker Tobak für einen Anfänger - klar, aber versuch' mal Dich durchzukämpfen. Viel Spaß!
Gruß
Werner