Об одной изящной конструкции

[Nomad1]

Отличная статья!

P.S. Для новых Бабушкиных, которые могут воскликнуть «А что если сделать архиватор??» после прочтения последней части: в случае с числом пи для описания 6-ти значащих цифр (3,1415) было использовано 26 бит «маршрута».

[Vayun]

Не 6-ти значащих цифр, а 23-х значащих бит (но сути не меняет).

[Mrrl]

Там примерно 16 бит (разность дробей больше 2^(-14) плюс два бита на целую часть).

[Vayun]

Если мы кодируем число пи, то надо смотреть на разность пи и последней дроби 355/113

[OLS]

Лет 200 или 300 считали что Пи равно 355/113, тем более что и «цифры красиво встали».

[alexanderzaytsev]

Да что там 200 лет, вот всего 25 лет назад: en.wikipedia.org/wiki/Indiana_Pi_Bill

[x0wl]

Все-таки 116 лет назад, мы в 2013 живем, а заявку подали в 1897.

[alexanderzaytsev]

Да, проглядел — не проснулся еще.

[NickLion]

Т.е. если учесть 25 лет, заснули Вы в 1922 г? Прошу прощения, но можно уточнить, это был успешный анабиоз, Вы вампир или путешествуете во времени? ;)

[alexanderzaytsev]

Путешествую во времениживу в будущем.

[oshibka404]

Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.

Имеются в виду ведь только дроби со значением от 0 до 1, да?

[define_rak]

Вероятно тут подразумеваются правильные дроби, хотя для строгости условия надо бы уточнить.
P.S. Так если для всех дробей, то правильные можно просто перевернуть и провести проверку на остаток от деления.

[bminaiev]

P. S. очевидно, что если для всех дробей, то вы не сможете решить задачу, т. к. несократимых дробей со знаменателем <=100 бесконечно много.

[Sayonji]

del

[Mrrl]

Можно и без рекурсии:

        static void Main(string[] args) {
            int N=100;
            int a=0,b=1,c=1,d=N;
            Console.Write("0/1 1/{0} ",N);
            do {
                int m=(N+b)/d;
                int e=m*c-a,f=m*d-b;
                a=c; c=e;
                b=d; d=f;
                Console.Write("{0}/{1} ",c,d);
            } while(c<d);
        }

[godlin]

На сколько я помню, любую рекурсивную функцию можно переписать без рекурсии ;)

[Mrrl]

Да, но обычно при этом требуется динамический массив для стека. И получается не очень красиво.

[x0wl]

List<T>

[Mrrl]

А почему тогда не Stack?

[EndUser]

Извините, я здесь не понял:
«Таким образом, мы можем каждой рациональной дроби поставить в соответствие последовательность букв L И R».
Дерево содержит только множество несократимых из множества всех дробей (=рациональных).
Как вы изобразите 4/8 или 57/741 через цепочку «L-R»?

[Flux]

Дерево содержит только множество несократимых из множества всех дробей

Эти множества совпадают. 4/8 = 1/2, 57/741 = 1/13. Ну и в задаче подчеркивается что дроби именно несократимые.

[KvanTTT]

Представление каждой дроби в виде последовательности L и R также может служить функцией для нумерации всех рациональных чисел (при доказательстве того, что множество рациональных чисел счетно).
Другое представление, для тех кому интересно, есть на math.stackexchange.com (код доступен на github).

[Iktash]

Я бы поспорил с несократимостью дробей с знаменателем 1.

[backmeupplz]

В каком смысле? Как Вы сможете эту дробь сократить сильнее?
В данном случае сокращение не подразумевает отброс знаменателя.

[Iktash]

В данном случае сокращение не подразумевает отброс знаменателя.

В таком случае извиняюсь. Действительно погуглив убедился, что
НЕСОКРАТИМАЯ ДРОБЬ — дробь, числитель и знаменатель которой не имеют общих делителей

[backmeupplz]

Просто невероятно, как труды математиков прошлого находят применение в компьютерах настоящего.
А ведь эти люди изобретали новые алгоритмы еще до того, как появилось слово «компьютер»!
Это, товарищи, бесподобно!

[3ap]

Ведь это всего лишь «автоматизация» ручного метода по построению дерева. Так что в этом нет ничего удивительного.

[SLY_G]

Встретившись с неправильным деепричастным оборотом, он опечалил меня.
Да, я знаю, что про ошибки в личку пишут, но может кто-нибудь ещё увидит и научится уже.

«Прочитав условие задачи до конца, она не показалась мне сложной » -> «Прочитав условие задачи до конца, я решил, что она несложная».
Или: «Я прочитал условие задачи до конца, и она не показалась мне сложной».

[NickolayStrahov]

После прочтения последнего абзаца возникла мысль: если хвост числа pi дает «белый шум», значит ли что белый шум будет давать последовательность, этих LLLRRRLLL или могут возникнуть какие-то закономерности? На первый взгляд- закономерности очень даже могут быть. Хотя-бы потому, что число пи можно приблизить очень даже красивым рядом Лейбница (всем из себя закономерным). А если такие закономерности на самом деле обнаружатся — это дает возможность изучать свойства мировых констант при помощи изучения вот этих самых закономерностей, возникающих при приближении их различными способами.

[tguev]

Насчет pi точно не знаю о закономерностях (возможно они есть), но если приблизить экспоненту e=2,718281828… то получается закономерность.
При приближении e получим такой результат: RRLRRLRLLLLRLRRRRRRLRLLLLLLLLLRLR…
Или же в форме закономерности e = (RL)^0(RLR)^2(LRL)^4(RLR)^6(LRL)^8(RLR)^10… что эквивалентно частному случаю одного открытия, сделанного Эйлером в 24 года.

[vbif]

>Оказывается дерево Штерна-Броко можно использовать в качестве системы счисления
Интересно, а можно ли было бы использовать подобную запись для хранения чисел с плавающей точкой вместо традиционного IEEE 754? Насколько сложной была бы реализация математических операций для таких чисел в железе?

[ITguru]

После прочтения

дерево Штерна-Броко можно использовать в качестве системы счисления

у меня возникли вопросы:
1) Можно ли как-то описать операцию сложения в такой системе?
2) Можно ли как-то описать операцию умножения в такой системе?
3) Как определить отрицательные числа?

[Mrrl]

Отрицательные числа определить легко — добавить ещё одну букву L или R в начало: 0/1 будет пустой строкой, 1/1=«R», -1/1=«L», 3/2=«RRL».
Для операций сложения и умножения больше подходят имеющие сходный формат записи сюрреальные числа Конвея — совершенно уникальная конструкция, являющаяся самым большим по мощности упорядоченным полем: эти числа даже не образуют множество — их для этого слишком много :) Но сложение и умножение в них определены. К сожалению, рациональные числа там, как правило, имеют бесконечную длину.

[ITguru]

Собственно, мои вопросы и возникли когда я попытался провести параллели между сюрреальными числами и деревом Штерна-Броко. А может быть, эти конструкции равномощны?

[Mrrl]

Если мы разрешим в дереве Штерна-Броко ветки произвольной трансфинитной длины, конструкции, конечно, станут равномощными. Но удастся ли понять математический смысл узлов на бесконечной (и далее) глубине, пока не понятно.
А что до арифметики в системе счисления дерева Штерна-Броко — на самом деле, всё просто. Сначала переведём цепочки из L,R в цепные дроби — это легко, главное — помнить, что последнее число в записи цепной дроби на 1 больше, чем число одинаковых букв в конце строки. А дальше — рекурсия (здесь пример только для положительных чисел):
Пусть [0;b]=1/[b], [a;b]=a+1/[b], [a]=a (здесь a — целое число, а b — последовательность).
Тогда

Inv([0;c])=c
Inv([1])=[1]
Inv([b])=[0;b]
Inv([b;c])=[0;b;c]
[a]+[c]=[a+c]
[a;b]+[c]=[a+c;b]
[a;b]+[c;d]=[a+c]+([b]+[d])*Inv([b]*[d])

[a;b]/[c]=[a/c]+Inv([c]*Inv([a%c;b]))
[a]*[b;c]=[a*b]+Inv(c/[a])
[a;b]*[c;d]=[a;b]+Inv(b/[c])+Inv(c/[b])+Inv(b*d)

Если в левой части формулы стоит одна буква в скобках, то это целое число. Операции a/c и a%c в делении на целое — как в С.
Я еще не проверял, всегда ли вычисление конечно, но вроде бы, формулы должны работать.

[VaalKIA]

Я встречал так же упоминание, помимо перечисленных свойств, того, что в ряде Фарея любой числитель и знаменатель имеет наименьшее значение среди всех рациональных чисел, лежащих в этом промежутке. Это позволяет получать приближение любой дроби теряя в точности, но выигрывая в разрядности чисел. Только вот не видел доказательство.