Aus Das deutschsprachige Scratch-Wiki

 
(10 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{unfertig}}
+
Blaise Pascal war ein französischer Mathematiker und Physiker. Er lebte 1623 bis 1662 und war sehr vielseitig. Einmal beschäftigte er sich mit der Frage, wie der Einsatz eines Glückspiels zwischen zwei gleichwertigen Partnern bei vorzeitigem Abbruch des Spieles aufzuteilen ist.
 +
Die ist gleichbedeutend mit der Frage, wieviele Möglichkeiten es gibt, aus einer Schublade mit Socken Paare von Socken zu ziehen. Oder auch wieviele verschiedene Ziehungsergebnisse es beim Lotto ("6 aus 45", "6 aus 49", etc.) gibt.
 +
Bei der Berechnung dieser Anzahlen stellte er fest, dass diese in einem Zahlendreieck zu finden sind, das schon sehr lange bekannt war
 +
(die alten Chinesen nannten es Chu Shun Chiehs Dreieck, in Persien ist es als Chayyam-Dreieck bekannt), aber in Folge nach Blaise Pascal '''Pascalsches Dreieck''' genannt wurde.
 +
 
 
[[Datei:PascalschesDreieckAnimation.gif|thumb|right|260px]]
 
[[Datei:PascalschesDreieckAnimation.gif|thumb|right|260px]]
Das Pascalsche Dreieck ist ein Dreieck, in dem Zahlen stehen. Das Dreieck ist in Kästchen aufgeteilt, die immer zur Hälfte unter einem Kästchen und zur anderen Hälfte unter einem anderen Kästchen stehen. Dabei gilt: Die Zahl in einem Kästchen ist die Summe der zwei darüberliegenden Zahlen. Grundsätzlich wird das Pascalsche Dreieck zur schnellen Berechnung des ''Binomialkoeffizienten'' benutzt, aber weil das zu kompliziert ist, wird hier beschrieben, welche Muster erzeugt werden können wenn man das Pascalsche Dreieck nutzt.
+
Die erste und letzte Zahl jeder Reihe ist 1; die übrigen Zahlen erhält man, indem man jeweils die beiden darüberstehenden Zahlen addiert.
 +
 
 +
 
 +
Gut, jetzt weiß man, wieviele verschiedene Ergebnisse es bei der Ziehung der Lottozahlen "6 aus 45" gibt. Dazu muss man in der 46. Zeile die 7. Zahl ablesen (man beginnt immer mit 0 zu zählen). Dort steht 8145060. (Da aber immer auch eine "Zusatzzahl" gezogen wird, gibt es eigentlich 45379620 Ergebnisse. - In der 46. Zeile die 8. Zahl, eh klar.) Für das Lotto "2 aus 4" lässt sich das in der Grafik rechts ablesen: In der 5. Zeile an der 3. Stelle steht 6.
  
== Namensherkunft ==
+
Aber hat das Pascalsche Dreieck auch für Kinder irgendeine Bedeutung? Ja!
Das pascalsche Dreieck war jedoch schon früher bekannt und wird deshalb auch heute noch nach anderen Mathematikern benannt. In China spricht man vom Yang-Hui-Dreieck (nach Yang Hui), in Italien vom Tartaglia-Dreieck (nach Nicolo Tartaglia) und im Iran vom Chayyām-Dreieck (nach Omar Khayyām).
+
Das Spannende am Pascalschen Dreieck ist nämlich, wenn man sich anschaut, welche Zahlen im Dreieck durch eine bestimmte Zahl teilbar sind (also ohne Rest dividiert werden können).
 +
Das erste Beispiel unten zeichnet solche Dreiecke. Für eine Eingabe von 2 ensteht das "Sierpinski-Dreieck".
  
== Tricks ==
 
Mit dem Dreieck kann man viele Tricks machen. Mit Addition kann man beispielsweise Zweierpotenzen oder die Fibonacci-Zahlen errechnen. Und mit Prüfung der Teilbarkeit interessante Muster erzeugen.
 
  
=== Zweierpotenzen ===
+
=== Beispiele ===
Die Zweierpotenzen erhält man, wenn man die Zahlen einer kompletten Zeile zusammenrechent.
+
{|style="text-align: center;" border=1
 +
|-
 +
|{{SBildlink|user=Leo2nardo|nr=245768328|name=Pascalsches Dreieck}}
 +
|{{SBildlink|user=webdesigner97|nr=2015915|name=Pascal's Triangle for Kids}}
 +
|}
  
=== Fibonacci-Zahlen ===
 
[[Datei:PascalschesDreieckFibonacci.gif|thumb|right|400px]]
 
Die Fibonnaci-Zahlen erhält man, wenn man Diagonal von oben rechts nach unten links die Zahlen addiert.
 
  
=== Prüfung der Teilbarkeit ===
+
=== weiterführende Informationen ===
Probiere es doch einfach mal selbst aus! Nimm dir ein Blatt Papier und male das Pascalsche Dreieck mitsamt den Zahlen darauf. Dann suche dir eine Zahl aus, z.B. 5, und male alle Kästchen, dessen Zahlen durch 5 teilbar sind, grün an. Du wirst ein sehr interessantes Muster erkennen.
+
Das Pascalsche Dreeick hat noch eine andere Bedeutung: In jeder Zeile stehen die ''Binomialkoeffizienten'', das heißt die Koeffizienten der Einzelterme, die entstehen, wenn man Potenzen von Binomen berechnet.<br>
 +
(a+b)<sup>0</sup> = 1<br>
 +
(a+b)<sup>1</sup> = 1a + 1b<br>
 +
(a+b)<sup>2</sup> = 1a<sup>2</sup> + 2ab + b<sup>2</sup><br>
 +
(a+b)<sup>3</sup> = 1a<sup>3</sup> + 3a<sup>2</sup>b + 3ab<sup>2</sup> + 1b<sup>3</sup><br>
 +
(a+b)<sup>4</sup> = 1a<sup>4</sup> + 4a<sup>3</sup>b + 6a<sup>2</sup>b<sup>2</sup> + 4ab<sup>3</sup> + 1b<sup>4</sup>
  
'''Wie man so etwas programmiert:'''<br />
+
Für so etwas benötigt es zwei Dinge: Erstmal müssen die Zahlen überhaupt generiert werden und zweitens, muss die Pyramide gemalt werden.  
+
Es gibt auch eine explizite Formel zur Berechnung: Die Zahl in der n-ten Zeile und der k-ten Stelle (die Zählung beginnt jeweils mit 0) lautet
 +
[[Datei:Formel_Binominalkoeffizienten.png|thumb|left|200px]]
 +
Wobei n! "n Fakultät" gesprochen und als Produkt aller natürlichen Zahlen kleiner gleich n berechnet wird, also n! = n * (n-1) * (n-2) * ... * 1.
 +
Ein Beispiel: 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800
  
Um die Zahlen zu generieren, sollte man eine Liste erstellen. In dieser Liste sind dann die Zahlen der Pyramide nacheinander aufgelistet sind. In welcher Reihenfolge, ist egal. In dem Beispielskript wird die Reihenfolge verwendet, bei der der erste Eintrag das Kästchen ganz unten links ist, der zweite das Kästchen rechts daneben, der dritte das rechts neben dem Kästchen des zweiten Eintrags u.s.w. Wenn man dann bei dem letzten Kästchen in der untersten Reihe angekommen ist, geht es mit dem ganz linken Kästchen in der Reihe darüber weiter. Nach dieser Methode sind die Einträge bei einer Pyramide mit 5 Kästchen in der untersten Reihe: 1, 4, 6, 4, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 1<br />
+
Da die Fakultäts-Funktion rasant an die Grenzen der Berechenbarkeit gelangt, ist die einzige Möglichkeit, Binominalkoeffizienten zu berechnen,
 +
in jedem Schritt zu multiplizieren und zu dividieren, um die Zahlen klein zu halten.<br>
 +
Man sieht auch anhand des Pascalschen Dreiecks: Die linke Seite und die rechte Seite sind symmetrisch. Also kann man, wenn k größer als n/2,
 +
statt Binominalkoeffizient(n,k) den weniger rechenaufwändigen Binominalkoeffizient(n,n-k) berechnen.
  
 
<scratchblocks>
 
<scratchblocks>
Wenn gf angeklickt
+
Definiere Binominalkoeffizient (n) über (k)
lösche (alles v) aus [Zahlen v]
+
setze [Ergebnis v] auf [1]
wiederhole (3) mal
+
falls <(k) > [0]> dann
füge [1] zu [Zahlen v] hinzu
+
falls <((2) * (k)) > (n)> dann
end
+
setze [k v] auf ((n) - (k))
setze [index2 v] auf [2]
+
setze [n-k v] auf (k)
wiederhole ((KästchenUntersteReihe) - (2)) mal
+
sonst
lösche (alles v) aus [AktuelleZahlen v]
+
setze [k v] auf (k)
setze [index3 v] auf [1]
+
setze [n-k v] auf ((n) - (k))
wiederhole (index2) mal
+
ende
füge (Element (index3) von [Zahlen v]) als (1 v) in [AktuelleZahlen v] ein
+
setze [i v] auf [1]
ändere [index3 v] um (1)
+
wiederhole bis <(i) > (k)>
end
+
setze [Ergebnis v] auf ((Ergebnis) * (((n-k) + (i)) / (i)))
lösche (alles v) aus [BerechneteZahlen v]
+
ändere [i v] um (1)
setze [index v] auf [1]
+
ende
füge [1] zu [BerechneteZahlen v] hinzu
+
ende
wiederhole ((Länge von [AktuelleZahlen v]) - (1)) mal
 
füge ((Element (index) von [AktuelleZahlen v]) + (Element ((index) + (1)) von [AktuelleZahlen v])) zu [BerechneteZahlen v] hinzu
 
ändere [index v] um (1)
 
end
 
füge [1] zu [BerechneteZahlen v] hinzu
 
setze [index4 v] auf (Länge von [BerechneteZahlen v])
 
wiederhole (Länge von [BerechneteZahlen v]) mal
 
füge (Element (index4) von [BerechneteZahlen v]) als (1 v) in [Zahlen v] ein
 
ändere [index4 v] um (-1)
 
end
 
ändere [index2 v] um (1)
 
end
 
 
</scratchblocks>
 
</scratchblocks>
  
''Notiz: Die Variable KästchenUntersteReihe beinhaltet die Anzahl der Kästchen in der untersten Reihe. Die Variable wurde nur erzeugt, um die Größe der Pyramide zu ändern ohne in den Quellcode eingreifen zu müssen. Wenn die Pyramide immer gleich groß sein soll, kann die Variable auch durch einen konstanten Wert ersetzt werden.''
+
[[Kategorie:Algorithmen und Datenstrukturen]]
 
+
{{en}}
Zuerst wird alles zurückgesetzt und die ersten drei Zahlen eingefügt: 1, 1 und 1. Dann wird index2 auf 2 gesetzt, weil die Reihe, aus der die dritte Reihe berechnet werden soll, 2 Kästchen beinhaltet. Dann wird KästchenUntersteReihe - 2 mal die nächste Reihe berechnet. Warum -2? die ersten zwei Reihen wurden schon generiert mit den drei Einsen in der Liste (Falls die Variable KästchenUntersteReihe weggelassen wurde, muss hier natürlich ein Wert, z.B. 20 eingefügt werden). Die Reihe wird so generiert: Zuerst wird die Liste "AktuelleZahlen", in der sich die Zahlen aus der die nächste Reihe berechnet wird befinden vollständig geleert damit wieder mit der neuen Reihe angefangen werden kann. Dann wird mithilfe von index2 die Liste wieder mit den nötigen Zahlen gefüllt (Der Index dazu ist index3, nur zur Info damit keine Verwirrung entsteht). Ist das geschehen, wird die Liste "BerechneteZahlen" geleert, damit dort die neuen, berechneten Zahlen eingefügt werden können. Und schon fängt es an: Die ersten zwei Einträge der Liste AktuelleZahlen werden addiert und in die Liste BerechneteZahlen eingefügt. Dannach geht es einen weiter und die eine neue Zahl und die eine alte wird addiert und eingefügt (in "BerechneteZahlen"). So geht es weiter bis die ganze Liste AktuelleZahlen abgearbeitet ist. Vor und nach dieser Prozedur wird eine 1 in BerechneteZahlen eingefügt, weil der Computer nicht weiß bzw. es schwierig zu programmieren wäre ihm verstehen zu geben, dass keine Eintrag als 0 gewertet werden soll. Deshalb kann er nicht die erste und die letzte 1 von der vorherigen Reihe mit ''Nichts'' addieren (Nichts meint einen Bereich außerhalb der Pyramide, der nicht in der Liste enthalten ist). Der Rest ist nicht wirklich der Rede wert. Die Zahlen in BerechneteZahlen werden umgekehrt als ersten Eintrag in Zahlen kopiert (damit die ganzen Zahlen nicht als letzte Einträge in Zahlen zu finden sind, sondern als erste aber die Reihenfolge der Einträge in BerechneteZahlen trotzdem dieselbe bleibt). Und zu guter Letzt wird index2 (die Anzahl der Kästchen in der Reihe vor der Reihe, dessen Zahlen gerade berechnet werden) um 1 erhöht, weil ja die nächste Reihe logischerweise ein Kästchen mehr hat.
 
 
 
Damit kommen wir zum Malen der Pyramide.<br />
 
 
 
[[Kategorie:Tutorials]]
 

Aktuelle Version vom 12. September 2018, 19:40 Uhr

Blaise Pascal war ein französischer Mathematiker und Physiker. Er lebte 1623 bis 1662 und war sehr vielseitig. Einmal beschäftigte er sich mit der Frage, wie der Einsatz eines Glückspiels zwischen zwei gleichwertigen Partnern bei vorzeitigem Abbruch des Spieles aufzuteilen ist. Die ist gleichbedeutend mit der Frage, wieviele Möglichkeiten es gibt, aus einer Schublade mit Socken Paare von Socken zu ziehen. Oder auch wieviele verschiedene Ziehungsergebnisse es beim Lotto ("6 aus 45", "6 aus 49", etc.) gibt. Bei der Berechnung dieser Anzahlen stellte er fest, dass diese in einem Zahlendreieck zu finden sind, das schon sehr lange bekannt war (die alten Chinesen nannten es Chu Shun Chiehs Dreieck, in Persien ist es als Chayyam-Dreieck bekannt), aber in Folge nach Blaise Pascal Pascalsches Dreieck genannt wurde.

PascalschesDreieckAnimation.gif

Die erste und letzte Zahl jeder Reihe ist 1; die übrigen Zahlen erhält man, indem man jeweils die beiden darüberstehenden Zahlen addiert.


Gut, jetzt weiß man, wieviele verschiedene Ergebnisse es bei der Ziehung der Lottozahlen "6 aus 45" gibt. Dazu muss man in der 46. Zeile die 7. Zahl ablesen (man beginnt immer mit 0 zu zählen). Dort steht 8145060. (Da aber immer auch eine "Zusatzzahl" gezogen wird, gibt es eigentlich 45379620 Ergebnisse. - In der 46. Zeile die 8. Zahl, eh klar.) Für das Lotto "2 aus 4" lässt sich das in der Grafik rechts ablesen: In der 5. Zeile an der 3. Stelle steht 6.

Aber hat das Pascalsche Dreieck auch für Kinder irgendeine Bedeutung? Ja! Das Spannende am Pascalschen Dreieck ist nämlich, wenn man sich anschaut, welche Zahlen im Dreieck durch eine bestimmte Zahl teilbar sind (also ohne Rest dividiert werden können). Das erste Beispiel unten zeichnet solche Dreiecke. Für eine Eingabe von 2 ensteht das "Sierpinski-Dreieck".


Beispiele

245768328_144x108.png

Pascalsches Dreieck

2015915_144x108.png

Pascal's Triangle for Kids


weiterführende Informationen

Das Pascalsche Dreeick hat noch eine andere Bedeutung: In jeder Zeile stehen die Binomialkoeffizienten, das heißt die Koeffizienten der Einzelterme, die entstehen, wenn man Potenzen von Binomen berechnet.
(a+b)0 = 1
(a+b)1 = 1a + 1b
(a+b)2 = 1a2 + 2ab + b2
(a+b)3 = 1a3 + 3a2b + 3ab2 + 1b3
(a+b)4 = 1a4 + 4a3b + 6a2b2 + 4ab3 + 1b4


Es gibt auch eine explizite Formel zur Berechnung: Die Zahl in der n-ten Zeile und der k-ten Stelle (die Zählung beginnt jeweils mit 0) lautet

Formel Binominalkoeffizienten.png

Wobei n! "n Fakultät" gesprochen und als Produkt aller natürlichen Zahlen kleiner gleich n berechnet wird, also n! = n * (n-1) * (n-2) * ... * 1. Ein Beispiel: 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800

Da die Fakultäts-Funktion rasant an die Grenzen der Berechenbarkeit gelangt, ist die einzige Möglichkeit, Binominalkoeffizienten zu berechnen, in jedem Schritt zu multiplizieren und zu dividieren, um die Zahlen klein zu halten.
Man sieht auch anhand des Pascalschen Dreiecks: Die linke Seite und die rechte Seite sind symmetrisch. Also kann man, wenn k größer als n/2, statt Binominalkoeffizient(n,k) den weniger rechenaufwändigen Binominalkoeffizient(n,n-k) berechnen.

Definiere Binominalkoeffizient (n) über (k)
setze [Ergebnis v] auf [1]
falls <(k) > [0]> dann
falls <((2) * (k)) > (n)> dann
setze [k v] auf ((n) - (k))
setze [n-k v] auf (k)
sonst
setze [k v] auf (k)
setze [n-k v] auf ((n) - (k))
ende
setze [i v] auf [1]
wiederhole bis <(i) > (k)>
setze [Ergebnis v] auf ((Ergebnis) * (((n-k) + (i)) / (i)))
ändere [i v] um (1)
ende
ende

Code zum Einbinden ins Forum:
[wiki=de:Pascalsches Dreieck]Pascalsches Dreieck[/wiki]

Kategorie:En-Link

Cookies helfen uns bei der Bereitstellung von Das deutschsprachige Scratch-Wiki. Durch die Nutzung von Das deutschsprachige Scratch-Wiki erklärst du dich damit einverstanden, dass wir Cookies speichern.