Loading AI tools
ориентированное двоичное дерево, в вершинах которого расположены положительные рациональные дроби Из Википедии, свободной энциклопедии
Дерево Ка́лкина — Уи́лфа (англ. Calkin—Wilf tree) — ориентированное двоичное дерево, в вершинах которого расположены положительные рациональные дроби согласно следующему правилу:
Дерево описано Нейлом Калкином и Гербертом С. Уилфом[англ.] (2000[1]) в связи с задачей явного пересчёта[2] множества рациональных чисел.
Из приведенных выше свойств следует, что последовательность положительных рациональных чисел, получаемая в результате обхода «в ширину»[3] (англ. breadth-first traversal) дерева Калкина — Уилфа (называемая также последовательностью Калкина — Уилфа; см. иллюстрацию),
определяет взаимно однозначное соответствие между множеством натуральных чисел и множеством положительных рациональных чисел.
Данная последовательность может быть задана рекуррентным соотношением[4]
где и обозначают соответственно целую и дробную части числа .
В последовательности Калкина — Уилфа знаменатель каждой дроби равен числителю следующей.
В 1976 году Э. Дейкстра определил на множестве натуральных чисел целочисленную функцию fusc(n) следующими рекуррентными соотношениями[5]:
Последовательность значений совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью
Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), -й член последовательности Калкина — Уилфа равен , а соответствие
является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.
Функция может быть, помимо указанных выше рекуррентных соотношений, определена следующим образом.
В оригинальной статье Калкина и Уилфа функция не упоминается, но рассматривается целочисленная функция , определённая для , равная количеству гипердвоичных представлений числа , и доказывается, что соответствие
является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для имеют место соотношения
Этот раздел статьи ещё не написан. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.