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

Trójkąt Pascala 10 faktów

https://mattomatti.com/a26

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.

C++C#
Python
  1. def wypiszPascala(wierszy):
  2.   lista = [];
  3.   while (wierszy > 0):
  4.     for i in range(1, len(lista)):
  5.       lista[i] = lista[i] + lista[i - 1]
  6.     lista.append(1)
  7.     txt = "";
  8.     for x in range(0, int(wierszy/2)):
  9.       txt += "\t"
  10.     for a in enumerate(lista):
  11.       if (wierszy % 2 == 1):
  12.         txt += "  "
  13.       txt += str(a[1]) + "\t"
  14.     print(txt)
  15.     wierszy = wierszy - 1

(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: (8. - 9.) odpowiednim wcięciu, (10. - 13.) o wypisaniu wartości i przesunięciu następnej wartości, a dla (11. - 12.) co drugiego wiersza dodatkowo przesunięcie danych o połowę odstępu pomiędzy danymi. Na koniec (14.) dane zostają wypisane, a (15.) pozostała ilość wierszy zmniejszona.

Testowanie funkcji

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

C++C#
Python
  1. n = int(input("Ile wierszy wypisać?\n n = "));
  2. wypiszPascala(n);