Ффу.

Задачка, приведенная avva с какого-то сайта с собеседовательными тестами для программистов:

Вражеская подводная лодка движется в одном измерении по числовой оси. Её движение дискретно: она всегда находится на каком-то целом числе, и местоположение меняется раз в минуту. Лодка движется с постоянной скоростью вдоль оси, скорость - сдвиг по числовой оси в каждую минуту - тоже целое число. Ни местоположение лодки, ни скорость вам неизвестны.

У вас есть возможность стрелять в лодку торпедами раз в минуту, всякий раз выбирая какую-нибудь целую координату, в которую попадает торпеда. Задача: пользуясь неограниченными временем и количеством торпед, описать алгоритм, который позволит вам гарантированно поразить вражескую подлодку.

Он же в более поздем постинге приводит решение. Признаться, в первый момент я застряла намертво и не поняла ни аза. Затем поняла действие алгоритма, предполагающего, что начало движения - точка 0, а лодка двигается с положительной скоростью. Дальше уже стало легче. Обрадовал тот факт, что чмогла понять решение. Огорчил тот факт, что не сразу, с трудом, и вообще - сама бы явно не решила. Хоть на матмех иди учиться.
Вот доступно изложенное решение (с) pingva:
( Read more... )

Ффу.

Задачка, приведенная avva с какого-то сайта с собеседовательными тестами для программистов:

Вражеская подводная лодка движется в одном измерении по числовой оси. Её движение дискретно: она всегда находится на каком-то целом числе, и местоположение меняется раз в минуту. Лодка движется с постоянной скоростью вдоль оси, скорость - сдвиг по числовой оси в каждую минуту - тоже целое число. Ни местоположение лодки, ни скорость вам неизвестны.

У вас есть возможность стрелять в лодку торпедами раз в минуту, всякий раз выбирая какую-нибудь целую координату, в которую попадает торпеда. Задача: пользуясь неограниченными временем и количеством торпед, описать алгоритм, который позволит вам гарантированно поразить вражескую подлодку.

Он же в более поздем постинге приводит решение. Признаться, в первый момент я застряла намертво и не поняла ни аза. Затем поняла действие алгоритма, предполагающего, что начало движения - точка 0, а лодка двигается с положительной скоростью. Дальше уже стало легче. Обрадовал тот факт, что чмогла понять решение. Огорчил тот факт, что не сразу, с трудом, и вообще - сама бы явно не решила. Хоть на матмех иди учиться.
Вот доступно изложенное решение (с) pingva:
( Read more... )