![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
redtigraЗадачка, приведенная ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
avva с какого-то сайта с собеседовательными тестами для программистов:
Вражеская подводная лодка движется в одном измерении по числовой оси. Её движение дискретно: она всегда находится на каком-то целом числе, и местоположение меняется раз в минуту. Лодка движется с постоянной скоростью вдоль оси, скорость - сдвиг по числовой оси в каждую минуту - тоже целое число. Ни местоположение лодки, ни скорость вам неизвестны.
У вас есть возможность стрелять в лодку торпедами раз в минуту, всякий раз выбирая какую-нибудь целую координату, в которую попадает торпеда. Задача: пользуясь неограниченными временем и количеством торпед, описать алгоритм, который позволит вам гарантированно поразить вражескую подлодку.
Он же в более поздем постинге приводит решение. Признаться, в первый момент я застряла намертво и не поняла ни аза. Затем поняла действие алгоритма, предполагающего, что начало движения - точка 0, а лодка двигается с положительной скоростью. Дальше уже стало легче. Обрадовал тот факт, что чмогла понять решение. Огорчил тот факт, что не сразу, с трудом, и вообще - сама бы явно не решила. Хоть на матмех иди учиться.
Вот доступно изложенное решение (с)pingva:
Лодка движется по закону x = x0 + n*v, так?
n - это номер минуты с начала охоты, т.е. число натуральное. x0, v - числа целые. Числа эти в каждом конкретном случае фиксированные и конечные, хотя вообще говоря могут быть сколь угодно больщими (по модулю)
Решение в лоб - перебрать _все_ возможные комбинации x0, v.
x0,v - это точки на двухмерной плоскости, с целыми координатами. Как нам последовательно перебрать все точки на этой плоскости? Будем двигаться по квадратной спирали начиная из центра координат, по точкам (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), (2,1) и т.д.
Каждую минуту мы будем пробовать очередной вариант и лупить "с упреждением" - т.е. с учетом прошедшего времени, т.е. по закону x0+n*v. Соответственно, какие-бы числа x0,v не были выбраны лодкой перед началом движения, в ту минуту, когда спираль докрутиться до точки x0,v мы ее поразим.
Такой подход используется для того чтобы показать, что все рациональные дроби (т.е. числа вида p/q) можно "сосчитать", т.е. каждому такому числу присвоить порядковый номер, хотя, казалось бы, рациональных чисел "гораздо больше", чем натуральных.
avva с какого-то сайта с собеседовательными тестами для программистов:Вражеская подводная лодка движется в одном измерении по числовой оси. Её движение дискретно: она всегда находится на каком-то целом числе, и местоположение меняется раз в минуту. Лодка движется с постоянной скоростью вдоль оси, скорость - сдвиг по числовой оси в каждую минуту - тоже целое число. Ни местоположение лодки, ни скорость вам неизвестны.
У вас есть возможность стрелять в лодку торпедами раз в минуту, всякий раз выбирая какую-нибудь целую координату, в которую попадает торпеда. Задача: пользуясь неограниченными временем и количеством торпед, описать алгоритм, который позволит вам гарантированно поразить вражескую подлодку.
Он же в более поздем постинге приводит решение. Признаться, в первый момент я застряла намертво и не поняла ни аза. Затем поняла действие алгоритма, предполагающего, что начало движения - точка 0, а лодка двигается с положительной скоростью. Дальше уже стало легче. Обрадовал тот факт, что чмогла понять решение. Огорчил тот факт, что не сразу, с трудом, и вообще - сама бы явно не решила. Хоть на матмех иди учиться.
Вот доступно изложенное решение (с)
pingva:Лодка движется по закону x = x0 + n*v, так?
n - это номер минуты с начала охоты, т.е. число натуральное. x0, v - числа целые. Числа эти в каждом конкретном случае фиксированные и конечные, хотя вообще говоря могут быть сколь угодно больщими (по модулю)
Решение в лоб - перебрать _все_ возможные комбинации x0, v.
x0,v - это точки на двухмерной плоскости, с целыми координатами. Как нам последовательно перебрать все точки на этой плоскости? Будем двигаться по квадратной спирали начиная из центра координат, по точкам (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), (2,1) и т.д.
Каждую минуту мы будем пробовать очередной вариант и лупить "с упреждением" - т.е. с учетом прошедшего времени, т.е. по закону x0+n*v. Соответственно, какие-бы числа x0,v не были выбраны лодкой перед началом движения, в ту минуту, когда спираль докрутиться до точки x0,v мы ее поразим.
Такой подход используется для того чтобы показать, что все рациональные дроби (т.е. числа вида p/q) можно "сосчитать", т.е. каждому такому числу присвоить порядковый номер, хотя, казалось бы, рациональных чисел "гораздо больше", чем натуральных.
