Figurální čísla

O(√n)

Figurální čísla zobecňují myšlenku rozmísťování objektů do geometrických tvarů. Trojúhelníková čísla T(k)=k(k+1)/2 odpovídají počtu objektů v rovnostranném trojúhelníku; čtvercová čísla k² odpovídají čtverci; pentagonální čísla P(k)=k(3k-1)/2 odpovídají pětiúhelníku. Vizualizér prochází k od 1 nahoru a označuje každou figurální hodnotu její barvou (zelená pro trojúhelníková, fialová pro čtvercová, zlatá pro pentagonální). Pokud číslo patří do více rodin, čtvercové bije trojúhelníkové bije pentagonální. Algoritmus se zastaví, jakmile všechny tři řady překročí n.

Čísla
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Inicializace všech buněk 1..n jako neutrálních
  2. Procházej k nahoru, počítej T(k), k², P(k)
  3. Označ každou figurální hodnotu; čtvercové > trojúhelníkové > pentagonální
  4. Zastav se, jakmile všechny tři řady překročí n

Pseudokód

1figurate(n):                        # O(sqrt(n))2  label[1..n] = "neutral"3  for k = 1, 2, ...:4    tri  = k*(k+1)/25    sq   = k*k6    pent = k*(3*k - 1)/27    if all three > n: break8    if sq   <= n: label[sq]   = "square"9    if tri  <= n and label[tri]  != "square": label[tri]  = "triangular"10    if pent <= n and label[pent] not in {"square","triangular"}: label[pent] = "pentagonal"