Pascal-háromszög – képlet, minták és példák
Mi az a Pascal-háromszög?
A Pascal-háromszög egy háromszög alakú számtömb, amelyet egy adott minta követ, és az előtte lévő sorhoz kapcsolódik. Blaise Pascal találta fel. Ez a háromszög az első sor egy elemével kezdődik. Ezt követően minden sor „1”-el kezdődik és végződik.
Pascal háromszög története
A „Kilenc fejezet a matematikai művészetről” című kínai könyv tartalmazza a Pascal-háromszög egyik első példáját. Ezenkívül ugyanazokat a mintákat és tulajdonságokat tartalmazza, amelyek ma a háromszögekben találhatók.
Pascal egyike volt azoknak Európában, akik tanulmányozták a háromszöget. Más matematikusok is megvizsgálták előtte hasonló háromszög alakú számtömböket.
Pascal-háromszög felépítése
A Pascal-háromszög megalkotása egyszerű. Az egyetlen dolog, amit emlékezned kell, hogy a sor 1-gyel kezdődik és végződik. A többi szám szabálya a következő:
Bármely r sor és c oszlop esetén a szám az r-1 sor c-1 és c oszlopának összege lesz.
Itt,
- r = 3,4,5….
- n és c = 2,3,4,…r-1.
Íme a lépések a Pascal-háromszög létrehozásához:
Step 1) Kezdjük két sor kitöltésével.
Step 2) A harmadik sor második eleme a második sor első és második számának összege.
Step 3) A negyedik sor „1”-el kezdődik. A második szám a 3, ami 1 és 2 összege (kék színnel kiemelve).
Az alábbi képen látható, hogyan kell kitölteni a negyedik sort:
Step 4) Az ötödik sor öt számból áll majd. A sorok feltöltésének mintáját már ismerjük a korábbi lépésekből.
Pascal-háromszög képlet – Binomiális együttható
A binomiális együttható olyan szám, amely különböző módszereket fejez ki egy k elemből álló részhalmaz kiválasztására n elemből álló gyűjteményből. Gyakran úgy írják, hogy „C(n,k)” vagy „n válasszuk k”.
A binomiális együtthatót a következőképpen határozzuk meg
A "!" a „tényezőt” jelöli.
n! = n.(n-1). (n-2)…3.2.1
Például,
5! = 5.4.3.2.1
= 120
Tehát mondjuk C(5,3) vagy 5 válassza ki a 3 = 5-öt! / 3!(5-3)!
= 120/(12)
= 10
1. módszer: Pascal háromszögének felépítése az előző sorból
Az eljárás lépései ugyanazok, mint a Pascal-háromszögben. Tegyük fel, hogy Pascal háromszögét akarjuk létrehozni legfeljebb hét sorból.
Ennek lépései a következők:
Step 1) Kezdje a legfelső sort „1”-el.
Step 2) Az „r” sorban a „c” tétel „c-1” és „c” az „r-1” sor számának szorzata lesz.
Step 3) A sorban az első és az utolsó szám mindig „1” lesz.
Ezt a három egyszerű lépést be kell tartanunk a Pascal-háromszög létrehozásához.
C++ Pascal-háromszög kódja az előző sor szerint
#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); }
output:
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 háromszög képlet kódja az előző sor szerint
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)
Pascal-háromszög példa kimenet:
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
Komplexitás elemzése
A kétdimenziós tömb a megvalósítás során használták. Tekintettel arra, hogy N a Pascal-háromszög sorainak száma. Ehhez szükség lesz N2 egységterek. Ezért O lesz a tér összetettsége (N2).
A függvényben két ciklus van, és mindegyik ciklus „N”-ig fut. Tehát az idő bonyolultsága is TOVÁBB2) vagy négyzetes időbonyolultság.
2. módszer: Pascal-háromszög felépítése binomiális együttható kiszámításával
Egyszerűen levezethetjük a Pascal-háromszög számait a binomiális együttható segítségével. Íme a diagram:
Íme a lépések a Pascal-háromszög felépítéséhez a binomiális kiszámításával:
Step 1) A legfelső sor C(0,0) lesz. A fenti képletet használva a binomiális együtthatóhoz C(0,0) = 1. Mert 0! = 1.
Step 2) Az „i” sorban összesen „i” elem lesz. Minden elem kiszámítása C(n,r) lesz, ahol n értéke i-1.
Step 3) Ismételje meg a 2. lépést a Pascal-háromszöghez kívánt sorok számához.
C++ Kódolja a Pascal-háromszöget binomiális együtthatóval
#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); }
output:
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 Kódolja a Pascal-háromszöget binomiális együtthatóval
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)
Pascal-háromszög példa kimenet:
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
Komplexitás elemzése
A megvalósítás során három hurkot használtak. Az egyik ciklus a binomiális együttható kiszámítására szolgál, a másik kettő pedig az összes sorhoz tartozó számok létrehozására. A sorok számát illetően három ciklusunk van, amelyek „n”-szer hajtódnak végre. Következésképpen a teljes időbonyolultság 0 (n3).
A tér összetettsége most állandó, mert nem tárolunk semmilyen adatot a tárhelyen. A program kiszámítja az elemet, és sorban kinyomtatja. A tér összetettsége ezután 0-ra (1) csökken.
3. módszer: Pascal-háromszög felépítése módosított binomiális együtthatóval
Az előző technikában már láttuk, hogyan lehet binomiális együtthatót használni a Pascal-háromszög egyes elemeinek kiszámításához. Ez a megközelítés meghatározza a C(n,r)-t a C-ből (n,r-1). Egy rendeléssel leegyszerűsíti a dolgokat.
Íme, a Pascal-háromszög módosított binomiális együtthatóval történő felépítésének lépései:
Step 1) Kezdje az első sort „1”-el
Step 2) Számítsa ki C(n,r), ahol „n” a sor száma, „r” pedig az oszlop vagy az elem. Adja hozzá az értéket egy C változóban.
Step 3) A C(n,k) kiszámításához C*(nk)/k lesz. Most rendelje hozzá ezt az értéket C-hez.
Step 4) Folytassa a 3. lépést, amíg a „k” el nem éri a sor végét. Minden iteráció után növelje a K értékét eggyel.
C++ Pascal-háromszög kódja módosított binomiális együtthatóval
#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); }
output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Pascal-háromszög kódja módosított binomiális együtthatóval
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)
Pascal-háromszög minták kimenete:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Komplexitás elemzése
A megvalósítás két hurokból áll. Minden ciklus legfeljebb „n” ideig fut, ahol az „n” a pascal háromszög sorainak számát jelenti. Tehát az idő bonyolultsága Tovább2), négyzetes idő.
Ami a tér összetettségét illeti, nem volt szükségünk semmilyen tömbre a tároláshoz. Csak egy változót használtunk, hogy megtartsuk az előző binomiális együtthatót. Tehát csak egy plusz helyre volt szükségünk. A tér összetettsége lett O (1).
Pascal-háromszög alkalmazása
Íme a Pascal-háromszög néhány alkalmazása:
Binomiális bővítések: A Pascal-háromszögből meg tudjuk határozni a binomiális bővítések együtthatóját. Íme egy példa:
(x + y)0 | 1 |
(x + y)1 | 1.x + 1.y |
(x + y)2 | 1x2 + 2xy + 1y2 |
(x + y)3 | 1x3 + 3x2és + 3xy2 + 1y3 |
(x + y)4 | 1x4 + 4x3és + 6x2y2 + 4xy3 + 1y4 |
Kombinációk számítása: Láttuk, hogy a Pascal-háromszög elemei ekvivalensek a binomiális együtthatókkal. Például, ha van 6 labdája, és megkérik, hogy válasszon 3 labdát, akkor az lesz 6C3. Vagy megtalálhatja a számot a Pascal-háromszög 3. sorának 6. elemében.
Érdekes tények Pascal háromszögéről
Íme néhány érdekes tény a Pascal-háromszögről:
- A sorban lévő összes elem összege mindig 2 hatványa.
- A sorok elemeinek átlós összege generálja a Fibonacci sorozatot.
Összegzésként
- A Pascal-háromszög megadja a binomiális kiterjesztések együtthatóit.
- A Pascal-háromszög minden sora 1-gyel kezdődik és végződik. A köztes értékek az előző sor két elemének összege.
- A Pascal-háromszög összes elemének átlós összeadása megadja a Fibonacci szekvencia.
- A Pascal-háromszög binomiális együtthatókkal is előállítható.