![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ещё раз о подлодке
Обещанное решение задачи о подлодке.
Постараюсь объяснить как можно более подробно, но если останется непонятным, можно задавать вопросы.
Нарисуем в уме координатную сетку. Пусть ось X обозначает возможные точки начала движения лодки (все целые числа), а ось Y - возможную её скорость (тоже все целые числа).
Если мы подозреваем, что "истинной" является какая-то конкретная точка на этой плоскости, например, точка с координатами (2,-3) (означающая, что подлодка начинает движение в точке 2 и движется со скоростью -3 единицы в минуту), то мы можем проверить эту гипотезу выстрелом в любую минуту N. Для этого надо просто в минуту N выстрелить по числу 2 + (-3)*N. Если мы попадём по подлодке, значит, всё хорошо (это необязательно значит, что "истинной" была именно точка (2,-3) -- есть и другие точки, приводящие к тому же числу на N-ной минуте -- но нам важно, в конце концов, то, что мы попали по подлодке). Если мы промахнёмся, то как минимум эту точку мы отвергли в качестве возможной.
Если бы у нас был алгоритм, позволяющий последовательно "проверять на вшивость" все точки нашей плоскости одну за другой, то это решило бы задачу. Такой алгоритм перебирал бы точку за точкой, рано или поздно добираясь до любой точки на плоскости (если до тех пор не попал ещё в подлодку). Т.к. какая-то точка на плоскости является "истинной", то рано или поздно алгоритм бы до неё добрался и попал бы в подлодку (если не попал в неё ещё раньше). Это было бы гарантированным.
Естественно, не любой перебор точек одной за другой нам подходит. Например, представим себе алгоритм, который стреляет последовательно в числа: 1, 4, 9, 16, 25, 36, ... Его можно представить, в наших терминах, как алгоритм, к-й "проверяет на вшивость" последовательно одну за другой точки (0,1), (0,2), (0,3)... - т.е. исходит из предположения, что подлодка начинает движение в точке 0, и проверяет одну за другой все возможные положительные скорости (учитывая в своих выстрелах номер данной минуты, естественно). Понятно, что такой алгоритм никогда не поймает подлодку, для которой "истинной" является точка (-1, -1), например. Не поймает именно потому, что он не обходит все точки на плоскости - вместо этого он уходит в бесконечность по оси Y, оставляя все остальные точки неисследованными.
Но на самом деле есть простой алгоритм, "обходящий" все точки на плоскости, и его легко представить геометрически. Он просто обходит все точки по концентрическим квадратам. Сначала проверяет точку (0,0); затем все точки, лежащие на квадрате с центром в 0 и длиной стороны в 2 единицы (а именно, точки (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1) ); затем все точки, лежащие в следующем концентрическом квадрате - с центром в 0 и длиной стороны в 4 единицы, и так далее. Каждую точку он "проверяет на вшивость", стреляя в то число, где должна была быть подлодка сейчас (на данной минуте N -- алгоритм ведёт счёт минутам, естественно), если бы именно эта точка была "истинной". Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любой точки на плоскости (хоть и очень медленно), и поэтому рано или поздно убъём подлодку.
Постараюсь объяснить как можно более подробно, но если останется непонятным, можно задавать вопросы.
Нарисуем в уме координатную сетку. Пусть ось X обозначает возможные точки начала движения лодки (все целые числа), а ось Y - возможную её скорость (тоже все целые числа).
Если мы подозреваем, что "истинной" является какая-то конкретная точка на этой плоскости, например, точка с координатами (2,-3) (означающая, что подлодка начинает движение в точке 2 и движется со скоростью -3 единицы в минуту), то мы можем проверить эту гипотезу выстрелом в любую минуту N. Для этого надо просто в минуту N выстрелить по числу 2 + (-3)*N. Если мы попадём по подлодке, значит, всё хорошо (это необязательно значит, что "истинной" была именно точка (2,-3) -- есть и другие точки, приводящие к тому же числу на N-ной минуте -- но нам важно, в конце концов, то, что мы попали по подлодке). Если мы промахнёмся, то как минимум эту точку мы отвергли в качестве возможной.
Если бы у нас был алгоритм, позволяющий последовательно "проверять на вшивость" все точки нашей плоскости одну за другой, то это решило бы задачу. Такой алгоритм перебирал бы точку за точкой, рано или поздно добираясь до любой точки на плоскости (если до тех пор не попал ещё в подлодку). Т.к. какая-то точка на плоскости является "истинной", то рано или поздно алгоритм бы до неё добрался и попал бы в подлодку (если не попал в неё ещё раньше). Это было бы гарантированным.
Естественно, не любой перебор точек одной за другой нам подходит. Например, представим себе алгоритм, который стреляет последовательно в числа: 1, 4, 9, 16, 25, 36, ... Его можно представить, в наших терминах, как алгоритм, к-й "проверяет на вшивость" последовательно одну за другой точки (0,1), (0,2), (0,3)... - т.е. исходит из предположения, что подлодка начинает движение в точке 0, и проверяет одну за другой все возможные положительные скорости (учитывая в своих выстрелах номер данной минуты, естественно). Понятно, что такой алгоритм никогда не поймает подлодку, для которой "истинной" является точка (-1, -1), например. Не поймает именно потому, что он не обходит все точки на плоскости - вместо этого он уходит в бесконечность по оси Y, оставляя все остальные точки неисследованными.
Но на самом деле есть простой алгоритм, "обходящий" все точки на плоскости, и его легко представить геометрически. Он просто обходит все точки по концентрическим квадратам. Сначала проверяет точку (0,0); затем все точки, лежащие на квадрате с центром в 0 и длиной стороны в 2 единицы (а именно, точки (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1) ); затем все точки, лежащие в следующем концентрическом квадрате - с центром в 0 и длиной стороны в 4 единицы, и так далее. Каждую точку он "проверяет на вшивость", стреляя в то число, где должна была быть подлодка сейчас (на данной минуте N -- алгоритм ведёт счёт минутам, естественно), если бы именно эта точка была "истинной". Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любой точки на плоскости (хоть и очень медленно), и поэтому рано или поздно убъём подлодку.
no subject
??
(Anonymous) 2002-08-06 06:32 am (UTC)(link)Re: ??
Вообще говоря, можно сколько угодно осей добавлять; например, пусть подлодка изначально движется по плоскости, а не по прямой - нет проблем, будем обходить 4-х мерное простраство (2 координаты начального положения и 2 координаты скорости) 4-х мерными кубиками. И т.п.
Re: ??
Re: ??
no subject
Алгоритмическое программирование и филологию.
И ещё не мало весчей.
Просто поражаюсь на Вас.
no subject
(Anonymous) 2002-08-14 01:40 am (UTC)(link)Pro
Re:
(не говоря уж о сложности случайного выбора точек на плоскости).
no subject
(Anonymous) 2002-08-15 02:29 am (UTC)(link)Pro
no subject
no subject
(Anonymous) 2002-08-15 05:56 am (UTC)(link)Pro
Re:
Нет, гарантии такой нет, если нет эксплицитной формулы или другого способа показать, в какой конкретный момент будет поражена любая конкретная точка.
no subject
(Anonymous) 2002-08-15 06:30 am (UTC)(link)