Pascalsche Dreieck

[Mr. General]

Also erstmal hallo!

Arbeitsauftrag ist folgender:

Pascalsches Dreieck
Eingabe in Edit: Anzahl der Zeilen, die berechnet werden sollen
Ausgabe in einem Memo-Feld

Ich weiß nicht wie ich da ran gehen soll... Ich hab schon viel gegoogelt aber nichts passendes gefunden.

Wäre echt nett wenn ihr mir helfen könntet

[lbccaleb]

Hey, ich habe vor einger Zeit schon mal das Dreieck hier veröffentlicht, vllt kann es dir weiterhelfen,du kannst es ja weiterentwickeln, mit den Dingen die du benötigst!!

Hoof mal das kann dir weiter helfen :lol:

[Mr. General]

passt perfekt :) ich habs jetzt so wie ich es brauche.

funktioniert genau so wie es soll, jetzt muss ich es nurmehr verstehen, kommentieren und fertig. :mrgreen:

[ericsson333]

Hallo zusammen,

bäuchte auch mal das Pascal'sche Dreieck mit Eingabe der Zeilenlänge in einem Edit-Feld. Ausgabe über
ButtonClick in einer Listbox. Könnte mit hierzu vielleicht einer behilflich sein.
Habe nächste Woche Klausur und keinen Plan wie ich das umsetzen soll. Ich weiß auch nicht wie ich
die Ausgabe über Memofeld umschreiben könnte.

Weiß hier jemand was??
VIelen dank vorab.

[MrMooed]

Bist du dir sicher, dass die Ausgabe über eine TListBox erfolgen soll? :shock:

Vielleicht meinst du eine TListView? Wäre jedenfalls meiner Meinung nach deutlich sinnvoller

[Furtbichler]

Also eine Listview?
Dann eine ListBox mit Courier-Zeichensatz und '*' und ' '.
Noch hübscher ist natürlich eine Paintbox.

[MrMooed]

Ansonsten habe ich mir ein altes Schulprojekt herausgekramt:

Stell dir das Dreieck einfach als 2D-Array vor.

Code:

Ebene: | Ergebnis:
0      |     1
1      |    1 1
2      |   1 2 1
3      |  1 3 3 1
4      | 1 4 6 4 1

Bei dem Dreieck wissen wir als einziges, dass außen immer eine '1' steht. Außerdem sehen wir, dass jede Dimension (Ebene) einen Wert mehr hat, als die vorherige.
D.h. konkret, dass wir ein Array erschaffen müssen, dessen Dimensionen immer um eins incrementiert werden und "außen" den Wert '1' besitzen:

Delphi-Quellcode:

procedure PasDreieck(var Ebenen: Integer);
var 
  PasDreieck : Array of Array of Integer;
  i, j       : Integer;
begin
for i:=0 to Ebenen -1 do    
    begin
      SetLength(PasDreieck[i], i+1);             // Länge für jede Ebene um 1 erweitern
      PasDreieck[i,Low(PasDreiech[i])] := 1;                      // Eins am Anfang
      PasDreieck[i,high(PasDreieck[i])] := 1;    // Eins am Ende
    end;
end;

Wie man aus der Tabelle sehen kann, müssen wir erst ab der 3. Ebene anfangen zu rechnen - davor kommen nur unsere Einsen vor :wink:

Delphi-Quellcode:

for i:=2 to Ebene -1 do
  for j:=1 to High(PasDreieck[i]) -1 do
    begin
      PasDreieck[i,j] := PasDreieck[i-1,j-1] + PasDreieck[i-1, j];
    end;

Und das Array kannst du nun in welcher Form auch immer du willst ausgeben.

Delphi-Quellcode:

for i:=Low(PasDreieck) to High(PasDreieck) do
  for b:=Low(PasDreieck[i]) to High(PasDreieck[i]) do
    StringGrid1.Cells[i,b] := IntToStr(PasDreieck[i,b]);

Wäre z.B. eine von vielen Möglichkeiten

[Nintendo]

Hi,

habe einfach mal mit Copy und Paste den Code übernommen, aber Lazarus 0.9.29 stößt sich an der SetLength Anweisung.

Auf dem Lazarus 1.0.6 Rechner hab ich auch Delphi installiert. Deshalb möchte ich gerne wissen, warum FPC an dieser Stelle bockt?

Das nächste ist das Verständnis des Codes. Kann da mal bitte jemand Pseudocode posten? Ich habe das bisher so weit verstanden, das am Anfang das Minimalfeld und das Maximalfeld gleich 1 gesetzt werden Wenn nur ein Feld da, (oberste Ebene), dann wird nur dieses eine Feld gleich 1 gesetzt. in der nächsten Ebene wird zum auf das erste Feld folgenden Feld 1 addiert, wodurch sich der Wert 2 ergibt, aber danach hängt es bei mir. Die Logik sagt mir zwar, das diese Addition weiter fortgesetzt werden muss, aber ich kann das anhand des hier vorliegenden Quellcodes nicht nachvollziehen. Deshalb bitte ich um Pseudocode zur Klarstellung.

[lbccaleb]

Die Wiki sollte für Aufklärung sorgen:

http://de.wikipedia.org/wiki/Pascalsches_Dreieck

Edit. Achso, poste vllt. mal deinen Code von FPC. Dann kann man da vllt. auch helfen ;)

[MrMooed]

Hallo,

zunächst einmal möchten wir, dass unser Array wie ein Dreieck "geformt" ist - sprich, es gibt immer mehr Elemente, je höher die Ebene liegt. Dabei können wir gleich in das erste- bzw. letzte Element unsere '1' schreiben:

Delphi-Quellcode:

for i:=0 to Ebenen -1 do 
    begin
      SetLength(PasDreieck[i], i+1); // Länge für jede Ebene um 1 erweitern
      PasDreieck[i,Low(PasDreiech[i])] := 1; // Eins am Anfang
      PasDreieck[i,high(PasDreieck[i])] := 1; // Eins am Ende
    end;

Code:

Das pascalsche Dreieck ist eine Form der grafischen Darstellung der Binomialkoeffizienten, die auch eine einfache Berechnung dieser erlaubt. Sie sind im Dreieck derart angeordnet, dass jeder Eintrag die Summe der zwei darüberstehenden Einträge ist

Soll für uns heißen: durchlaufe alle leeren Felder und schreibe die Summe der beiden drüber liegenden Werte hinein:

Delphi-Quellcode:

for i:=2 to Ebene -1 do
  for j:=1 to High(PasDreieck[i]) -1 do
    begin
      PasDreieck[i,j] := PasDreieck[i-1,j-1] + PasDreieck[i-1, j];
    end;

Anbei noch ein kleines Bildchen, allerdings sehe ich gerade, dass es Wikipedia deutlich besser visualisiert als ich es könnte :lol:
/Edit: Die Farben geben an, welche Werte zu welchen Ergebnissen führen. (Die beiden braunen ergeben z.B. die braune 2)

[Sir Rufo]

Was ist denn mit so einem Konstrukt:

Delphi-Quellcode:

TPDNode = class
private
  FLeft, FRight : TPDNode;
  function GetValue : Integer;
public
  property Left : TPDNode read FLeft write FLeft;
  property Right : TPDNode read FRight write FRight;
  property Value : Integer read GetValue;
end;

function TPDNode.GetValue : Integer;
begin
  Result := 0;
  if Assigned( Left ) then
    Result := Result + Left.Value;
  if Assigned( Right ) then
    Result := Result + Right.Value;
  if Result = 0 then
    Result := 1;
end;

Diese passend verknotet und das Dreieck berechnet sich von selbst ;)

[BUG]

Zitat:

Zitat von Nintendo (Beitrag 1220474)

Deshalb möchte ich gerne wissen, warum FPC an dieser Stelle bockt?

Am Code von MrMooed ist etwas faul ... es sieht aus, als sollte ein Array von Arrays von Integern genutzt werden, es wird aber nur ein Arrays von Integern definiert.

Sieh erst einmal zu, dass du die Rechenvorschrift "verstehst". Dann können wir uns immer noch über Code unterhalten.

Und die Vorschrift ist einfach .. eine Zahl im pascalschen Dreieck ist:

• 1 (wenn sie die erste oder letzte in ihrer Zeile ist)
• die Summe der "beiden darüber liegenden" Zahlen (sonst)

Das war es schon :mrgreen:

[MrMooed]

Zitat:

Zitat von BUG (Beitrag 1220482)

Am Code von MrMooed ist etwas faul ... es sieht aus, als sollte ein Array von Arrays von Integern genutzt werden, es wird aber nur ein Arrays von Integern definiert.

:wall: :wall: :wall:
natürlich :oops: habe zwar 2D-Array geschrieben, aber im Code falsch definiert..

Delphi-Quellcode:

PasDreieck : Array of Array of Integer;

habe den Beitrag editiert

[Nintendo]

Hey, danke lbccaleb. Werde mir den Wikipedia Artikel erst mal vornehmen. Obwohl danach immer noch kein Code, bzw. nur der hier gepostete da ist, den ich ja verstehen will.

Ich kann gerne meinen Code hier posten, der mit FPC nicht läuft. Es ist der von MrMooed, von hier kopiert. Habe den in eine Unit gepackt. Hier ist sie:

Delphi-Quellcode:

unit UTriangle;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils; 

procedure PasDreieckHasPlanes(var Ebenen: Integer);
procedure BildeDreieck;
procedure AusgabeInTabelle;

implementation

var
  Ebene: Integer;
  PasDreieck: array of Integer;

procedure PasDreieckHasPlanes(var Ebenen: Integer);
var
  PasDreieck : Array of Integer;
  i, j : Integer;
begin
  Ebene := Ebenen;
  for i:=0 to Ebenen -1 do
    begin
      SetLength(PasDreieck[i], i+1); // Länge für jede Ebene um 1 erweitern
//An dieser Stelle in Lazarus Type mismatch
//liegt das an der falschen Array Definition (nur eindimensional dimensioniert?)
      PasDreieck[i,Low(PasDreiech[i])] := 1; // Eins am Anfang
      //hier Illegal Qualifier ( Folgefehler ? )
      PasDreieck[i,high(PasDreieck[i])] := 1; // Eins am Ende
    end;
end;

procedure BildeDreieck;
var i,j: Integer;
begin
  for i:=2 to Ebene -1 do
  for j:=1 to High(PasDreieck[i]) -1 do
    begin
      PasDreieck[i,j] := PasDreieck[i-1,j-1] + PasDreieck[i-1, j];
    end;
end;

procedure AusgabeInTabelle(tabelle: TStringGrid);
var i,b: Integer;
begin
  if Assigned(tabelle) then
  for i:=Low(PasDreieck) to High(PasDreieck) do
  for b:=Low(PasDreieck[i]) to High(PasDreieck[i]) do
    tabelle.Cells[i,b] := IntToStr(PasDreieck[i,b]);
end;

procedure AusgabeInMemo(memo: TMemo);
var i,b: Integer; Plane: String;
begin
  if Assigned(Memo) then
  for i:=Low(PasDreieck) to High(PasDreieck) do
  for b:=Low(PasDreieck[i]) to High(PasDreieck[i]) do
  begin
    Plane := IntToStr(PasDreieck[i]) + ' ';
    memo.Lines.Add(Plane);
  end;
end;

end.

//Im Formular:

procedure TForm1.btnApplyClick(Sender: TObject);
begin
  FPlanes := IntToStr(Edit1.Text); //Anzahl Ebenen
  PasDreieckHasPlanes(FPlanes);
  BildeDreieck;
  //Hier käme dann die Ausgabe des Pascalschen Dreiecks
end;

[Edit]:
Nach Anderung der Deklaration in Array of Array of Integer wird SetLenth so akzeptiert, aber der Error: Illegal qualifier bleibt bestehen.

Hab mir auch die .zip Datei von @lbccaleb runter geladen. Diesen Code werde ich in den nächsten Tagen studieren und dazu auch den Wikipediartikel studieren. Wenn dann noch Fragen übrig sind, melde ich mich eh wieder.

Aber es bleibt das seltsame Verhalten von Lazarus bei der Übersetzung des Codes von MrMooed. Was kapiert FPC da nicht?

.

[Nintendo]

Hallo,

habe mir die Wikipedia angeschaut und zusätzlich eine mathematische Formelsammlung.

So habe ich rausgefunden, daß (n über k) = (n*(n-1)*(n-2)*(n-k+1)/k! ist.

im Quelltext unten (aus dreieck_770.zip <Unit1.pas>) ist i aber nicht als i fakultät ersichtlich. Warum funktioniert die Rechnung dennoch. Was habe ich da übersehen?

Delphi-Quellcode:

function nuebk(n,k: integer): integer;
  var i: integer;
begin
  result := 1;
  for i := 1 to k do
    result := (n-i+1)*result div i; //ist i hier nicht einfach i statt i!???
end;

[gammatester]

Zitat:

Zitat von Nintendo (Beitrag 1220545)

im Quelltext unten (aus dreieck_770.zip <Unit1.pas>) ist i aber nicht als i fakultät ersichtlich. Warum funktioniert die Rechnung dennoch. Was habe ich da übersehen?

Nein, Du hast nichts übersehen. Mathematisch ist das alles korrekt, das i läuft halt durch die verschiedene Werte 1,2,... in Deiner Formel, wobei die Produkte im Zähler ((n*(n-1)*(n-2)*...*(n-k+1)) und im Nenner (1*2*...*k) von links nach rechts durchlaufen wird, also (((n div 1)*(n-1) div 2)* ...)

Das eigentlich Interessante ist etwas ganz anderes: Du mußt zeigen, daß Integer-Divisionen hier korrekt sind, d.h. Du mußt Dir klarmachen, daß alle Divisionen mit div ohne Rest aufgehen.

[lbccaleb]

Zitat:

Zitat von Sir Rufo (Beitrag 1220481)

Was ist denn mit so einem Konstrukt:

Delphi-Quellcode:

TPDNode = class
private
  FLeft, FRight : TPDNode;
  function GetValue : Integer;
public
  property Left : TPDNode read FLeft write FLeft;
  property Right : TPDNode read FRight write FRight;
  property Value : Integer read GetValue;
end;

function TPDNode.GetValue : Integer;
begin
  Result := 0;
  if Assigned( Left ) then
    Result := Result + Left.Value;
  if Assigned( Right ) then
    Result := Result + Right.Value;
  if Result = 0 then
    Result := 1;
end;

Diese passend verknotet und das Dreieck berechnet sich von selbst ;)

Wie genau kann man das dann verwenden?