Pascal's triangle

Pascal's triangle (tsz. Pascal's triangles)

1. (informatika) Pascal-háromszög

A Pascal-háromszög (Pascal’s Triangle) egy olyan matematikai elrendezés, amelyben minden szám az adott sor két szomszédos számának összege. Az első sor (0. sor) és az első szám minden sorban 1. A háromszög szerkezete így néz ki:

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

A Pascal-háromszögben az n-edik sor k-adik számát a következő képlettel lehet meghatározni:

C(n, k) = n! / (k! * (n-k)!)

Ez a képlet a kombinációs számítások alapja, amelyet a Pascal-háromszögben minden szám reprezentál.

Az alábbiakban bemutatom, hogyan lehet Pascal-háromszöget kiírni C++-ban.

Az egyszerűbb megoldás ciklusokkal valósítható meg, és az alábbiakban bemutatom, hogyan készíthetjük el ezt a háromszöget C++-ban.

#include <iostream>
using namespace std;

// Függvény a faktoriális kiszámításához
long long factorial(int n) {
    long long fact = 1;
    for (int i = 1; i <= n; i++) {
        fact *= i;  // Szorzás minden egyes számra
    }
    return fact;
}

// Függvény a Pascal-háromszög kiíratásához
void printPascal(int n) {
    for (int i = 0; i < n; i++) {
        // Fehér helyek kiírása a megfelelő eltoláshoz
        for (int j = 0; j < n - i - 1; j++) {
            cout << " ";
        }

        // A sor elemeinek kiíratása
        for (int j = 0; j <= i; j++) {
            // Kombinációs szám (nCr) kiszámítása
            cout << factorial(i) / (factorial(j) * factorial(i - j)) << " ";
        }

        // Új sor
        cout << endl;
    }
}

int main() {
    int n;
    cout << "Add meg, hány sorból álljon a Pascal-háromszög: ";
    cin >> n;

    cout << "Pascal-háromszög " << n << " sorral:" << endl;
    printPascal(n);

    return 0;
}

1. Faktoriális függvény: A factorial függvény kiszámítja egy szám faktoriálisát, amely szükséges a Pascal-háromszögben szereplő számok kiszámításához. A faktoriális egy szám összes pozitív egész számával való szorzataként van definiálva.
2. Pascal-háromszög kiíratása: A printPascal függvény iterál a sorokon és minden sorra kiszámítja a megfelelő kombinációs számokat (nCr).
   • A külső ciklus a sorokat iterálja, míg a belső ciklus a sor elemeit (azaz a számokat) számítja ki és írja ki.
   • Az eltolásokat úgy biztosítjuk, hogy minden sor előtt elegendő fehér helyet adunk ki.

Ha a felhasználó 5 soros Pascal-háromszöget kér, akkor a kimenet a következő lesz:

Add meg, hány sorból álljon a Pascal-háromszög: 5
Pascal-háromszög 5 sorral:
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1 

A fenti kód a faktoriális kiszámításához használja a factorial függvényt, de ez nem a leghatékonyabb megoldás. A Pascal-háromszöget gyorsabban is kiírhatjuk úgy, hogy az egyes számokat rekurzív módon számoljuk ki az előző számok segítségével.

#include <iostream>
using namespace std;

// Pascal-háromszög kiíratása kombinációk segítségével
void printPascal(int n) {
    for (int i = 0; i < n; i++) {
        // Fehér helyek kiírása
        for (int j = 0; j < n - i - 1; j++) {
            cout << " ";
        }

        // A sor elemeinek kiíratása
        long long val = 1;  // Az első elem mindig 1
        for (int j = 0; j <= i; j++) {
            cout << val << " ";
            val = val * (i - j) / (j + 1);  // Az aktuális kombinációs szám kiszámítása
        }

        cout << endl;
    }
}

int main() {
    int n;
    cout << "Add meg, hány sorból álljon a Pascal-háromszög: ";
    cin >> n;

    cout << "Pascal-háromszög " << n << " sorral:" << endl;
    printPascal(n);

    return 0;
}

• Az iterációk során az egyes számokat nem faktoriálisokból számítjuk ki, hanem a kombinációs képletet alkalmazzuk közvetlenül:
  • Az első szám mindig 1.
  • Minden következő számot úgy számolunk ki, hogy az előző számot megszorozzuk a sor számának és az indexének különbségével, majd elosztjuk az index + 1 értékével.

Ez a kód ugyanolyan kimenetet ad, mint az előző, de lényegesen gyorsabb.

Add meg, hány sorból álljon a Pascal-háromszög: 5
Pascal-háromszög 5 sorral:
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1 

• A Pascal-háromszög egy egyszerű, de fontos matematikai struktúra, amelyet különböző módon generálhatunk C++-ban.
• Az optimális megoldás az, ha a számokat rekurzívan, az előző számok segítségével számoljuk ki, elkerülve a nagy számú faktoriális műveletek végrehajtását.

• Pascal's triangle - Szótár.net (en-hu)
• Pascal's triangle - Sztaki (en-hu)
• Pascal's triangle - Merriam–Webster
• Pascal's triangle - Cambridge
• Pascal's triangle - WordNet
• Pascal's triangle - Яндекс (en-ru)
• Pascal's triangle - Google (en-hu)
• Pascal's triangle - Wikidata
• Pascal's triangle - Wikipédia (angol)