Drzewo Sterna-Brocota

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Drzewo Sterna-Brocota - drzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne.

Konstrukcja[edytuj | edytuj kod]

Zaczynamy od \frac 0 1 - symbolizującego zero i \frac 1 0 symbolizującego nieskończoność. Następnie na kolejnych piętrach drzewa wpisujemy "pomiędzy" wartości \frac a b oraz \frac c d wartość \frac {a+c}{b+d} - patrz ilustracja.

SternBrocotTree.svg

Własności[edytuj | edytuj kod]

  • W drzewie występują wszystkie dodatnie liczby wymierne zapisane jako ułamki nieskracalne.
  • Każda liczba wymierna dodatnia występuje w drzewie dokładnie raz.
  • Jeśli liczby a\; oraz b\; są względnie pierwsze to ułamek \frac a b występuje w drzewie dokładnie raz.
  • W drzewie występują wszystkie liczby dodatnie wymierne, więc taką liczbę możemy opisać jako ścieżkę od korzenia drzewa do tej liczby. Jest to skończony ciąg symboli L oraz P (albo 0 1) np. liczbę \frac 3 8 zapisujemy jako LLPL
  • Każdą liczbę rzeczywistą dodatnią możemy zapisać jako ciąg symboli L oraz P tak, że początkowe fragmenty tego ciągu symbolizują liczby wymierne przybliżające tę liczbę.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]