Pascalin kolmio – kaava, kuviot ja esimerkit
Mikä on Pascalin kolmio?
Pascalin kolmio on kolmion muotoinen joukko numeroita, joita seuraa tietty kuvio ja yhteys sitä edeltävään riviin. Sen keksi Blaise Pascal. Tämä kolmio alkaa yhdellä elementillä ensimmäisellä rivillä. Sen jälkeen jokainen rivi alkaa ja päättyy numeroon 1.
Pascalin kolmion historia
Kiinalainen kirja "The Nine Chapters on the Mathematical Art" sisältää yhden ensimmäisistä esimerkeistä Pascalin kolmiosta. Lisäksi se sisältää joitain samoja kuvioita ja ominaisuuksia, joita löytyy nykyään kolmioista.
Pascal oli yksi monista ihmisistä Euroopassa, joka tutki kolmiota. Muut matemaatikot olivat tutkineet samanlaisia kolmiomaisia lukujonoja ennen häntä.
Pascalin kolmion rakentaminen
Pascalin kolmion rakentaminen on yksinkertaista. Ainoa asia, joka sinun on muistettava, on, että rivi alkaa ja päättyy numeroon 1. Muiden numeroiden sääntö on seuraava:
Minkä tahansa rivin r ja sarakkeen c luku on rivin r-1 sarakkeiden c-1 ja c summa.
Täällä
- r = 3,4,5….
- n ja c = 2,3,4,…r-1.
Tässä on vaiheet Pascalin kolmion rakentamiseen:
Vaihe 1) Aloitetaan täyttämällä kaksi riviä.
Vaihe 2) Kolmannen rivin toinen elementti on toisen rivin ensimmäisen ja toisen numeron summa.
Vaihe 3) Neljäs rivi alkaa kirjaimella "1.". Toinen luku on 3, joka on 1:n ja 2:n summa (korostettu sinisellä).
Alla oleva kuva näyttää, kuinka neljäs rivi täytetään:
Vaihe 4) Viides rivi koostuu viidestä numerosta. Tiedämme jo mallin rivien täyttämiseksi aikaisemmista vaiheista.
Pascalin kolmiokaava – binomiaalinen kerroin
Binomikerroin on luku, joka ilmaisee eri menetelmiä k elementin osajoukon valitsemiseksi n elementin joukosta. Usein se kirjoitetaan "C(n,k)" tai "n valitse k".
Binomikerroin määritellään seuraavasti
"!" tarkoittaa "tekijää".
n! = n.(n-1). (n-2)…3.2.1
Esimerkiksi
5! = 5.4.3.2.1
= 120
Sanotaan siis, että C(5,3) tai 5 valitse 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Tapa 1: Rakenna Pascalin kolmio edellisen rivin mukaan
Tämän menettelyn vaiheet ovat samat kuin Pascalin kolmiossa. Oletetaan, että haluamme luoda Pascalin kolmion, jossa on enintään seitsemän riviä.
Toimenpiteet sen suorittamiseksi ovat seuraavat:
Vaihe 1) Aloita ylin rivi numerolla 1.
Vaihe 2) Rivin "r" kohta "c" on "c-1":n ja "r-1"-rivin numeron "c" tulo.
Vaihe 3) Ensimmäinen ja viimeinen numero rivissä ovat aina "1".
Meidän on noudatettava näitä kolmea helppoa vaihetta Pascalin kolmion luomiseksi.
C++ Pascalin kolmion koodi edellisellä rivillä
#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); }
lähtö:
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 Pascal-kolmiokaavan koodi edellisellä rivillä
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)
Pascalin kolmion esimerkkitulos:
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
Monimutkaisuusanalyysi
A kaksiulotteinen matriisi käytettiin toteutuksessa. Koska N on Pascalin kolmion rivien lukumäärä. Tämä vaatii N2 yksikkötilat. Siksi O on avaruuden kompleksisuus (N2).
Meillä on kaksi silmukkaa funktiossa, ja jokainen silmukka toimii "N" kertaa. Joten, aika monimutkaisuus on myös PÄÄLLÄ2) tai neliöity aika monimutkaisuus.
Menetelmä 2: Pascalin kolmion rakentaminen laskemalla binomiaalinen kerroin
Voimme yksinkertaisesti johtaa Pascalin kolmion luvut käyttämällä binomikerrointa. Tässä kaavio:
Tässä on vaiheet Pascalin kolmion rakentamiseksi laskemalla binomiaali:
Vaihe 1) Ylin rivi on C(0,0). Käyttämällä yllä olevaa kaavaa binomikertoimelle C(0,0) = 1. Koska 0! = 1.
Vaihe 2) Rivillä "i" on yhteensä "i"-elementtejä. Jokainen kohde lasketaan C(n,r), jossa n on i-1.
Vaihe 3) Toista vaihe 2 Pascalin kolmion rivien lukumäärälle.
C++ Koodaa Pascalin kolmio binomiaalisella kertoimella
#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); }
lähtö:
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 Koodaa Pascalin kolmio binomiaalisella kertoimella
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)
Pascalin kolmion esimerkkitulos:
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
Monimutkaisuusanalyysi
Toteutuksessa käytettiin kolmea silmukkaa. Yksi silmukka on binomikertoimen laskemiseen ja kaksi muuta on tarkoitettu lukujen luomiseen kaikille riveille. Mitä tulee rivien määrään, meillä on kolme silmukkaa, jotka suoritetaan "n" kertaa. Näin ollen kokonaisaika monimutkaisuus on 0 (n3).
Tilan monimutkaisuus on nyt jatkuvaa, koska emme säilytä mitään tietoja tallennustilassa. Ohjelma laskee elementin ja tulostaa sen riville. Avaruuden monimutkaisuus pienenee sitten arvoon 0(1).
Menetelmä 3: Pascalin kolmion rakentaminen modifioidulla binomikertoimella
Edellisessä tekniikassa olemme jo nähneet kuinka käyttää binomikerrointa Pascalin kolmion jokaisen elementin laskemiseen. Tämä lähestymistapa määrittää C(n,r):n arvosta C. (n, r-1). Se yksinkertaistaa asioita yhdellä tilauksella.
Tässä on vaiheet Pascalin kolmion rakentamiseksi modifioidulla binomikertoimella:
Vaihe 1) Aloita ensimmäinen rivi numerolla 1
Vaihe 2) Laske C(n,r), jossa "n" on rivin numero ja "r" on sarake tai elementti. Anna arvo muuttujassa C.
Vaihe 3) Laskettaessa C(n,k) se on C*(nk)/k. Määritä nyt tämä arvo C:lle.
Vaihe 4) Jatka vaihetta 3, kunnes "k" saavuttaa rivin lopun. Kasvata K:n arvoa jokaisen iteraation jälkeen yhdellä.
C++ Pascalin kolmion koodi modifioidulla binomiaalisella kertoimella
#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); }
lähtö:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Pascalin kolmion koodi modifioidulla binomiaalisella kertoimella
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)
Pascalin kolmiomallien lähtö:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Monimutkaisuusanalyysi
Toteutuksessa on kaksi silmukkaa. Jokainen silmukka kulkee enintään "n" ajan, jossa "n" tarkoittaa pascal-kolmion rivien määrää. Aika monimutkaisuus on siis Päällä2), neliöity aika.
Mitä tulee tilan monimutkaisuuteen, emme tarvinneet mitään taulukkoa tallennettavaksi. Käytimme vain yhtä muuttujaa säilyttääksemme edellisen binomikertoimen. Joten tarvitsimme vain yhden lisätilan. Tilan monimutkaisuus muuttui O (1).
Pascalin kolmion soveltaminen
Tässä on joitain Pascalin kolmion sovelluksia:
Binomilaajennukset: Voimme määrittää binomilaajennusten kertoimen Pascalin kolmiosta. Tässä on esimerkki:
(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 |
Yhdistelmien laskeminen: Olemme nähneet, että Pascalin kolmion elementit vastaavat binomiaalikertoimia. Jos sinulla on esimerkiksi 6 palloa ja sinua on pyydetty valitsemaan 3 palloa, niin se on 6C3. Tai voit löytää numeron Pascalin kolmion 3. rivin 6. elementistä.
Mielenkiintoisia faktoja Pascalin kolmiosta
Tässä on joitain mielenkiintoisia faktoja Pascalin kolmiosta:
- Kaikkien rivin elementtien summa on aina 2:n potenssi.
- Rivien elementtien diagonaalinen summa muodostaa Fibonacci-sekvenssin.
Yhteenveto
- Pascalin kolmio antaa kertoimet binomilaajennuksille.
- Jokainen Pascalin kolmion rivi alkaa ja päättyy numeroon 1. Väliarvot ovat edellisen rivin kahden elementin summa.
- Kaikkien Pascalin kolmion elementtien diagonaalinen lisääminen antaa sinulle Fibonacci-sekvenssi.
- Pascalin kolmio voidaan generoida myös binomiaalisilla kertoimilla.