Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 36

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

P.S. Для новых Бабушкиных, которые могут воскликнуть «А что если сделать архиватор??» после прочтения последней части: в случае с числом пи для описания 6-ти значащих цифр (3,1415) было использовано 26 бит «маршрута».
Всего голосов 5: ↑5 и ↓0+5
Там примерно 16 бит (разность дробей больше 2^(-14) плюс два бита на целую часть).
Комментарий пока не оценивали0
Если мы кодируем число пи, то надо смотреть на разность пи и последней дроби 355/113
Комментарий пока не оценивали0
Лет 200 или 300 считали что Пи равно 355/113, тем более что и «цифры красиво встали».
Всего голосов 2: ↑2 и ↓0+2
Да, проглядел — не проснулся еще.
Всего голосов 1: ↑1 и ↓0+1
Т.е. если учесть 25 лет, заснули Вы в 1922 г? Прошу прощения, но можно уточнить, это был успешный анабиоз, Вы вампир или путешествуете во времени? ;)
Комментарий пока не оценивали0
Путешествую во времениживу в будущем.
Всего голосов 2: ↑2 и ↓0+2
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.

Имеются в виду ведь только дроби со значением от 0 до 1, да?
Всего голосов 2: ↑2 и ↓0+2
Вероятно тут подразумеваются правильные дроби, хотя для строгости условия надо бы уточнить.
P.S. Так если для всех дробей, то правильные можно просто перевернуть и провести проверку на остаток от деления.
Всего голосов 2: ↑2 и ↓0+2
P. S. очевидно, что если для всех дробей, то вы не сможете решить задачу, т. к. несократимых дробей со знаменателем <=100 бесконечно много.
Всего голосов 1: ↑1 и ↓0+1
Можно и без рекурсии:
        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);
        }

Всего голосов 5: ↑5 и ↓0+5
На сколько я помню, любую рекурсивную функцию можно переписать без рекурсии ;)
Комментарий пока не оценивали0
Да, но обычно при этом требуется динамический массив для стека. И получается не очень красиво.
Всего голосов 2: ↑2 и ↓0+2
А почему тогда не Stack?
Комментарий пока не оценивали0
Извините, я здесь не понял:
«Таким образом, мы можем каждой рациональной дроби поставить в соответствие последовательность букв L И R».
Дерево содержит только множество несократимых из множества всех дробей (=рациональных).
Как вы изобразите 4/8 или 57/741 через цепочку «L-R»?
Всего голосов 1: ↑1 и ↓0+1
Дерево содержит только множество несократимых из множества всех дробей


Эти множества совпадают. 4/8 = 1/2, 57/741 = 1/13. Ну и в задаче подчеркивается что дроби именно несократимые.
Всего голосов 3: ↑3 и ↓0+3
Представление каждой дроби в виде последовательности L и R также может служить функцией для нумерации всех рациональных чисел (при доказательстве того, что множество рациональных чисел счетно).
Другое представление, для тех кому интересно, есть на math.stackexchange.com (код доступен на github).
Всего голосов 3: ↑3 и ↓0+3
Я бы поспорил с несократимостью дробей с знаменателем 1.
Всего голосов 5: ↑0 и ↓5-5
В каком смысле? Как Вы сможете эту дробь сократить сильнее?
В данном случае сокращение не подразумевает отброс знаменателя.
Всего голосов 4: ↑4 и ↓0+4
В данном случае сокращение не подразумевает отброс знаменателя.

В таком случае извиняюсь. Действительно погуглив убедился, что
НЕСОКРАТИМАЯ ДРОБЬ — дробь, числитель и знаменатель которой не имеют общих делителей
Всего голосов 3: ↑3 и ↓0+3
Просто невероятно, как труды математиков прошлого находят применение в компьютерах настоящего.
А ведь эти люди изобретали новые алгоритмы еще до того, как появилось слово «компьютер»!
Это, товарищи, бесподобно!
Комментарий пока не оценивали0
Ведь это всего лишь «автоматизация» ручного метода по построению дерева. Так что в этом нет ничего удивительного.
Комментарий пока не оценивали0
Встретившись с неправильным деепричастным оборотом, он опечалил меня.
Да, я знаю, что про ошибки в личку пишут, но может кто-нибудь ещё увидит и научится уже.

«Прочитав условие задачи до конца, она не показалась мне сложной » -> «Прочитав условие задачи до конца, я решил, что она несложная».
Или: «Я прочитал условие задачи до конца, и она не показалась мне сложной».
Всего голосов 19: ↑16 и ↓3+13
После прочтения последнего абзаца возникла мысль: если хвост числа pi дает «белый шум», значит ли что белый шум будет давать последовательность, этих LLLRRRLLL или могут возникнуть какие-то закономерности? На первый взгляд- закономерности очень даже могут быть. Хотя-бы потому, что число пи можно приблизить очень даже красивым рядом Лейбница (всем из себя закономерным). А если такие закономерности на самом деле обнаружатся — это дает возможность изучать свойства мировых констант при помощи изучения вот этих самых закономерностей, возникающих при приближении их различными способами.
Всего голосов 2: ↑1 и ↓10
Насчет pi точно не знаю о закономерностях (возможно они есть), но если приблизить экспоненту e=2,718281828… то получается закономерность.
При приближении e получим такой результат: RRLRRLRLLLLRLRRRRRRLRLLLLLLLLLRLR…
Или же в форме закономерности e = (RL)^0(RLR)^2(LRL)^4(RLR)^6(LRL)^8(RLR)^10… что эквивалентно частному случаю одного открытия, сделанного Эйлером в 24 года.
Всего голосов 5: ↑5 и ↓0+5
>Оказывается дерево Штерна-Броко можно использовать в качестве системы счисления
Интересно, а можно ли было бы использовать подобную запись для хранения чисел с плавающей точкой вместо традиционного IEEE 754? Насколько сложной была бы реализация математических операций для таких чисел в железе?
Комментарий пока не оценивали0
После прочтения
дерево Штерна-Броко можно использовать в качестве системы счисления

у меня возникли вопросы:
1) Можно ли как-то описать операцию сложения в такой системе?
2) Можно ли как-то описать операцию умножения в такой системе?
3) Как определить отрицательные числа?
Комментарий пока не оценивали0
Отрицательные числа определить легко — добавить ещё одну букву L или R в начало: 0/1 будет пустой строкой, 1/1=«R», -1/1=«L», 3/2=«RRL».
Для операций сложения и умножения больше подходят имеющие сходный формат записи сюрреальные числа Конвея — совершенно уникальная конструкция, являющаяся самым большим по мощности упорядоченным полем: эти числа даже не образуют множество — их для этого слишком много :) Но сложение и умножение в них определены. К сожалению, рациональные числа там, как правило, имеют бесконечную длину.
Комментарий пока не оценивали0
Собственно, мои вопросы и возникли когда я попытался провести параллели между сюрреальными числами и деревом Штерна-Броко. А может быть, эти конструкции равномощны?
Комментарий пока не оценивали0
Если мы разрешим в дереве Штерна-Броко ветки произвольной трансфинитной длины, конструкции, конечно, станут равномощными. Но удастся ли понять математический смысл узлов на бесконечной (и далее) глубине, пока не понятно.
А что до арифметики в системе счисления дерева Штерна-Броко — на самом деле, всё просто. Сначала переведём цепочки из 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 в делении на целое — как в С.
Я еще не проверял, всегда ли вычисление конечно, но вроде бы, формулы должны работать.

Всего голосов 1: ↑1 и ↓0+1
Я встречал так же упоминание, помимо перечисленных свойств, того, что в ряде Фарея любой числитель и знаменатель имеет наименьшее значение среди всех рациональных чисел, лежащих в этом промежутке. Это позволяет получать приближение любой дроби теряя в точности, но выигрывая в разрядности чисел. Только вот не видел доказательство.
Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время
Изменить настройки темы

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr