Pascali kolmnurk – valem, mustrid ja näited
Sarah Chen
Mis on Pascali kolmnurk?
Pascali kolmnurk on kolmnurkne arvude massiiv, millele järgneb konkreetne muster ja ühendus sellele eelneva reaga. Selle leiutas Blaise Pascal. See kolmnurk algab esimeses reas ühe elemendiga. Pärast seda algab ja lõpeb iga rida numbriga 1.
Pascali kolmnurga ajalugu
Hiina raamat “Üheksa peatükki matemaatilisest kunstist” sisaldab üht esimestest Pascali kolmnurga näidetest. Lisaks sisaldab see mõningaid samu mustreid ja omadusi, mida tänapäeval kolmnurkades leidub.
Pascal oli üks paljudest inimestest Euroopas, kes kolmnurka uuris. Teised matemaatikud olid enne teda uurinud sarnaseid kolmnurkseid arvude massiive.
Pascali kolmnurga ehitamine
Pascali kolmnurga konstrueerimine on lihtne. Ainus asi, mida peate meeles pidama, on see, et rida algab ja lõpeb 1-ga. Ülejäänud numbrite reegel on järgmine:
Iga rea r ja veeru c puhul on arv rea r-1 veergude c-1 ja c summa.
Siin
- r = 3,4,5….
- n ja c = 2,3,4,…r-1.
Siin on sammud Pascali kolmnurga loomiseks:
Step 1) Alustame kahe rea täitmisega.
Step 2) Kolmanda rea teine element on teise rea esimese ja teise numbri summa.
Step 3) Neljas rida algab tähega 1. Teine arv on 3, mis on 1 ja 2 summa (sinisega esile tõstetud).
Allolev pilt näitab, kuidas täita neljandat rida:
Step 4) Viies rida koosneb viiest numbrist. Me teame juba varasemate sammude järgi ridade täitmise mustrit.
Pascali kolmnurga valem – binoomkoefitsient
Binoomkoefitsient on arv, mis väljendab erinevaid meetodeid k elemendi alamhulga valimiseks n elemendist koosnevast kogumist. Sageli kirjutatakse see kui "C(n,k)" või "n vali k".
Binoomkoefitsient on määratletud kui
"!" tähistab "faktoriaalset".
n! = n.(n-1). (n-2)…3.2.1
Näiteks
5! = 5.4.3.2.1
= 120
Ütleme nii, et C(5,3) või 5 vali 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
1. meetod: Pascali kolmnurga ehitamine eelmise rea järgi
Selle protseduuri sammud on samad, mis Pascali kolmnurgas. Oletame, et tahame luua kuni seitsmerealise Pascali kolmnurga.
Selle täitmise sammud on järgmised:
Step 1) Alusta ülemist rida 1-ga.
Step 2) Rea "r" puhul on üksus "c" korrutis "c-1" ja "c" rea "r-1" number.
Step 3) Rea esimene ja viimane number on alati 1.
Pascali kolmnurga loomiseks peame järgima neid kolme lihtsat sammu.
C++ Pascali kolmnurga kood eelmise rea järgi
#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);
}
Väljund:
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 Pascali kolmnurga valemi kood eelmise rea järgi
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)
Pascali kolmnurga näidisväljund:
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
Keerukuse analüüs
A kahemõõtmeline massiiv rakendamisel kasutati. Arvestades, et N on Pascali kolmnurga ridade arv. Selleks on vaja N2 ühiku ruumid. Seetõttu on O ruumi keerukus (N2).
Funktsioonis on kaks tsüklit ja iga tsükkel jookseb "N" korda. Seega on ka ajaline keerukus PEAL2) või ruudus aja keerukus.
2. meetod: Pascali kolmnurga loomine binoomkoefitsiendi arvutamise teel
Me saame lihtsalt binoomkoefitsiendi abil tuletada Pascali kolmnurga arvud. Siin on diagramm:
Siin on sammud Pascali kolmnurga loomiseks binoomarvu arvutamise teel:
Step 1) Ülemine rida on C(0,0). Kasutades ülaltoodud valemit binoomkoefitsiendi jaoks, C(0,0) = 1. Kuna 0! = 1.
Step 2) Rea “i” puhul on “i” elemente kokku. Iga üksus arvutatakse C(n,r), kus n on i-1.
Step 3) Korrake 2. sammu Pascali kolmnurga jaoks soovitud ridade arvu jaoks.
C++ Kodeerige Pascali kolmnurk binoomkoefitsiendi järgi
#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);
}
Väljund:
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 Kodeerige Pascali kolmnurk binoomkoefitsiendi järgi
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)
Pascali kolmnurga näidisväljund:
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
Keerukuse analüüs
Rakendamisel kasutati kolme silmust. Üks tsükkel on mõeldud binoomkoefitsiendi arvutamiseks ja ülejäänud kaks kõigi ridade arvude loomiseks. Seoses ridade arvuga on meil kolm tsüklit, mis käivitavad "n" korda. Järelikult on üldine ajaline keerukus 0 (n3).
Ruumi keerukus on nüüd pidev, kuna me ei hoia andmeid salvestusruumis. Programm arvutab elemendi ja see trükitakse reas. Ruumi keerukus väheneb seejärel 0-ni (1).
3. meetod: Pascali kolmnurga koostamine modifitseeritud binoomkoefitsiendi järgi
Eelmises tehnikas oleme juba näinud, kuidas kasutada Pascali kolmnurga iga elemendi arvutamiseks binoomkoefitsienti. See lähenemisviis määrab C(n,r) väärtusest C. (n, r-1). See lihtsustab asju ühe tellimusega.
Siin on sammud Pascali kolmnurga loomiseks modifitseeritud binoomkoefitsiendi järgi:
Step 1) Alustage esimest rida 1-ga
Step 2) Arvutage C(n,r), kus "n" on rea number ja "r" on veerg või element. Määrake väärtus muutujas C.
Step 3) C(n,k) arvutamiseks on see C*(nk)/k. Nüüd määrake see väärtus C-le.
Step 4) Jätkake sammu 3, kuni "k" jõuab rea lõppu. Pärast iga iteratsiooni suurendage K väärtust ühe võrra.
C++ Pascali kolmnurga kood modifitseeritud binoomkoefitsiendi järgi
#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);
}
Väljund:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Pascali kolmnurga kood modifitseeritud binoomkoefitsiendiga
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)
Pascali kolmnurga mustrite väljund:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Keerukuse analüüs
Rakendusel on kaks silmust. Iga silmus jookseb maksimaalselt "n" aja, kus "n" tähendab ridade arvu pascali kolmnurgas. Niisiis, ajaline keerukus on Peal2), ruudus aeg.
Mis puudutab ruumi keerukust, siis me ei vajanud salvestamiseks massiivi. Eelmise binoomkoefitsiendi säilitamiseks kasutasime lihtsalt ühte muutujat. Seega vajasime lihtsalt ühte lisaruumi. Ruumi keerukus muutus O (1).
Pascali kolmnurga rakendamine
Siin on mõned Pascali kolmnurga rakendused:
Binoomlaiendused: Binoomlaienduste koefitsiendi saame määrata Pascali kolmnurgast. Siin on näide:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2ja + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3ja + 6x2y2 + 4xy3 + 1y4 |
Kombinatsioonide arvutamine: Oleme näinud, et Pascali kolmnurga elemendid on samaväärsed binoomkoefitsientidega. Näiteks kui teil on 6 palli ja teil on palutud valida 3 palli, siis see nii on 6C3. Või leiate numbri Pascali kolmnurga 3. rea 6. elemendist.
Huvitavad faktid Pascali kolmnurga kohta
Siin on mõned faktid, mis Pascali kolmnurga kohta huvitavad:
- Kõikide reas olevate elementide summa on alati 2 aste.
- Ridade elementide diagonaalselt summa genereerib Fibonacci jada.
kokkuvõte
- Pascali kolmnurk annab binoomlaienduste koefitsiendid.
- Pascali kolmnurga iga rida algab ja lõpeb numbriga 1. Vaheväärtused on eelmise rea kahe elemendi summa.
- Pascali kolmnurga kõigi elementide diagonaalne liitmine annab teile Fibonacci järjestus.
- Pascali kolmnurga saab genereerida ka binoomkoefitsientidega.
