04.11.2021 07:09
yurixi 1 2800 Источник
Представьте, что работает у вас повар. Лучший повар во всём городе: он — также как все — закупает квадратные коржи у поставщика, но торты — только у него все получаются круглые. У всех пироги, а у него настоящие торты! Да ещё и пирожные идут к столу, разных форм. Вы бы сразу догадались, что он вырезает из квадратов круги и делает пирожные из остатков, и когда проверяете по весу соотношение веса пирожных и тортов составляет именно $(4-\pi)/\pi.$



А теперь представьте, что вы сам этот повар, а станок ровно вырезающий круги сломался, а на рынке только станки обрезающие прямоугольники — рынок порешал за унификацию. Хорошо, что 3D-принтер, использующийся для пирожных, может и круг напечатать, но чтоб ничего не изменилось надо массу доставленных коржей разделить по самой точной пропорции. Разумеется, можно было бы задать программу разделения квадратного коржа: отделить $\pi/4$. Но вот засада: ножи от поставщика имеют ограничение — нож может прицельно делить только на целое количество одинаковых кусков, и отрезать только один.

Для простоты обозначим $\pi/4=\vartheta$. Для числа $\pi$ есть удобное приближение $355/113$. Соответствующее приближение для $\vartheta$ будет $355/452$. Таким ножом без оптимизации надо будет сделать $355$ отрезов $1/452;1/451;1/450;...$, а это не так уж быстро. Но это — если резать со стороны отделения тортовой части. А если отрезать со стороны пирожных, то для дроби $1-355/452$ нужно будет $452-355=97$ отрезов. Уже лучше. Теперь надо разобраться как то же самое проделать ещё быстрее.

Эту дробь можно представить как сумму дробей с единицей в числителе.

$97/452=1/5+1/69+1/9173+1/1430437620$

Число $\pi$ можно приблизить этими дробями.

$\pi\approx4\cdot(1-(1/5+1/69+1/9173))=3{,}1415929... $

Только, дело в том, что после отделения $1/5$ отделять $1/69$ уже не от чего, целый корж уже разрезан.

Всё равно, первый отрез правильный. Пропорция деления оставшегося после него куска в $((1-1/5)-(1-97/452))/4\cdot5=33/1808$ требует $33$ отреза. После первого из них оставшаяся пропорция будет $32/1807$, затем $31/1806$, а уже $30/1805$ сокращается до $6/361$. Значит, отрезается $1/361$. Останется отрезать $1/72$. Всего шесть отрезов. $(5;1808;1807;1806;361;72)$. Вот мы и справились задачей.

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

Нож, который отделяет доли — всё же лучше, чем нож, который просто делит пополам. При отделяющем половину ноже программа действий следующая: разрезать текущую часть пополам, и если отрезано больше, чем надо, то второй кусок идёт на пирожные, а режется первый. Если меньше, то первый кусок идёт на торты, а режется второй.
Если правые части пойдут на пирожные, тогда после первого разреза надо резать правую часть, опять правую, левую, опять левую, правую, левую, левую, правую… Правилом для определения какую сторону резать будет представление числа $\vartheta$ в двоичной системе исчисления. За исключением смещённой (из-за деления на четыре) позиции точки, отделяющей целую часть, оно же будет представлением в двоичной системе числа $\pi$

$\pi={11.0010010000111111011010101...}_{2} $

Если воспользоваться преимуществом имеющегося ножа, смещением разреза, то направление перебора кусков можно не менять. И если откладываемые куски пойдут на торт, то сначала надо отделить половину:

$v_0=\vartheta=0{,}78539...=w_0 $

$v_1=w_0-1/2=v_0-1/2=0{,}28539... $

$2v_1=2w_0-1=2v_0-1=0{,}57079...=w_1 $

Здесь $v_n$ — это сколько после шага $n$ осталось отделить, по весу.
$w_n$ — доля нужного остатка от оставшегося куска.

Затем опять половину:

$2v_2=w_1-1/2=2v_1-1/2=0{,}07079... $

$4v_2=2w_1-1=4v_1-1=0{,}1415926...=w_2 $

Потом отделить нужно будет восьмую часть:

$4v_3=w_2-1/8=4v_2-1/8=0{,}0165926... $

$32v_3=8w_2-1=32v_2-1=0{,}1327412...=w_3 $

Расчёт этих остатков представлен следующим образом:

$w_0=\vartheta \\w_1=\vartheta\cdot2-1 \\w_2=(\vartheta\cdot2-1)\cdot2-1 \\w_3=((\vartheta\cdot2-1)\cdot2-1)\cdot8-1 $

Рассчитать можно и дальше:

$ \\w_4=(((\vartheta\cdot2-1)\cdot2-1)\cdot8-1)\cdot8-1 \\w_5=((((\vartheta\cdot2-1)\cdot2-1)\cdot8-1)\cdot8-1)\cdot 17-1 \\w_6=(((((\vartheta\cdot2-1)\cdot2-1)\cdot8-1)\cdot8-1)\cdot 17-1)\cdot19-1$

Последовательность коэффициентов выглядит так:

$R_\rightarrow : 2,2,8,8,17,19,300,1991,\\2492,7236,10586,34588,63403,70637,1236467,\dots $

Это разложение для $\vartheta$ начиная с восьмёрок повторяет последовательность A006784 — это разложение для $\pi$.

Здесь можно заметить кое-что странное. Числа увеличиваются. Казалось бы, бо́льшие числа говорят о большей точности. Но здесь не тот случай, когда чем больше тем лучше. Это похоже на пробуксовку.

Если первый отрез делать со стороны пирожных, то отделять нужно не половину, а, как уже выяснили, одну пятую.

$v_0=1-\vartheta=0{,}21460...=w_0 $

$v_1=v_0-1/5=0{,}0146018... $

$5v_1=5v_0-1=0{,}073009...=w_1 $

Вся последовательность делений будет выглядеть так:

$R_{\leftarrow}:5,14,46,56,315,2024,3364,3786,\\6302,35677,347917,870105,2652048,... $

И здесь величина доли только возрастает.

Вспомнив о режущем пополам ноже можно предположить, что если периодически менять сторону, с которой отрезать куски, то дело пойдёт веселее. Только, для простого ножа вполне ясно, когда менять сторону, а для нашего — не совсем.

Когда мы делаем отрез, мы не только выбираем число для доли. Одновременно надо выбрать, какую из частей будем резать дальше и куда пойдёт та часть, которую откладываем — на торт или на пирожное. Это четыре различных варианта действий.

Если мы можем отрезать на выбор слева или справа от идеальной пропорции, то у нас есть простой критерий выбора: чем ближе будет отрез, тем точнее выбор. Но если учесть, что за два последовательных отреза теоретически можно приблизиться ближе через тот, первый шаг которого был дальше — тогда возможны и другие критерии.

Рассмотрим по порядку все четыре варианта отреза.

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

Своевременный вопрос: как выбирать следующий кусок для разрезания? Если разрез происходит пополам, то разницы между кусками нет, выбирать между ними не нужно. Но если делитель больше двух, выбор происходит между бо́льшим куском и меньшим. Выбор для разреза меньшего куска, конечно, лучше приблизит отрез, но при превышении делителем некоторого значения отрез зайдёт дальше точного отреза и после этого придётся сменить направление — точнее, сам отрез будет уже другого типа. При выборе большего куска, соответственно, направление можно и не менять. Но можно и поменять. Как-то уже не так ясно.

Так что посчитаем. Пусть $v_0$ — величина нужного отреза, отсчитывая с левого края. Складывать куски будем слева на торт, справа на пирожные. Увеличение дробности смещает отрез влево. Первый вариант отреза это когда левый кусок откладывается налево, для следующего отреза берётся правый кусок.

$v_{n}=v_{p}-1/(k_pn) \\k_n=k_p\cdot n \\w_\swarrow=nw_p-1 $

Судя по множителю уменьшения остаточного объёма, при большом числе дробления остаточный объём почти не меняется.
Второй вид отреза — когда отрез делается так же, но налево откладывается правый кусок, а разрезан будет левый. Всё равно что перевернуть схему отреза. Или перевернуть нож, чтобы при увеличении числа дробности он смещался бы не влево, а вправо.

$v_n=v_p-(n-1)/(k_pn) \\k_n=k_p\cdot n \\w_\searrow=nw_p-(n-1) $

Рассмотрим ситуацию с последовательным использованием только этого вида отреза. На первом шаге отрежем половину, на втором шаге тоже половину. Вообще-то, можно было сразу на первом шаге поделить на четыре. А на следующем шаге будет:

${3\over4}+{1\over4}\left({1\over2}\right)={7\over8}>{2\pi\over8}=\vartheta $

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

Третий и четвёртый виды отреза — такие же как первый и второй, только отделённый кусок откладывается в другую сторону. Поэтому величина остатка для отделения не меняется.

$v_n=v_p \\w_\nearrow=(n/(n-1))w_{p}=w_{p}(1+1/(n-1)) $


Четвёртый вид:

$v_n=v_p \\w_\nwarrow=nw_{p}$

Да, у этого вида отреза формула самая простая: увеличение доли остатка в разрезаемом кусочке в $n$ раз. Но взамен, повторять такой отрез несколько раз становится бессмысленно: можно на первом шаге использовать произведение всех чисел.

После этого можно соорудить программку, которая покажет результаты соревнования с перебором всех видов и степеней отреза.

***

Особенность нашей задачи в том, что в ней речь идёт не о произвольной дроби, а о дроби, имеющей прямое отношение к кругу. Так что, гамма-повар решил бы эту задачу по-другому.

Представьте единичный круг, на котором в вертикальном направлении вниз от центра поставлена точка. Если эта точка будет двигаться по кругу, то координата вдоль этого направления будет косинусом этого сдвига. Теперь можно добавить ещё одну точку на том же месте, но двигаться она будет только горизонтально. Можно связать точки так, что центр окружности, первая точка и вторая точка — все три лежали бы на одной линии.
Косинус сдвига первой точки тогда будет обратен расстоянию от центра до второй.

$\cos(s)=\frac{1}{\sqrt{1+x^2}}$

Дальше можно выяснить взаимосвязь скоростей. Различие скоростей состоит в различие направлений и различном удалении от центра. Что приводит к тому, что скорость первой точки пропорциональна скорости второй точки с коэффициентом косинус в квадрате.

$v(s)=\cos^2(s) $

А значит, пропорционально дроби

$v(s)=\frac{1}{1+x^2} $

Которую можно развернуть

$v(s)=\frac{1}{1+x^2}=1-\frac{x^2}{1+x^2}=1-x^2+x^4-x^6+x^8-x^{10}+\dots $

И при интегрировании скорости точки зависимость сдвига первой точки от сдвига второй будет выражаться

$s=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{11}}{11}+\frac{x^{13}}{13}-\dots $

Для числа $\pi$ это станет рядом Лебница

$\frac{\pi}{4}=\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\dots $

Этот ряд можно удвоить, со сдвигом копии на одну позицию.

$2\cdot\frac{\pi}{4}=\frac{1}{1}+\left(\frac{1}{1}-\frac{1}{3}\right)-\left(\frac{1}{3}-\frac{1}{5}\right)+\left(\frac{1}{5}-\frac{1}{7}\right)-\left(\frac{1}{7}-\frac{1}{9}\right)+\dots $

$\frac{\pi}{2}=\frac{1}{1}+\frac{2}{3}-\frac{2}{3\cdot5}+\frac{2}{5\cdot7}-\frac{2}{7\cdot9}+\frac{2}{9\cdot11}-\frac{2}{11\cdot13}+\frac{2}{13\cdot15}-\dots $

Проделав то же самое ещё раз, только начиная со второго члена суммы, и сразу поделив на два, получим:

$\frac{\pi}{2}=\frac{1}{1}+\frac{1}{3}+\frac{4}{3\cdot5}-\frac{4}{3\cdot5\cdot7}+\frac{4}{5\cdot7\cdot9}-\frac{4}{7\cdot9\cdot11}+\frac{4}{9\cdot11\cdot13}-\dots$

Ещё раз, начиная с третьего слагаемого:

$ \frac{\pi}{2}=\frac{1}{1}+\frac{1}{3}+\frac{2}{3\cdot5}+\frac{2\cdot6}{3\cdot5\cdot7}-\frac{2\cdot6}{3\cdot5\cdot7\cdot9}+\frac{2\cdot6}{5\cdot7\cdot9\cdot11}-\dots $

Дальше с четвёртого:

$\frac{\pi}{2}=\frac{1}{1}+\frac{1}{3}+\frac{2}{3\cdot5}+\frac{2\cdot3}{3\cdot5\cdot7}+\frac{2\cdot3\cdot8}{3\cdot5\cdot7\cdot9}-\frac{2\cdot3\cdot8}{3\cdot5\cdot7\cdot9\cdot11}+\dots $

Проделав последовательно со всей суммой получим:

$\frac{\pi}{2}=\frac{1}{1}+\frac{1}{3}+\frac{1\cdot2}{3\cdot5}+\frac{1\cdot2\cdot3}{3\cdot5\cdot7}+\frac{1\cdot2\cdot3\cdot4}{3\cdot5\cdot7\cdot9}+\frac{1\cdot2\cdot3\cdot4\cdot5}{3\cdot5\cdot7\cdot9\cdot11}+\dots$

Произведение в знаменателе это двойной факториал.

Это преобразование из одного ряда в другой

$\frac{\pi}{4}=\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}=\frac{1}{2}\sum_{n=0}^{\infty}\frac{n!}{(2n+1)!!}$

Основано на равенстве

$\sum_{n=0}^{\infty} \frac{C_n^{\,n-k}}{2^{n+1}}=1$

При $k\geqslant0$.

Образное объяснение такое: если у вас есть ряд аккумуляторов, каждый из которых за один временной промежуток отдаёт половину своего заряда соседнему аккумулятору справа, получая при этом половину заряда соседа слева, то начав заряжать что-нибудь с начала ряда и двигаясь последовательно, вы всё равно используете весь их заряд. Сумму можно переписать как

$\frac{\pi}{2}=1+\frac{1}{3}\left(1+\frac{2}{5}\left(1+\frac{3}{7}\left(1+\frac{4}{9}\left(1+\frac{5}{11}\left(1+\dots\right)\right)\right)\right)\right) $

Теперь можно обе части поделить на два, вернувшись к определению $\pi/4$

$\frac{\pi}{4}=\frac12+\frac{1}{3}\left(\frac12+\frac{2}{5}\left(\frac12+\frac{3}{7}\left(\frac12+\frac{4}{9}\left(\frac12+\frac{5}{11}\left(\frac12+\dots\right)\right)\right)\right)\right) $

Если из множителей перед скобками выделить одну вторую, то получится:

$\frac{\pi}{4}=\frac12+\frac12\cdot\frac{2}{3}\left(\frac12+\frac12\cdot\frac{4}{5}\left(\frac12+\frac12\cdot\frac{6}{7}\left(\frac12+\frac12\cdot\frac{8}{9}\left(\frac12+\dots\right)\right)\right)\right) $

Дроби перед скобкой можно преобразовать по принципу

$\frac{n-1}{n}=1-\frac{1}{n}$

Получится:

$\frac{\pi}{4}=\frac12+\frac12\left(1-\frac{1}{3}\right)\left(\frac12+\frac12\left(1-\frac{1}{5}\right)\left(\frac12+\frac12\left(1-\frac{1}{7}\right)\left(\frac12+\dots\right)\right)\right) $

Сумма выглядит как сумма двух слагаемых: половины и половины, умноженной на что-то ещё, меньше единицы. То есть, на первом шаге от единицы отделяется половина, и дальше определяется, какая часть остатка будет отделена точно так же. У второго слагаемого есть множитель $1-\frac{1}{3}$, который говорит, что треть точно не входит в общее количество, и не только отделяется, но и откладывается. А оставшийся множитель внутри повторяет эти два деления.

Это значит, что для деления коржа есть простой алгоритм:

  1. Половину остатка отправить на торты
  2. Третью часть остатка отправить на пирожные
  3. Половину остатка отправить на торты
  4. Пятую часть остатка отправить на пирожные
  5. Это цикл из двух действий, только знаменатель дроби отделения для пирожных каждый раз увеличивается на два.




Задачка решена. Точность обеспечена.

Комментарии (1)


  1. roboter
    04.11.2021 11:22
    #23666480
    +9

    А Вы посчитали сколько на ноже остаётся?