Дерево Штерна — Броко — спосіб розташування всіх невід'ємних нескоротних дробів у вершинах упорядкованого нескінченного двійкового .
У кожному вузлі дерева Штерна — Броко (іноді також званого (деревом Фарея)) стоїть (медіанта) дробів і , які стоять у найближчих до цього вузла лівому і правому верхніх вузлах. Початковий шматок дерева Штерна — Броко в цьому випадку має такий вигляд:
Близьким за побудовою до дерева Штерна — Броко є (дерево Калкіна — Вілфа), в якому дріб є коренем, а всі інші вузли заповнюються за таким алгоритмом: кожна вершина має двох нащадків: лівого і правого .
Історія
У книзі (Р. Грема), (Д. Кнута), «» відкриття «дерева Штерна — Броко» пов'язується з іменами (1858) і (1860). Однак аналогічна побудова у формі «дерева Калкіна — Вілфа» була відомою ще давньогрецьким математикам. Його описана під назвою «породження всіх відношень з відношення рівності як з матері і кореня» в двох математичних оглядах (II століття), що належать (Нікомаху Гераському) і [ru]. Теон повідомляє, що ця конструкція була відома (Ератосфену Киренському) — знаменитому вченому, що жив у III столітті до н. е.
Властивості
- Всі дроби в деревах Калкіна — Вілфа і Штерна — Броко нескоротні;
- Кожен нескоротний дріб з'являється в дереві рівно один раз.
Для дерева Калкіна — Вілфа ці властивості легко довести, якщо зауважити, що кожному кроку деревом у напрямку до кореня відповідає елементарний крок віднімання меншого числа з більшого в (алгоритмі Евкліда) для пошуку найбільшого спільного дільника.
Для дерева Штерна — Броко доведення ґрунтується на такій лемі: якщо — дроби в двох сусідніх вузлах дерева, то .
Система числення Штерна — Броко
Можна скористатися символами L і R для ідентифікації лівої і правої гілки при просуванні вниз по дереву від кореня, дробу 1/1, до деякого певного дробу. Тоді кожен додатний дріб отримує єдине подання у вигляді рядка, що складається зі символів «R» і «L» (дробу 1/1 відповідає порожній рядок). Таке подання додатних раціональних чисел назвемо системою числення Штерна — Броко. Наприклад, позначення LRRL відповідає дробу 5/7.
Див. також
- (Ряд Фарея)
- (Ланцюговий дріб)
- Система числення
- (Алгоритм Евкліда)
- (Дерево Калкіна — Вілфа)
- (Коло Форда)
Література
- , Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. — М. : Мир, 2006. — С. 105—109. — ..
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М. : Мир, 1998. — 704 с. — ..
- Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // . — 2008. — Т. 2 (16 червня). — С. 55—74. — ISSN 1995-4328. з джерела 5 лютого 2020. Процитовано 29 червня 2021.
- Brocot A. Calcul des rouages par approximation, nouvelle méthode // Revue Chonométrique. — 1861. — Т. 3 (16 червня). — С. 186—194.
- Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55 (16 червня). — С. 193—220.
Посилання
- The Stern — Brocot or Farey Tree [ 24 жовтня 2010 у Wayback Machine.](англ.)
- Кноп К. Недвоичная система // Домашний компьютер. — 2001. — № 8 (16 червня). з джерела 12 березня 2007.
- Онлайн-демонстратор наближення раціональних чисел за допомогою дерева Штерна — Броко [ 29 червня 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет