Система счисления Штерна-Броко
Burzon56 (обсуждение | вклад) |
Burzon56 (обсуждение | вклад) |
||
| (не показаны 8 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | '''Система счисления Штерна-Броко''' | + | Автор составитель: |
| + | Бурзайкина Татьяна (Пиб-101) | ||
| + | |||
| + | |||
| + | == '''Система счисления Штерна-Броко''' == | ||
| + | |||
| + | |||
| Строка 6: | Строка 12: | ||
---- | ---- | ||
| + | '''Дерево Штерна — Броко''' — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева. | ||
| − | + | Это замечательный способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить (m+m')/(n+n') между двумя соседними дробями m/n и m'/n'. | |
| + | |||
| + | Или немного научнее: | ||
В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея) стоит медианта [[Изображение:ь.jpg.png]] дробей [[Изображение:б.jpg.png]] и [[Изображение:ю.jpg.png]]стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так: | В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея) стоит медианта [[Изображение:ь.jpg.png]] дробей [[Изображение:б.jpg.png]] и [[Изображение:ю.jpg.png]]стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так: | ||
[[Изображение:юб.jpg.png]] | [[Изображение:юб.jpg.png]] | ||
| − | История | + | Каждый узел дерева имеет вид (m+m')/(n+n'), где m/n — ближайший предок сверху слева, а m'/n' — сверху справа. |
| + | |||
| + | |||
| + | |||
| + | == История == | ||
| + | |||
В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математика открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). | В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математика открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). | ||
| − | Также была похожая система счисления была известна еще древнегреческим математикам и была построениа в форме «дерева | + | Также была похожая система счисления была известна еще древнегреческим математикам и была построениа в форме «дерева [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%9A%D0%B0%D0%BB%D0%BA%D0%B8%D0%BD%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D1%84%D0%B0 Калкина-Уилфа]". |
| + | |||
| + | |||
| + | |||
| + | == Свойства == | ||
| + | |||
| + | |||
| + | -Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы; | ||
| + | -Каждая несократимая дробь появляется в дереве ровно один раз. | ||
| + | |||
| + | Для дерева Штерна — Броко доказательство основано на следующей лемме: если p1 / q1 < p2 / q2 — дроби в двух соседних узлах дерева, то q1p2 − q2p1 = 1. | ||
| + | |||
---- | ---- | ||
| − | ''Система счисления Штерна — Броко'' | + | == ''Система счисления Штерна — Броко'' == |
| + | |||
| + | |||
| + | Можно воспользоваться символами '''L''' и '''R''' для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определённой дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов '''«R»''' и '''«L»''' (''дроби 1/1 соответствует пустая строка''). Такое представление положительных рациональных чисел назовём системой счисления Штерна — Броко. К примеру, обозначение '''LRRL''' соответствует дроби 5/7. | ||
| + | |||
| + | |||
| − | + | [[Категория:Информатика и ИКТ]] | |
Текущая версия на 11:06, 20 сентября 2011
Автор составитель: Бурзайкина Татьяна (Пиб-101)
Содержание |
Система счисления Штерна-Броко
Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.
Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева.
Это замечательный способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить (m+m')/(n+n') между двумя соседними дробями m/n и m'/n'.
Или немного научнее:
В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея) стоит медианта 
дробей 
и 
стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так:
Каждый узел дерева имеет вид (m+m')/(n+n'), где m/n — ближайший предок сверху слева, а m'/n' — сверху справа.
История
В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математика открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). Также была похожая система счисления была известна еще древнегреческим математикам и была построениа в форме «дерева Калкина-Уилфа".
Свойства
-Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы; -Каждая несократимая дробь появляется в дереве ровно один раз.
Для дерева Штерна — Броко доказательство основано на следующей лемме: если p1 / q1 < p2 / q2 — дроби в двух соседних узлах дерева, то q1p2 − q2p1 = 1.
Система счисления Штерна — Броко
Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определённой дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов «R» и «L» (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовём системой счисления Штерна — Броко. К примеру, обозначение LRRL соответствует дроби 5/7.
