задачки и головоломки

[avva]

Интересный ресурс: хранилище задач и головоломок, используемых во время интервьюирования программистов. Много знакомых и хорошо известных, но много и незнакомых. Большинство простые, но есть сложные и интересные.

Вот например забавная задачка, которая мне понравилась; не слишком сложная (хоть и из раздела hard):

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

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

Кстати, раз уж речь зашла о головоломках, вот незаменимый сайт, содержащий архив ньюсгруппы rec.puzzles: большое количество интересных головоломок на самые разные темы, с решениями. Там есть даже большой список загадок-"данеток" (иначе называемых "ситуации", а по-английски - Situation Puzzles).

P.S. А за ссылку на страницу компьютерных задачек спасибо горячему жирафу, а кому же ещё.

Comments

[malenkiy-scot.livejournal.com]

Подождите-ка, в условии ничего не говорилось про то, что лодка движется в одном направлении (было написано - в одном измерении). Если она движется только в одном направлении - задача элементарна!

[avva.livejournal.com]

Было написано: с постоянной скоростью, а это подразумевает, что в одном направлении (т.к. скорость - целое число -- это тоже было написано -- и таким образом включает в себя информацию о направлении).

Элементарна - это кому как, видимо. Если есть некий математический багаж и понимаешь, как его использовать - тривиально, действительно. Но не у всех есть этот багаж и не все догадываются, что его надо использовать.

[malenkiy-scot.livejournal.com]

Да, я уже понял. Торопливость...