0,0
рейтинг
15 марта 2013 в 13:09

Разработка → Иголка, нитка и число пи

Этот пост поможет вам выкрутиться из довольно-таки щекотливой ситуации. Скажем, вы заперты в комнате, у вас есть моток ниток и иголка, и от вас настойчиво требуют посчитать приблизительное значение числа Пи, используя лишь эти предметы, ну, всякое бывает, знаете. Так вот, сегодня слушая на курсере курс по матану Пенсильванского университета, я вдруг узнал, как это сделать. Вот чего я и предположить не мог, так это того, что число Пи скрывается и тут. Оказалось, что корни этого вопроса уходят аж в 18 век, когда Жорж-Луи Леклерк де Бюффон поставил себе следующую задачу: «предположим, пол сделан из деревянных полосок двух цветов, они чередуются; какова вероятность того, что брошенная иголка упадет так, что будет пересекать линию состыковки двух полосок?» Симуляцию этого процесса и ответ на вопрос можно найти под катом.



Симуляция


Чтобы не портить интригу, начнем, пожалуй, с эксперимента. Итак, у нас имеется множество иголок длины L и моток ниток зеленого цвета. Нанесем на поверхность некоторое количество параллельных отрезков одинаковой длины на расстоянии L друг от друга.



Кинем на это поле 100 иголок.



Пожалуй, мало. Добавим еще 900 и отметим те иголки, которые пересекают нити, красным цветом.



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



Если бросить 10000 иголок, то картина будет более точной.



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



Для 10000 иголок уже точнее.



Если найти среднее из последних пяти тысяч членов ряда мы получим 3.141685, в то время как число пи равно 3.141593.

В общем, ни для кого уже не секрет, что последний ряд сходится к числу Пи. Но как такое могло произойти? Я узнал об этом на 28 году жизни из вышеупомянутого курса. Окунемся в матан.

Теория



Будем рассматривать иголку и ближайшую от нее линию справа. Расстояние от левого конца иглы обозначим h, угол отклонения от линии — a.



Очевидно, что длина противоположного катета от угла а будет равна синусу угла, умноженного на длину гипотенузы. Тогда мы можем утверждать, что если h меньше либо равна катету напротив угла а, то игла пересекает нить. Изобразим график:




Если мы посчитаем для каждой брошенной иголки h и a и отметим эти точки на предыдущем графике, то картина будет следующая:



Таким образом, вероятность того, что иголка пересечет нить, будет равна отношению площади фигуры под графиком к площади прямоугольника, то есть Пи, умноженное на длину иголки.



Отсюда и получается искомая аппроксимация числа Пи, что и показал опыт в первой части.

Ссылки


Павел Нестеров @mephistopheies
карма
80,2
рейтинг 0,0
data scientist
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

  • +15
    Сюжет напоминает киноленту «Пила».
    • +7
      Скорее «Куб»
      • +9
        Хорошо хоть не «Игры разума», а то было бы примерно так — "… иголки говорят со мной, и каждая твердит свою версию, чему равно число Пи. Мне же нужно расслышать среди них правильный ответ"
        • +5
          Извините что пишу тут (повыше), просто мне кажется, что это будет интересно многим.
          Я вспомнил еще одну красивую задачку, где возникает число pi.

          1) Представьте, себе два одинаковых упругих шарика массой m. Один шарик покоится чуть поотдаль от упругой стенки, а второй мячик налетает издалека перпендикулярно стенке на покоящийся мячик. Давайте проследим за тем, что будет:
          Так как мячики имеют одинаковую массу, то при ударе налетающий шарик остановится, передав всю свою скорость второму шарику. Второй шарик полетит в сторону стенки, отскочит от нее и полетит обратно к первому шарику. Ударит его, передав обратно всю скорость. В итоге будет 3 столкновения.

          2) Теперь представьте себе, что масса первого налетающего шарика 100m, а масса покоящегося m. Тогда из-за того, что масса налетающего мячика слишком большая, при первом столкновении, он передаст только часть своего импульса легкому шарику. Шарик полетит на стенку, вернется обратно, опять отскочит от тяжелого шарика к стенке, потом вернется…
          В итоге будет 31 столкновений.

          3) Если масса первого шарика 10 000m, то будет 314 столкновений

          4) Если 1 000 000m, то будет 3141 столкновений

          ну и так далее.
          • +1
            Интересная задачка. Какая-то смесь афинных преобразований, элементов комбинаторной геометрии и хорошего воображения. Насколько я понимаю, ответ будет ceiling(PI/atan(1/sqrt(M)))-1, что при больших M примерно равно [sqrt(M)*PI]. Но если не повезёт, и в каком-то месте числа pi будет очень много девяток подряд (вдвое больше, чем цифр перед ними), то при соответствующем M получится одно лишнее столкновение :)
    • +52
      … Я хочу сыграть с тобой в игру. У тебя есть 1000 иголок и один час, чтобы определить число Пи с точностью до шестого знака, иначе я буду определять его сам, намного точнее, скинув на тебя еще миллион иголок.
      • +6
        Как хорошо, что я число Пи с точностью до 14 знака помню.
        • +3
          Эх, а я только до седьмого после запятой (
        • 0
          Хм, я только до 11 знаю, русский стишок. Вроде как немецкий был длиннее, или есть ещё какой-то фокус?
          • 0
            А что за стишок?
            Я просто еще в универе зачем-то запомнил 18 разрядов (в основном парами, там близкие легко запоминающиеся группы есть).
            • +22
              Я его в какой-то детской книжке по математическим головоломкам вычитал ещё в начальной школе, помню до сих пор :-S

              «Это я знаю и помню прекрасно, пи многие знаки мне лишни, напрасны»

              Число букв в каждом слове — очередной разряд.
              • 0
                Спасибо
              • +10
                Наконец понял, зачем нужна возможность добавлять комментарии в избранное.
                • 0
                  А вы его уже не забудете и так :-) Въедливый
                  • +3
                    Я его уже три раза успешно забывал, например.
              • +6
                Этот мне известен, но там надо буквы пересчитывать — впрочем, если вас заперли в комнате, как предполагалось выше, то время на это есть.
                А я использую другой, который сразу дает запись числа:

                Надо просто постараться и запомнить все как есть:
                три, четырнадцать, пятнадцать, девяносто два и шесть.


                Соответственно, 3.1415926 вспоминаются сразу, без вычисления количества букв.
                • +4
                  Я также запоминал, только в конце 654 легко присоединилось: три, четырнадцать, пятнадцать, девяносто два, шестьсот пятьдесят четыре )
                  • +4
                    Не в тему, но моя любимая фраза для запоминания корня из двух (тоже надо считать число цифр в каждом слове):

                    Я Маша, я дура, но я вот взяла корень из двух.

                    Фразе меня научил мой друг, адепт Красноярской Летней Школы (КЛШ).
                  • +5
                    Простите, но
                    легко присоединилось: три, четырнадцать, пятнадцать, девяносто два, шестьсот пятьдесят четыре )
                    мне напоминает исключительно
                    Раз, два, три, четыре, пять
                    С детства с рифмой я дружу
                    Как вы это запомнили вообще?
                    • 0
                      Кто бы знал бы :) Просто запомнилось в таком варианте звучания.
                    • 0
                      Просто 654 — это обратный счет)) А еще 54 — это номер моего региона)
                  • 0
                    Вообще число пи как-то так построено гармонично, что легко запоминается. Я вот помню до 18 — вначале сам стишок, а потом легко присоединяется пять-три-пять восемь-девять-семь-девять три-два-три.

                    И да, советую не округлять при запоминании, иначе захотите запомнить больше — возникнут проблемы.
              • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Я запомнил мнемонику «How I want a drink, alcoholic of course, after the heavy lectures, involving quantum mechanics.»

            Сейчас погуглил — есть намного более крутые и длинные мнемоники: www.komplexify.com/math/humor_pure/PiMnemonics.html
    • +10
      Если использовать иголку и много раз посмотреть фильм «Пила», то задачу можно решить так:

      1. Измеряем длину нити иголками, пусть длина ее k*ИГ (1 ИГ — длина иголки);
      2. Вытаскиваем и ломаем свою плечевую кость (допущение, что на сломе кость — идеальная окружность);
      3. Наматываем нитку на край кости как можно больше раз, к примеру n раз и еще остается маленький огрызок, длину которого мы только примерно можем замерить в дробях от ИГ, обозначим его ОГ. Выписываем формулу: n*Д*Пи+ОГ = k*ИГ
      4. Находим диаметр (Д). Для этого отрываем по мальким кусочками нити и откладываем диаметр кости m раз. Измеряем ниткой длину получившейся зебры, z*ИК. Вычисляем диаметр Д = z*ИК/m;
      5. Находим Пи. Пи = (k*ИГ-ОГ)/(z*ИК*n/m)

      6. Если делать много измерений, то погрешность определения длины огрызка не будет играть большой роли.
      • НЛО прилетело и опубликовало эту надпись здесь
      • +4
        Если делать много измерений
        Т.е. вы полагаете одной кости может не хватить?
        • 0
          :)
          n и m должны быть большими.
      • +20
        Да я бы на что другое намотал… погрешность будет примерно такая-же, только ломать не надо.
        • +1
          На череп? =)
          • +5
            На *** намоталъ
            • 0
              Но почему не намотать на иголку? Надо будет только как-нибудь найти отношение длины иголки к толщине.
              • 0
                Потому что иголка считается бесконечно тонкой.
                Кстати, наматывая плотно нитку на иголку или линейку — можно определить толщину нити. К примеру намотали 5 сантиметров, сделали 100 витков, толщина нити: 0.05/100 = 0.0005m.
                • 0
                  Мне легче запомнить сколько у меня радиус диаметр и обхват. Про длинну говорить не буду
  • +7
    А нам это учитель в школе в 11 классе рассказывал. Очень хороший был учитель, любил математику.
    А ещё говорил, что бог знает на 5, я на 4, ну а с вами всё ясно :))
    • +4
      У нас в универе так же говорил препод по квантовой физике. Все-равно сдавали на 4 и 5 :)
      • 0
        А у нас по сопромату. И я до сих пор ему верю
        • 0
          У меня не было сопромата, так что возможно там преподы похлеще каких-то квантовых физиков :)
    • 0
      Наш учитель по физике в школе говорил такую же фразу :)
  • +3
    Об этом деле очень хороший фильмик есть у Numberphille (Brady Haran и Nottingham University) — Pi and Buffon's Matches.
    (А позавчера, в день пи они измерили пи с помощью пирожков — Pi with Pies).
    • 0
      блин чорт нада в послдений день масленицы измерить число пи блинами!
      • 0
        Можно даже каплями сметаны на одном большом.
        • 0
          месье знает толк -)
          • +2
            Или икрой. При применении черной можно достигнуть высокой точности!
  • +23
    Я этот замечательный факт читал у Якова Перельмана, «Занимательная алгебра».
    Там же есть гораздо более простое и красивое доказательство без всякого матана.

    Возьмём иголку и сломаем её в произвольной точке. Бросаем оба обломка одновременно и считаем количество пересечений ниток хотя бы одним из обломков на 1000 экспериментов. Очевидно, оно точно то же, что и для целой иголки.

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

    Теперь представим, что мы согнули иголку бесконечное число раз и получили ровную окружность. Исходя из рассуждений выше, количество пересечений линии согнутой в окружность иголкой на N экспериментов точно то же, что и для прямой иголки. А вот его посчитать тривиально — отношение диаметра окружности к расстоянию между линиями * 2 (всегда два пересечения) * N = 2N/пи.
    • +2
      Великолепно!!!
    • +3
      Что-то я с ходу не осознал, откуда берется «очевидно».

      Допустим, берем такую иголку, которая может пересечь только одну линию. Разломав на куски, вероятность падения хотя бы одним будет другая. Мы также будем получать случаи, когда оба куска падают на линии. С согнутой иголкой вообще проблемы. Совсем не независимые события.

      Ну и если бы было так просто, то вероятность падения длинной иголки равна была вероятности короткой иголки при той же решетке. Иглу можно гнуть в кольцо, а можно в спираль. Можно в зигзаг нулевой ширины и очень короткой длины.
      • 0
        Там было с картинками :) Без картинок правда не очень-то очевидно и трудно объяснять.
      • +6
        Матожидание суммы случайных величин равно сумме матожиданий как для независимых, так и для зависимых событий. Так что согнув иголку посередине, мы разделили случайную величину на две части, функции распределения у них те же, что у частей несогнутой иголки, а то, что изменилась зависимость между ними, на матожидание числа пересечений не влияет.
        Вероятность пересечения линии (точнее, матожидание числа пересечений) у половины иголки ровно вдвое меньше, чем у целой иголки. Поэтому, если мы сложим иголку пополам, то вероятность пересечения уменьшится вдвое, но в случае успеха у нас будет ровно два пересечения — матожидание останется прежним.
        Кстати, иголка вообще не нужна — можно было отрезать кусок нитки длины L, и бросать его — ведь среднее число пересечений зависит только от длины, а не от формы :)
        • 0
          А, точно. Извините, не внимательно читал. Пятница и рабочее время )))

          Я считал вероятность, а не число пересечений.
  • +5
    Если я не ошибаюсь, в какой-то своей книжке Арнольд приводит очень изящное решение этой задачи.
    Пусть длина иголки равна 1, и ширина между нитками тоже равна 1.
    1) Сдаем очень много экспериментов (скажем N) и посчитаем количество пересечений иголок с нитками.
    2) Пристально подумав, можно сообразить, что если иголки погнуть (сделать ломаную, состояющую из двух отрезков) то количество пересечений с нитками в среднем не изменится.
    3) Значит иголки, вообще можно гнуть сколько хочешь раз, и опять в среднем количество пересечений с нитками не изменится.
    4) Раз иголки можно превращать в ломаные, то перейдем к пределу и превратим каждую иголку в окружность периметра 1 (Диаметра 1/pi). Опять количество пересечений с нитками в среднем не изменится
    5) Так как теперь мы бросаем на плоскость не иголки, а окружности, то намного легче найти среднее количество пересечений. Действительно, диаметр окружности равен 1/pi, поэтому он с вероятностью 1/pi пересечет нитку. Но окружность пересекает нитку всегда в двух точках (если не брать в расчет событие вероятности ноль, когда окружность касается нитки). Поэтому на N бросаний будет 2N/pi пересечений.

    Задача решена. Вероятность пересечения иголки ниток равна 2/pi.
    • +9
      N мало, возьмем лучше K
      ©
  • –14
    Никогда не мог вникнуть в вышку, так как единственное применение в рельной жизни которе я понял — это вычисление площади под кривой. все остальное я просто не понимал зачем это нужно, а не могу себя заставить изучать то, что я не знаю зачем мне нужно.
    • +4
      Ну вы перегибаете палку. Из очевидных применений в реальной жизни. Пишу, что первое пришло на ум.
      1) Теория чисел — шифрование.
      2) Диффуры — да вообще везде нужны. Как, кто-то говорил, что если бог существует, то он очень любит дифференциальные уравнения.
      3) Геометрия кривых пространств — без нее не было бы общей теории относительности, а без этого ваш любимый GPS ошибался бы метров на 100.
      Ну и так далее…
      Ну самом деле список бесконечный.
      • –3
        вы меня не так поняли. под реальной я имею ввиду той с которой более 90% людей сталкиваются.
        вышку просто преподают много где в институте, совершенно не вдаваясь в объяснение того за каким макаром нужно научиться вычислять логарифм и прочее и куда это потом применить можно.
        • +1
          Тогда у вас получается, что в реальной жизни вообще никакие специальные знания не применимы (вряд ли есть хоть какая-нибудь область, в которой более 10% людей — специалисты), а значит и не нужны вообще.
          • +2
            В голову приходит кулинария :)
            • 0
              Наш преподаватель по вышке говорила, что если вы не можете сдать математику — вам дорога в кулинарный техникум:)
              • +2
                ну вот зря к кулинарии так относятся -) на самом деле там точный расчет, и серьезная теория в бэкграунде, начиная от того базовой физиологии до химии. Это как с пэхэпистами, порог вхождения в бизнес очень маленький, пэхэпистов дохрена, и усредненный пэхэпист это не очень умный и хороший программер. Но есть маленькая часть из пэхэпистов которые реально рулят, так и в кулинарии. Готовить начать может много кто, а реально круто сготовить, учесть все пожелания, добавить изюминку могут единицы.
    • НЛО прилетело и опубликовало эту надпись здесь
    • +5
      Анекдот: «Матан пригодился единственный раз в жизни, когда я уронил в унитаз связку ключей. Я взял кусок проволоки и согнул ее интегралом...»
    • +1
      И правильно, 4 класса церковно-приходской школы, научить читать-писать и шагом марш в большую жизнь, чтобы у специалистов под ногами на рынке труда не мешались :)
    • 0
      Для начала процитирую начало статьи:
      > Этот пост поможет вам выкрутиться из довольно-таки щекотливой ситуации. Скажем, вы заперты в комнате, у вас есть моток ниток и иголка, и от вас настойчиво требуют посчитать приблизительное значение числа Пи, используя лишь эти предметы, ну, всякое бывает, знаете.

      <irony>
      А теперь. Представьте — идёте вы спокойно по тёмной улице, никого не трогаете, а вдруг сзади подходят гопники и спрашивают косинус из 45… Ну всякое бывает, знаете.
      </irony>
      • 0
        image

        что то эта картинка вспомнилась сразу -)
      • 0
        √2 / 2

        Запомнить легко. Синус
        30°: √1 / 2
        45°: √2 / 2
        60°: √3 / 2
        Косинус в другую сторону. Тангенс/Котангенс — делением.
  • 0
    Не совсем в тему, но тоже клево: youtu.be/whYqhpc6S6g
  • 0
    Не могу похвастаться знанием математики, увы. Подскажите, пожалуйста, откуда в формуле вероятности взялось пи в знаменателе? При моих убогих знаниях, я бы предположил, что это сделано по причине того что фигура под графиком похожа на полукруг. Но это же явно неверно.
    • +1
      мы описываем каждую иголну как пару чисел: расстояние от левого края иголки до близжайшей правой нити и угол отклонения от нити.
      0 градусов — она перпендикулярна нити, 90 градусов вниз по часовой стрелке (угол пи/2) — она параллельна нити, 180 градусов она опять перпендикулярна нити (угол пи), если больше 180 то левый край поменялся с правым и опять угол отсчитывается от нуля, т.е. угол мы измеряем от 0 до 180 градувов (пи). образуется область длина иголки на пи — это всевозможные комбинации h и угла а.
      • 0
        Ааа! Вот спасибо, действительно понял.
  • +2
    нас по другому учили численно узнавать число Пи: бросая иголки на квадрат со вписанной окружностью
    • 0
      То ли Вас учили как-то странно, то ли так и не научили. На квадрат со вписанной окружностью иголки бросать незачем, достаточно бросать точки, называется «метод Монте-Карло».
  • 0
    Делали на лабораторных по физике классе в 10. Ну и смотрели, что будет, если поменять длину иголки или расстояние между полосками.
  • 0
    Не хватит только катушки и иголок:
    — Нанесем на поверхность некоторое количество параллельных отрезков одинаковой длины на расстоянии L друг от друга.

    Нужна еще линейка. Вообще же, нам об этом еще в школе говорили.
    • 0
      Зачем линейка? Нитки же есть. Правда, непонятно, чем их закреплять.
      • 0
        Извините, до меня дошло, что расстояние между нитками равно длине иголки.
  • 0
    Теперь Вам надо сделать следующий шаг — почитать статей про интегральную геометрию (а весь Ваш рассказ — маленький простой пример из нее) и потом рассказать нам, как (например) без бинаризации картинки (т.е. без выделения самих объектов) считать среднюю толщину/длину объектов на изображении и про прочие применения, гораздо более интересные, чем задача Бюффона.
  • +1
    Помню, как три года назад в реальности бросали иголку на разлинованный лист бумаги, после 10000 падений иголки мы получили пи равное 2.5, что сильно расстроило Все таки вероятностные методы не всегда работают так, как должны.
    • 0
      Значит нерандомно бросали)
      • 0
        Просто иногда действительно произвольные события даже при большом количестве повторов не дают рассчитанного теоретически процента удовлетворительных исходов. Параллельно с нами этим занимались еще две-три пары человек, у них получилось что-то близкое к 3.1, 3.2. при том, что они бросали иголку раз в двадцать меньше.

        При этом на компьютере такие эксперименты моделируются всегда с удовлетворительным результатом, так как компьютер почти всегда использует генератор псевдослучайных чисел, которые иногда дают гораздо более равномерное распределение значений, чем действительно случайные события.
    • 0
      А соблюдали условие, что длина иголки должна быть меньше расстояния между линиями, но близко к нему?
      У меня с киданием гвоздя на кирпичную кладку получилось 3.151… за 100 повторений, но гвоздь был подобран хорошо, да и кидание было достаточно рандомным.
      • 0
        Соблюдали. А вообще там точность зависит от отношения длины иголки к расстоянию между линиями. Точно не помню, но, вроде, когда расстояние между линиями короче иголки, то (при несколько других коэффициентах формуле), подбросить иголку достаточно меньшее количество раз (проверять не стали — и без того задолбались бросать).

        (Строго говоря мы тоже бросали гвоздь с откусаной шляпкой, на лист А3)
  • 0
    Эта задача была иллюстрацией на главной странице журнала Квант в каком-то из 70-ых годов.

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