Pascalův trojúhelník

O(n²)

Pascalův trojúhelník uspořádá binomické koeficienty tak, že strukturu počítá samo uspořádání. Každý kraj je 1 a každé vnitřní číslo je součet dvou nad ním — což je přesně identita C(n,k) = C(n−1,k−1) + C(n−1,k). Řádek n dává koeficienty (x+y)ⁿ; úhlopříčky jsou přirozená, trojúhelníková a čtyřstěnná čísla; mělké úhlopříčky dávají součtem Fibonacciho čísla a celý řádek se sečte na 2ⁿ. Sestavení je drobné dynamické programování O(n²), kde každá buňka přečte své dva rodiče. Dvě jantarové buňky jsou rodiče sčítaní do oranžové.

Číselný trojúhelník
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Dej 1 na vrchol.
  2. Každý řádek začni a ukonči jedničkou.
  3. Každá vnitřní buňka = součet dvou buněk nad ní.
  4. Řádek n je C(n,0), C(n,1), …, C(n,n).

Pseudokód

1pascal(n):                          # O(n²)2  for r from 0 to n-1:3    T[r][0] ← 1,  T[r][r] ← 1        # edges4    for c from 1 to r-1:5      T[r][c] ← T[r-1][c-1] + T[r-1][c]6  return T