Триъгълникът на Паскал – формула, модели и примери
Сара Чен
Какво представлява триъгълникът на Паскал?
Триъгълникът на Паскал е триъгълен масив от числа, последван от определен модел и връзка с реда преди него. Изобретен е от Блез Паскал. Този триъгълник започва с един елемент в първия ред. След това всеки ред започва и завършва с „1“.
История на триъгълника на Паскал
Китайската книга „Деветте глави за математическото изкуство” съдържа един от първите примери за триъгълника на Паскал. В допълнение, той съдържа някои от същите модели и качества, открити в триъгълниците днес.
Паскал беше един от няколкото души в Европа, които изучаваха триъгълника. Други математици са изследвали подобни триъгълни масиви от числа преди него.
Построяване на триъгълника на Паскал
Конструирането на триъгълника на Паскал е просто. Единственото нещо, което трябва да запомните е, че редът започва и завършва с 1. Правилото за останалите числа е следното:
За всеки ред r и колона c числото ще бъде сумата от колони c-1 и c от ред r-1.
Тук
- r = 3,4,5….
- n и c = 2,3,4,…r-1.
Ето стъпките за изграждане на триъгълника на Паскал:
Стъпка 1) Нека започнем с попълването на два реда.
Стъпка 2) Вторият елемент за третия ред е сумата от първото и второто число във втория ред.
Стъпка 3) Четвъртият ред започва с „1.“. Второто число е 3, което е сборът от 1 и 2 (маркирани в синьо).
Изображението по-долу показва как да попълните четвъртия ред:
Стъпка 4) Петият ред ще се състои от пет числа. Вече знаем модела за попълване на редовете от по-ранните стъпки.
Формула на триъгълника на Паскал – Биномен коефициент
Биномен коефициент е число, което изразява различни методи за избор на подмножество от k елемента от колекция от n елемента. Често се изписва като „C(n,k)“ или „n избира k“.
Биномиалният коефициент се определя като
"!" обозначава „факториела“.
п! = n.(n-1). (n-2)…3.2.1
Например,
5! = 5.4.3.2.1
= 120
И така, да кажем C(5,3) или 5 изберете 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Метод 1: Изграждане на триъгълника на Паскал от предишния ред
Стъпките в тази процедура са същите като тези в триъгълника на Паскал. Да кажем, че искаме да създадем триъгълник на Паскал до седем реда.
Стъпките за постигане на това са следните:
Стъпка 1) Започнете най-горния ред с „1“.
Стъпка 2) За реда “r”, елементът “c” ще бъде произведението на “c-1” и “c” числото на реда “r-1”.
Стъпка 3) Първото и последното число в реда винаги ще бъдат „1“.
Трябва да се придържаме към тези три лесни стъпки, за да създадем триъгълника на Паскал.
C++ Код на триъгълника на Паскал от предишния ред
#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
int numbers[n][n];
for (int row = 0; row < n; row++)
{
for (int col = 0; col <= row; col++)
{
if (col == 0 || col == row)
{
numbers[row][col] = 1;
}
else
{
numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
}
cout << numbers[row][col] << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printRow(n);
}
Изход:
How many rows: 7 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
Python Код на формулата на триъгълника на Паскал от предишния ред
def printRow(n):
numbers = [[0 for row in range(n)]
for col in range(n)
]
for row in range(len(numbers)):
for col in range(0, row+1):
if row == col or col == 0:
numbers[row][col] = 1
else:
numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]
print(numbers[row][col],end="\t")
print("\n")
n = int(input("How many rows: "))
printRow(n)
Примерен изход за триъгълника на Паскал:
How many rows: 7 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
Анализ на сложността
A двумерен масив е използван при изпълнението. Като се има предвид, че N е броят на редовете в триъгълника на Паскал. Това ще изисква Н2 единични пространства. Следователно O ще бъде пространствената сложност (N2).
Имаме два цикъла във функцията и всеки цикъл се изпълнява "N" пъти. Така че времевата сложност също е такава НА2) или времева сложност на квадрат.
Метод 2: Изграждане на триъгълника на Паскал чрез изчисляване на биномен коефициент
Можем просто да изведем числата на триъгълника на Паскал, използвайки биномния коефициент. Ето диаграмата:
Ето стъпките за изграждане на триъгълника на Паскал чрез изчисляване на бинома:
Стъпка 1) Най-горният ред ще бъде C(0,0). Използвайки горната формула за биномен коефициент, C(0,0) = 1. Защото 0! = 1.
Стъпка 2) За ред „i“ ще има общо „i“ елементи. Всеки елемент ще бъде изчислен C(n,r), където n ще бъде i-1.
Стъпка 3) Повторете стъпка 2 за броя редове, които искате за триъгълника на Паскал.
C++ Кодирайте триъгълника на Паскал с биномен коефициент
#include <iostream>
using namespace std;
int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}
int binomialCoefficient(int n, int r)
{
int result = 1;
if (r > n)
{
return -1;
}
result = factorial(n) / (factorial(r) * factorial(n - r));
return result;
}
void printPascalTriangle(int row)
{
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= i; j++)
{
cout << binomialCoefficient(i, j) << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "Enter row number: ";
cin >> n;
printPascalTriangle(n);
}
Изход:
Enter row number: 9 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
Python Кодирайте триъгълника на Паскал с биномен коефициент
def factorial(n):
result = 1
for i in range(1,n+1):
result*=i
return result
def binomialCoefficient(n,r):
result =1
if r>n:
return None
result = factorial(n) / (factorial(r) * factorial(n - r))
return int(result)
def printPascalTriangle(row):
for i in range(row+1):
for j in range(i+1):
print(binomialCoefficient(i, j), end="\t")
print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)
Примерен изход за триъгълника на Паскал:
Enter row number: 8 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
Анализ на сложността
При изпълнението са използвани три цикъла. Единият цикъл е за изчисляване на биномиалния коефициент, а другите два са за създаване на числа за всички редове. Що се отнася до броя на редовете, имаме три цикъла, които се изпълняват „n“ пъти. Следователно общата времева сложност ще бъде 0(n3).
Сложността на пространството вече е постоянна, защото не съхраняваме никакви данни в хранилището. Програмата изчислява елемента и той се отпечатва в ред. След това пространствената сложност намалява до 0(1).
Метод 3: Изграждане на триъгълника на Паскал чрез модифициран биномен коефициент
В предишната техника вече видяхме как да използваме биномен коефициент за изчисляване на всеки елемент от триъгълника на Паскал. Този подход ще определи C(n,r) от C. (n, r-1). Това ще опрости нещата с една поръчка.
Ето стъпките за изграждане на триъгълника на Паскал чрез модифициран биномен коефициент:
Стъпка 1) Започнете първия ред с „1“
Стъпка 2) Изчислете C(n,r), където "n" е номерът на реда и "r" е колоната или елемента. Задайте стойността в променлива C.
Стъпка 3) За изчисляване на C(n,k) ще бъде C*(nk)/k. Сега присвоете тази стойност на C.
Стъпка 4) Продължете стъпка 3, докато „k“ достигне края на реда. След всяка итерация увеличавайте стойността на K с единица.
C++ Код за триъгълника на Паскал чрез модифициран биномен коефициент
#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
for (int row = 1; row <= n; row++)
{
int previous_coef = 1;
for (int col = 1; col <= row; col++)
{
cout << previous_coef << "\t";
previous_coef = previous_coef * (row - col) / col;
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printpascalTriangle(n);
}
Изход:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python код за триъгълника на Паскал чрез модифициран биномен коефициент
def printpascalTriangle(n):
for row in range(1, n+1):
previous_coef = 1
for col in range(1, row+1):
print(previous_coef, end="\t")
previous_coef = int(previous_coef*(row-col)/col)
print()
n = int(input("How many rows: "))
printpascalTriangle(n)
Резултат от моделите на триъгълника на Паскал:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Анализ на сложността
Изпълнението има два цикъла. Всеки цикъл се изпълнява максимум "n" време, където "n" означава броя на редовете в паскал триъгълника. И така, времевата сложност е O(n2), време на квадрат.
Що се отнася до сложността на пространството, нямахме нужда от масив за съхранение. Току-що използвахме една променлива, за да запазим предишния биномен коефициент. Така че просто ни трябваше едно допълнително място. Космическата сложност стана O (1).
Приложение на триъгълника на Паскал
Ето някои приложения на триъгълника на Паскал:
Биномни разширения: Можем да определим коефициента на биномните разширения от триъгълника на Паскал. Ето един пример:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2и + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3и + 6x2y2 + 4xy3 + 1y4 |
Изчисляване на комбинации: Виждали сме, че елементи от триъгълника на Паскал са еквивалентни на биномни коефициенти. Например, ако имате 6 топки и сте били помолени да изберете 3 топки, това ще бъде 6C3. Или можете да намерите числото в 3-тия елемент на 6-ия ред от триъгълника на Паскал.
Интересни факти за триъгълника на Паскал
Ето някои факти, които ще намерите за интересни за триъгълника на Паскал:
- Сумата от всички елементи в ред винаги е степен на 2.
- Диагоналната сума на елементите на редовете генерира редицата на Фибоначи.
Oбобщение
- Триъгълникът на Паскал дава коефициентите за биномните разширения.
- Всеки ред от триъгълника на паскал започва и завършва с „1“. Междинните стойности са сумата от два елемента от предходния ред.
- Диагоналното събиране на всички елементи в триъгълника на Паскал ще ви даде Последователност на Фибоначи.
- Триъгълникът на Паскал също може да бъде генериран с биномни коефициенти.
