ещё раз о подлодке
Aug. 5th, 2002 07:13 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОбещанное решение задачи о подлодке.
Постараюсь объяснить как можно более подробно, но если останется непонятным, можно задавать вопросы.
Нарисуем в уме координатную сетку. Пусть ось 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 -- алгоритм ведёт счёт минутам, естественно), если бы именно эта точка была "истинной". Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любой точки на плоскости (хоть и очень медленно), и поэтому рано или поздно убъём подлодку.
