[Help] Pascalsches Dreieck mit Rekursion erstellen.
-
Hallo zusammen,
sitze hier verzweifelnd an einer Aufgabe zur Rekursion, aus der sich ein Pascal'sches Dreieck bilden soll.
Die Aufgabenstellung lautet:
- Die Zahlen werden jeweils aus der übergeordneten Zeile ermittelt
- Das Randfeld erhält den Wert 1
- Die inneren Felder berechnen sich aus Werten der vorhergehenden Zeile.Mathematische Notation:
C(z,s) = C(z-1, s-1)+C(z-1,s)
z = aktuelle Zeile,
s = aktuelle Spalte.Mir fehlt hier leider der Ansatz, wie ich das ganze aufbauen soll.
Habe zwar schon Rekursion gemacht (Fibonacci Nummern, Fakultät) aber hier blick ich im Moment nicht durch.
Bin froh um jeden Denkanstoß; sprich wie definiere ich die Funktion(en) mit Berechnung und wie erziehle ich eine Ausgabe als "Dreieck".Hoffe ihr helft mir weiter.
Ich danke schon mal!!!
Sven
-
Kannst du Delphi Sourcen lesen?
Wir haben das mal damit gemacht.
Ich paste dir das einfach mal rein:function pas3(Zeile,Spalte:Int64):Int64; // Int64 sind 64-Bit Integer-Zahlen begin if Abbruch then Exit; // Abbruchmöglichkeit für sehr große Zahlen if (Spalte=0) or (Zeile=Spalte) then result:=1 else result:=Pas3(Zeile-1,Spalte-1)+Pas3(Zeile-1,Spalte); end; procedure TForm1.BitBtn1Click(Sender: TObject); var i,j,k : Integer; Zeile : String; ZahlString : String[12]; begin Abbruch:=False; try Screen.Cursor:=crHourGlass; for i:=0 to 35 do begin Zeile:=''; for k:=34 downto i do Zeile:=' '+Zeile; for j:=0 to i do begin ZahlString:=IntToStr(Pas3(i,j))+' '; Zeile:=Zeile+ZahlString; if j=0 then ListBox1.Items.Add(Zeile) else begin ListBox1.Items[i]:=Zeile; Application.ProcessMessages; end; if Abbruch then Exit; // Abbruchmöglichkeit für sehr große Zahlen end; end; finally ListBox1.Items.SaveToFile('pas3.txt'); Screen.Cursor:=crDefault; end; end;Vielleicht gibs dir ja einen Denkanstoß.
-
danke für den delphi code, aber leider verwirrt der mich noch mehr.
kann mir das jmd. bitte in c++ übersetzen?
DANKE!!!
-
Nun, ich denke nicht, dass du große Probleme haben wirst den Code nach C++ zu übersetzen.
Zwar ist die Syntax unterschiedlich, aber es ist wohl klar, dass ausfor i:=0 to 35 do begin for k:=34 downto i do Zeile:=' '+Zeile; for j:=0 to i do begin ZahlString:=IntToStr(Pas3(i,j))+' '; Zeile:=Zeile+ZahlString; if j=0 then ListBox1.Items.Add(Zeile) else begin ListBox1.Items[i]:=Zeile; Application.ProcessMessages; end; if Abbruch then Exit; // Abbruchmöglichkeit für sehr große Zahlen end; end;sowas hier werden kann
for(int i = 0; i < 35; ++i) { for(int k = 34; i < k; --k) zeile += " " + zeile; // zeile ist z.B. ein std::string for(int j = 0; j < i; ++j) { szahl = FUNKTIONSAUFRUF(); zeile += szahl + " "; if(j == 0) ListBox1.Items.Add(zeile); else { ListBox.Item[i] = zeile; Application.ProcessMessages; } if(Abbruch) break; // Wobei das nur dieses innere FOR killt. // Da weiß ich aber nicht wie das bei Delphi ist. } }
-
unsigned pascal(unsigned row, unsigned column) { return column&&column<row?pascal(row-1,column-1)+pascal(row-1,column):1; }
-
hmmm... also ich komm immer noch nicht klar.
stimmt denn die funktionsdefintion von camper?
ist denn "pascal" als name nicht schon vordefiniert, so dass ich besser "pas" ode so schreibe?das mit der for-Schleife müsste mir auch noch mal jmd. erklären, sprich wie das mit dem "std::string" gemeint ist, oder ob es noch anders möglich ist.
Danke!!!
-
Nun das mit dem Funktionsnamen kannst du halten wie du möchtest.
Nur sollte er für dich aussagekräftig sein!std::string ist eine Stringklasse aus der Standardbibliothek.
#include <iostream> #include <string> using namespace std; int main() { string name; cout << "Namen eingeben: "; getline(cin, name); cout << "Zahl eingeben: "; int i = 0; cin >> i; cout << "Name: " << name << endl << "Zahl: " << i << endl; return 0; }
-
Ich raffs leider immer noch nicht. Ich hab hier mal den Code für die Berechnung der Fakultät.
Was muss ich denn jetzt anders machen? Wäre froh, wenn ihr mir denn fehlenden Code mal erstellen würdet, damit ich das mit dem "String" mal sehe.
Danke.#include <iostream> #include <iomanip> using namespace std; //Funktions-Prototype unsigned long factorial( unsigned long ); int main() { for ( int i = 0; i <= 10; i++ ) cout << setw( 2 ) << i << "! = " << factorial( i ) << endl; //Funktions-Aufruf return 0; } // Rekursive Funktionsdefinition von Fakultaet unsigned long factorial( unsigned long number ) { if ( number <= 1 ) // BasisFall return 1; else // RekursivFall return number * factorial( number - 1 ); }
-
svenb schrieb:
hmmm... also ich komm immer noch nicht klar.
stimmt denn die funktionsdefintion von camper?Ja, allerdings verwendet er Rekursionen. Deswegen ist der Code auch so kurz und elegant, macht aber viele redundante Berechnungen. Wenn du nur einen Wert irgendwo aus dem Dreieck berechnen willst könnte das evtl hilfreich sein (ungetestet)...
unsigned C(unsigned n, unsigned k) { if(k > n) return 0; if(k == n) return 1; unsigned rval = 1; for(unsigned i = n; i != k; --i) rval *= i; for(unsigned i = n - k; i != 1; --i) rval /= i; return rval; }Ansonsten, wenn du ein ganzes Dreieck zeichnen willst, dann würde ich bei der Berechnung neuer Werte auf die Werte der vorigen Zeile zurückgreifen und die rekursive Definition des Binomialkoeffizienten, die du bereits oben hingeschrieben hast, benutzen. Wenn du dir bereits berechnete Werte in einem Array oder irgendwo anders merkst, dann kannst du den Vorgang deutlich beschleunigen (Stichwort: Memoization)
-
ich schnall es leider nicht
Mir ist schleierhaft, wie daraus ein Dreieck werden soll usw...ich will ja keinen belästigen, aber wäre jmd. bitte so freundlich den Code zu erstellen, damit ich mich an der richtigen Lösung orientieren kann und nicht ständig im Kreis dreh.
Danke, danke!!!Sven
-
Wie wäre es, wenn du dir ein Tutorial oder Buch schnappst und es selber probierst? Genug Anregungen hast du und Schleifen programmieren ist nicht schwer. Ausserdem bin ich sicher, dass es die Lösung per google auch fertig gibt!
-
Walli schrieb:
Wie wäre es, wenn du dir ein Tutorial oder Buch schnappst und es selber probierst? Genug Anregungen hast du und Schleifen programmieren ist nicht schwer. Ausserdem bin ich sicher, dass es die Lösung per google auch fertig gibt!
Das mit Tutorials und Büchern lesen hab ich ja gemacht, sonst würde ich mich ja hier nicht melden. Wenn du mir nen link geben kannst, dann würd ich mich freuen.
-
svenb schrieb:
ich schnall es leider nicht
Mir ist schleierhaft, wie daraus ein Dreieck werden soll usw...Stell Dir das Dreieck als Treppe vor:
1
11
121
1331
14641
usw.Um z.B. den Wert aus Zeile 5, Spalte 3 zu errechnen, musst Du die Werte aus Zeile 4, Spalten 2 und 3 addieren. Dann kommt etwa das raus, was camper hingerot..., äh, geschrieben hat
-
genau, bei dem hier darfst du das andere wort benutzen :p
unsigned p(unsigned r, unsigned c) { return c%r--?p(r,c-1)+p(r,c):1; }ist aber immer noch zu gut lesbar.
-
hallo nochmal,
Die "Dreiecks-Treppe" muss ich ja noch links neben die oben bestehende Treppe dazu bauen.
Damit ich das ganze mal grundsätzlich verstehe: Kann mir jmd. hinschreiben was ich alles brauch, um diese Aufgabe zu meistern?....reicht die eine Funktion "unsigned p(unsigned r, unsigned c) { return c%r--?p(r,c-1)+p(r,c):1; }"
was brauch ich noch? Nur eine for-Schleife mit entsprechenden Bedingungen?Also was fehlt mir noch alles zum Aufbau?
Danke.
-
Für eine erste Implementierung brauchst du nur noch zwei Schleifen, die ineinander verschachtelt sind. Fang doch einfach mal an, sonst wird das nie was.
-
bin ich hiermit auf dem richtigen Weg?
Aber wie bekomm ich eine "Pyramide" mit den entspr. Zahlen raus?//FunktionsDefinition int Pascal( int Zeile, int Spalte ) { if( Spalte == 1 ) return 1; if( Zeile == Spalte ) return 1; return Pascal( Zeile-1, Spalte-1 ) + Pascal( Zeile - 1, Spalte ); }