Абсурдотека:Поиск иголки в стоге сена
| Библиотека нетленной классики |
| Абсурдотека |
|---|
 |
| Книжные завалы |
| Читальный зал · Книгохранилище · Случайная книга |
| Найти книгу |
Постановка задачи[править]
Дано:
- стог сена объёмом 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 % окажется не далее, чем на три деления от точки сброса, справа или слева.
Применение принцессы[править]
Такой грубый приём, как применение сторожевых собак-поисковиков, которые бы чуяли местонахождение иголки, ненаучен в силу небольшой точности. Следует применять более эффективные приборы.
Например, как известно из многочисленных авторитетных источников (художественной литературы), некая принцесса показала фантастические способности к обнаружению всего лишь одной горошины в своих огромных покоях, притом неизменно находила её каждый день (хотя любой другой человек повернулся бы на бок и не ворочался), в связи с чем не высыпалась, ходила наутро с синяками под глазами и радовала местный завод по производству косметики многомиллионными заказами. Впрочем, это всё детали, неважные для нашей задачи. Просто пригласите принцессу отдохнуть на стоге сена, и иголку она незамедлительно найдёт.
Виртуальный тренажёр[править]
Ниже вам представлен виртуальный тренажёр, с помощью которого вы можете наловчиться искать иголки в стогах сена. В дальнейшем, встретившись с проблемой поиска иголки лицом к лицу, вы сможете использовать навыки, приобретённые с помощью этого тренажёра, и найти иголку, не затрачивая практически никаких усилий. Тренажёр абсолютно безопасен, не вызывает раздражения кожи и спонтанной беременности, и только в редких и особо странных случаях возможен летальный исход, но даже если это произойдёт, Абсурдопедия гарантирует вам счастливое будущее.
Просто поводите мышкой по стогу с сеном, представленному ниже, и попытайтесь найти там иголку.
См. также[править]
