то
qn-1 < 1/√ε < qn
(5)
и, значит
Поэтому,
Ic(ε) <= 1/2∙I2(ε) + 1/2 + log2 an
Если принять, что 1/q2n < ε, то оценка упрощается:
Ic(ε) <= 1/2∙I2(ε) + 1/2
Таким образом видим, что теоретическая нижняя граница для Ic(ε) — объема данных, потребных для хранения вещественного числа а, оценена нами как сверху (формулы (6) и (6’)), так и снизу (формула (4)). Поэтому в случае больших объемов информации (Ic(ε) —> оо) представление числа в виде цепной дроби требует примерно вдвое меньшего количества бит, т. е. достигаемое сжатие — порядка 50 %.
3. Оценку (6) можно несколько улучшить. Для этого достаточно вместо (3) использовать более точную оценку приближения произвольного числа а подходящими дробями. Именно, ([1]. стр. 30) имеют место неравенства:
(7)
Поэтому если дробь pn/qn — первая из последовательности подходящих дробей, которая приближает число а с точностью ε, то, очевидно, имеют место неравенства:
и в тоже время
Из последнего неравенства вытекает
qn-1qn <= 1/ε (8)
Но
qn-1qn = qn-1(anqn-1 + qn-2) >= anq2n-1
Поэтому (8) превращается в неравенство
каковая оценка является просто уточнением первого из неравенств (5). Поэтому точно так же, как и раньше получаем уточненную оценку для Ic(ε):
Список литературы
[1] А. Я. Хинчин. Цепные дроби. Государственное изд-во физ. — мат. лит-ры. М., 1961.
Задача: Три рыбака ловили рыбу и после ловли заночевали на берегу. Двое рыбаков заснули, а третий решил уехать домой со своей частью улова. Он разделил рыбу на 3 равные части, но при этом одна рыбина оказалась лишней. Он швырнул ее в воду, забрал свою треть и ушел.
Среди ночи проснулся второй рыбак и тоже решил уехать. Не зная, что первый рыбак уже ушел, он тоже поделил всю рыбу на 3 равные части, одна рыбина снова оказалась лишней, он ее тоже выкинул и ушел.
То же произошло и с последним рыбаком: проснувшись, он тоже разделил оставшийся улов на 3 равные части, выкинул одну рыбину и ушел.
Вопрос: какое наименьшее количество рыб могло быть у рыбаков?
Решение П. А. М. Дирака: Рыб было (-2). После того, как первый рыбак выкинул одну рыбину в воду, их осталось (-2) — 1 = -3. Потом он ушел, унося (-1) рыбу. Рыб стало (-3) — (-1) = -2. Второй и третий рыбаки просто повторили поступок своего товарища.
Из книги "Физики продолжают шутить".
На самом деле решение Дирака, хоть и остроумно, но, строго говоря, неверно, и во всяком случае неполно. Приведем полное, "математическое" решение, т. е. найдем ВСЕ решения.
Решение.
Пусть в начале рыб было n0 (количество, после того, как уехало 0 рыбаков). Первый рыбак выбросил одну (лишнюю) рыбину (n0 — > n0 — 1), после чего количество рыбин стало делиться на 3, и взял 1/3 оставшегося улова, и после себя он оставил n1 = (2/3)∙(n0 — 1) рыбин. Аналогичным образом действовали и остальные рыбаки, так что после отъезда 2-го рыбака рыб осталось n2 = (2/3)∙(n1 — 1), а после отъезда 3-го — n3 = (2/3)∙(n2 — 1). Подставляя в последнее равенство выражения для n2 и n1, получаем:
В итоге получаем уравнение, требующее разрешения в целых числах:
8n0 — 27n3 = 38.
Для упрощения расчетов имеет смысл уменьшить входящие в уравнение числа перейдя к новым переменным n0 = n0 + k, n3 = n3. Если взять k = 5, то уравнение превратится в
27n3 — 8n0 = 2. (1)
Это уравнение имеет вид
ах — by = с (1')
т. е. является диофантовым уравнением, и нужно найти все решения данного уравнения. Как это сделать?
Взглянем на уравнение (1') с точки зрения теории сравнений. В самом деле, требуется найти такое число х, что ах отличается от заданного числа с на слагаемое, кратное Ь. Иными словами, разность ах — с делится на Ь, т. е. (ах — с) = ()(mod b) или