Статья проверена участником José Monteiro
Эта статья написана в рамках спринта

Абсурдотека:Поиск иголки в стоге сена

Материал из Абсурдопедии
Перейти к навигацииПерейти к поиску
Дано
Найти


Постановка задачи[править]

Дано:

  • стог сена объёмом 1 кубический метр (наностог) (1)
  • как минимум две иголки в стоге сена: одна иголка ледяная, а другая лубяная костяная, другая железная. (2)

Задача-минимум:

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

Задача-максимум:

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

Подготовительные соображения[править]

Оценка сложности алгоритма полного перебора вариантов[править]

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

Сперва рассмотрим упрощённый случай — куб сена (стог сена строго кубической формы). Разобьём его на множество маленьких кубиков со стороной Δ. Оценим присутствие иголки в кубике. Берём первую попавшуюся точку маленького кубика. Если она железная или костяная — присутствие равно Δ³, если же там воздух или сено, то наличие иголки равно нулю. На этом этапе нас не волнует, есть ли иголка где-то ещё в этом кубике, кроме той единственной точки, которую мы проверили.

Устремим Δ к нулю и просуммируем значения по всем маленьким кубикам. Если от того, как мы выбирали точки внутри маленьких кубиков, результат меняется меньше чем на α, притом α уменьшается при уменьшении Δ, то наличие иголки в стоге сена можно научно оценить.

Назовём сумму-результат тройным интегралом I функции состояния иголки по кубу сена.

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

Лемма 1
Интеграл I равен сумме объёмов всех иголок.

Таким образом, мы сразу узнаём количество спрятанных иголок. А также будем в курсе, если нас обманули и иголок там нет.

Лемма 2
Шанс с ходу найти иголку в стоге сена равен I/Δ³.

Отсюда запишем

Следствие
Сложность нахождения иголки методом перебора растёт как O(n³), где n — сторона стога.

Такой метод, как правило, неприемлем для практических вычислений (например, если иголку надо найти срочно: здесь и сейчас).

Решаемость задачи[править]

Теорема 1 [о корректности задачи]
Пусть дана задача (1), (2). Тогда найдутся такие две иголки, которые будут удовлетворять условиям задачи.
Теорема 2 [о решаемости в срок]
Пусть стог задачи (1), (2) ограничен сверху, снизу и сбоку. Тогда для любого диаметра иголки ε>0 время её нахождения конечно.

Более быстрые решения[править]

Теорема 3 [о неоднородном стоге]
Существует алгоритм решения задачи (1), (2) со сложностью менее O(n³), если стог сена вместе с иголками не является однородным.
Пояснение
Иными словами, возможно более быстро найти любую иголку, кроме сделанной из сена.

Собственно решения[править]

Магниты[править]

Воспользуемся известным из физики свойством: железная иголка стремится к магниту («стремится» в смысле нормальной метрики трёхмерного пространства, то есть если предположить, что теорема Пифагора применима). Поместим стог сена в томограф и выудим все такие иголки. Условие (2) задачи более не выполняется, следовательно, теорема 3 (о неоднородном стоге) неприменима. Быстрого способа найти костяную иглу нет. Правда, есть вариант с рентгеном, о котором мы расскажем вам позже.

Просеивание. Гауссовское распределение[править]

Будем кидать сено в решётку, за которой расположены вертикальные столбики. Сено будет постоянно застревать в решётке; отсеем его. Иголка же упадёт вниз, притом с вероятностью 99,7 % окажется не далее, чем на три деления от точки сброса, справа или слева.

Применение принцессы[править]

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

Например, как известно из многочисленных авторитетных источников (художественной литературы), некая принцесса показала фантастические способности к обнаружению всего лишь одной горошины в своих огромных покоях, притом неизменно находила её каждый день (хотя любой другой человек повернулся бы на бок и не ворочался), в связи с чем не высыпалась, ходила наутро с синяками под глазами и радовала местный завод по производству косметики многомиллионными заказами. Впрочем, это всё детали, неважные для нашей задачи. Просто пригласите принцессу отдохнуть на стоге сена, и иголку она незамедлительно найдёт.

Виртуальный тренажёр[править]

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

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

Иголка?Иголка?Иголка?
Ищите

См. также[править]