Pascalův trojúhelník mod 2 (Sierpiński)

O(n²)

Každá buňka se počítá stejně jako v Pascalově trojúhelníku, ale hodnota se bere modulo 2, takže se objevuje jen 0 a 1. Liché buňky (1) tvoří viditelný vzor Sierpińského trojúhelníku. Fraktální struktura vzniká proto, že (a+b) mod 2 = a XOR b, takže při počtech řádků rovných mocninám dvojky vznikají velké trojúhelníkové mezery. Na n řádcích obsahuje trojúhelník přesně 3^k vyplněných buněk, kde 2^k ≤ n < 2^(k+1).

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

Jak to funguje

  1. Připrav prázdný trojúhelník o n řádcích
  2. Vyplň každou krajní buňku jedničkou
  3. Vyplň každou vnitřní buňku jako (levý rodič + pravý rodič) mod 2
  4. Pozoruj Sierpińského fraktál ve vzoru parit

Pseudokód

1pascalMod2(n):                      # O(n²)2  rows = []3  for r in 0..n-1:4    rows[r] = array of r+1 nulls5    for c in 0..r:6      if c == 0 or c == r:7        rows[r][c] = 1              # edge8      else:9        rows[r][c] = (rows[r-1][c-1] + rows[r-1][c]) % 2