Pascal'sches Dreieck

1. Aufgabe

Das Pascalsche Dreieck ist eine Anordnung von Zahlen in Dreiecksform, die sich nach einer einfachen Regel berechnen lassen. Blaise Pascal (1623 - 1662) hat dieses Zahlendreieck zwar nicht entdeckt – es war schon den Chinesen als Chu Shun Chiehs Dreieck bekannt–, aber als erster systematisch untersucht. Das Bildungsgesetz für ein Pascalsches Dreieck sieht so aus: In der ersten Reihe steht eine Eins, in der zweiten zwei Einsen. In allen weiteren Reihen ist jeweils die erste und letzte Zahl eine Eins. Alle anderen Zahlen innerhalb der Reihe erhält man, indem man jeweils die beiden darüberstehenden Zahlen addiert. Das Dreieck kann folglich nach unten beliebig weit fortgesetzt werden:

                                    1 
                                 1     1
                              1     2     1
                           1     3     3     1 
                        1     4     6     4     1 
                     1     5    10    10     5     1 
                  1     6    15    20    15     6     1 
               1     7    21    35    35    21     7     1 
            1     8    28    56    70    56    28     8     1 
         1     9    36    84   126   126    84    36     9     1 
      1    10    45   120   210   252   210   120    45    10     1 
   1    11    55   165   330   462   462   330   165    55    11     1 
1    12    66   220   495   792   924   792   495   220    66    12     1
                                  ...

Erstellen Sie eine Klasse PascalTriangle mit einer Methode Compute, die in Abhängigkeit von der Zeilenanzahl alle Reihen des Pascal'schen Dreiecks brechnet.

2. Lösung

Ein Anwendungsbeispiel zur Klasse PascalTriangle finden Sie im Anschluss von Listing 1 vor:

01: class PascalTriangle
02: {
03:     private int level;
04:     private int[][] triangle;
05: 
06:     public PascalTriangle ()
07:     {
08:         this.level = 0;
09:     }
10: 
11:     // properties
12:     public int Level
13:     {
14:         get
15:         {
16:             return this.level;
17:         }
18:     }
19: 
20:     // public interface
21:     public void Compute( int level)
22:     {
23:         this.level = level;
24:         this.triangle = new int[this.level][];
25:         for (int i = 0; i < this.triangle.Length; i++)
26:         {
27:             // allocate row
28:             int[] row = new int[i+1];
29: 
30:             // initialize edges
31:             row[0] = 1;
32:             row[i] = 1;
33: 
34:             // calculate binomial coefficients
35:             for (int j = 1; j < i; j++)
36:                 row[j] = this.triangle[i-1][j-1] + this.triangle[i-1][j];
37: 
38:             // enter row into top-level array
39:             this.triangle[i] = row;
40:         }
41:     }
42: 
43:     // indexer
44:     public int this [int n, int m]
45:     {
46:         get
47:         {
48:             return this.triangle[n][m];
49:         }
50:     }
51: 
52:     // overrides
53:     public override String ToString()
54:     {
55:         String s = "";
56:         for (int i = 0; i < this.triangle.Length; i++)
57:         {
58:             s += this.Indentation(i);
59: 
60:             String formatString =
61:                 String.Concat("{0,", this.NumberOfDecimalPlaces, ":D}"); 
62:             
63:             for (int j = 0; j < this.triangle[i].Length; j++)
64:                 s += String.Format(formatString, this.triangle[i][j]);
65: 
66:             s += Environment.NewLine;
67:         }
68: 
69:         return s;
70:     }
71: 
72:     // private helper methods
73:     private int NumberOfDecimalPlaces
74:     {
75:         // should be even for a symmetric visualization
76:         get
77:         {
78:             if (this.level <= 5)
79:                 return 2;
80:             else if (this.level <= 13)
81:                 return 4;
82:             else
83:                 return 6;
84:         }
85:     }
86: 
87:     private String Indentation(int row)
88:     {
89:         int numOfBlanks = this.NumberOfDecimalPlaces / 2;
90: 
91:         String s = "";
92:         for (int i = 0; i < this.triangle.Length - row - 1; i++)
93:              for (int j = 0; j < numOfBlanks; j++)
94:                 s = s + " ";
95: 
96:         return s;
97:     }
98: }

Beispiel 1. Die Klasse PascalTriangle.


Testrahmen:

public static void Main()
{
    PascalTriangle pascal = new PascalTriangle();
    for (int i = 1; i <= 20; i += 5)
    {
        pascal.Compute(i);

        Console.WriteLine("Level: {0}", pascal.Level);
        Console.WriteLine(pascal);
        Console.WriteLine();
    }
}

Ausgabe:

Level: 1
 1


Level: 6
             1
           1   1
         1   2   1
       1   3   3   1
     1   4   6   4   1
   1   5  10  10   5   1


Level: 11
                       1
                     1   1
                   1   2   1
                 1   3   3   1
               1   4   6   4   1
             1   5  10  10   5   1
           1   6  15  20  15   6   1
         1   7  21  35  35  21   7   1
       1   8  28  56  70  56  28   8   1
     1   9  36  84 126 126  84  36   9   1
   1  10  45 120 210 252 210 120  45  10   1


Level: 16
                                                  1
                                               1     1
                                            1     2     1
                                         1     3     3     1
                                      1     4     6     4     1
                                   1     5    10    10     5     1
                                1     6    15    20    15     6     1
                             1     7    21    35    35    21     7     1
                          1     8    28    56    70    56    28     8     1
                       1     9    36    84   126   126    84    36     9     1
                    1    10    45   120   210   252   210   120    45    10     1
                 1    11    55   165   330   462   462   330   165    55    11     1
              1    12    66   220   495   792   924   792   495   220    66    12     1
           1    13    78   286   715  1287  1716  1716  1287   715   286    78    13     1
        1    14    91   364  1001  2002  3003  3432  3003  2002  1001   364    91    14     1
     1    15   105   455  1365  3003  5005  6435  6435  5005  3003  1365   455   105    15     1