Strona główna » Algorytmy » Artykuły » Trójkąt Pascala 10 faktów
 

Trójkąt Pascala 10 faktów

Historia

1.1
2.11
3.121
4.1331
5.14641
6.15101051

Trójkąt Pascala zadziwia pod wieloma względami. Został tak nazwany na cześć Blaise Pascala'a, którym był sławnym francuskim matematykiem i filozofem.

Jak się go tworzy?

Własność #1

Każda linijka ma dokładnie tyle samo elementów co numer wiersza. Trójkąt Pascala zaczynamy zawsze od 1. Każdy następny element to suma elementu do góry na lewo i na prawo. W przypadku, gdy jakiś element nie istnieje (dotyczy to skrajnych elementów każdego rzędu) to jego wartość wynosi 0.

Własność #2

n-ta linijka trójkąta to kolejny liczby z rozwinięcia

Przykładowo weźmy pod uwagę linijkę numer 3:

Elementy

1.1
2.11
3.121
4.1331
5.14641
6.15101051

Własność #3

Pierwszy element w każdym wierszu to jeden.

Własność #4

Drugi element w każdym wierszu to kolejne liczby. tj. 1, 2, 3, 4, 5, 6, ...

Własność #5

Trzeci element w każdym wierszu to kolejny liczby liczby trójkątne. Kolejne liczby trójkątne graficznie można przedstawić jako trójkąt. Wzór na n-tą liczbę trójkątną to

Własność #6

Czwarty element w każdym wierszu to kolejne liczby czworościenne. Kolejne liczby czworościenne to ilość kulek, które są potrzebne do wypełnienia czworościan foremny. Wzór na n-tą liczbę czworościenną to

Własność #7

n-ty element to kolejne liczby, które można ustawić w ciąg.

Wiersze

1.1= 1
2.11= 2
3.121= 4
4.1331= 8
5.14641= 16
6.15101051= 32

Własność #8

Suma n-tego wiersza to n-ta potęga 2. Można to udowodnić z tego powodu, że pierwszy wyraz to an, a ostatni bn, bo jest to rozwinięcie (a + b)n. Pierwsz i ostatni wyraz to zawsze 1, więc suma wiersza to (1 + 1)n = 2n.

Własność #9

Jeśli zamalujemy wszystkie liczby parzyste to trójkąt Pascala zacznie przypominać trójkąt Sierpińskiego

Dowolny drugi element z n-tego wiersza podniesiony do kwadratu równa się sumie elementu na prawo i elementu na prawo i w dół. Przykładowo . Spróbujmy udowodnić tę własność:

Wypisywanie trójkąta

Algorytm

W celu wygenerowania kolejnych wartości trójkąta Pascala należy wykonać następujący algorytm. Na początku niech lista wartości będzie pusta. W celu wygenerowania nowego wiersza należy dla każdej kolejnej pary liczb od prawej do lewej wykonać aktualizację, że i-ty element jest sumą i-tego elementu oraz elementu o indeksie i - 1. Po zakończeniu sumowania należy dopisać na koniec listy wartość 1.

Przykład

Początkowo lista jest pusta. Dla pierwszego i drugiego wiersza nie jest wykonane, żadne sumowanie, a jedynie dopisywane są jedynki. Dla trzeciego wiersza lista to {1, 1}, więc wykonanie zostanie jedno sumowanie 1 + 1 = 2 i zostanie wstawione zamiast drugiego elementu. Na koniec zostanie na koniec dopisana wartość 1. W ten sposób powstają wartości z trzeciego wiersza {1, 2, 1}. W tabelce poniżej zostały przedstawione kolejne aktualizacje listy:

Wiersz
11----
211---
3121--
41331-
514641

Przypatrując się powyższej tabelki należy pamiętać, że w każdym wierszu ostatnia wartość 1 została dołączona po sumowaniu, a każda wartość prócz pierwszej i ostatniej w rzędzie to suma elementu nad tą wartością i elementu obok tego nad.

Rozwiązanie

Poniżej została przedstawiona funkcja wypiszPascala(), która akceptuje jeden argument wierszy. Określa on ile wierszy ma mieć wypisany trójkąt Pascala.

  1. static void wypiszPascala(int wierszy) {
  2.   List<int> lista = new List<int>();
  3.   while (wierszy-- > 0) {
  4.     for (int i = lista.Count - 1; i > 0; i--)
  5.       lista[i] = lista[i] + lista[i - 1];
  6.     lista.Add(1);
  7.     for (int i = wierszy / 2; i > 0; i--)
  8.       Console.Write("\t");
  9.     foreach(int a in lista) {
  10.       if (wierszy % 2 == 1)
  11.         Console.Write(" ");
  12.       Console.Write("{0}\t", a);
  13.     }
  14.     Console.WriteLine();
  15.   }
  16. }

(2.) Przygotuj listę do zapisu danych, a następnie (3.) rozpocznij wykonywanie wskazanej ilości powtórzeń. W każdej iteracji (4. - 6.) zaktualizuj wartości wiersza. W celu wypisania w postaci wyglądu należy pamiętać o: (7. - 8.) odpowiednim wcięciu, (9. - 13.) o wypisaniu wartości i przesunięciu następnej wartości, a dla (10. - 11.) co drugiego wiersza dodatkowo przesunięcie danych o połowę odstępu pomiędzy danymi. Na koniec (12.) należy oczywiście przejść do nowej linii.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:

  1. static void Main(string[] args) {
  2.   Console.Write("Ile wierszy wypisać?\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   wypiszPascala(n);
  5.   Console.ReadKey();
  6. }