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

[avva]

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

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

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

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

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

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

Comments

[vrml.livejournal.com]

Нет уж - лбо нулевая, либо ненулевая :)
Бесконечно малыми бывают не числа, а относительные величины.

[ska-o.livejournal.com]

Я не совсем понял, что такое относительные величины в этом контексте и чем они отличаются от чисел. В общем, если повторить Ваши рассуждения для неподвижной лодки, результат будет тоже 0 :-)

[vrml.livejournal.com]

В этом контексте и я не вижу относительных величин :)
А вот что такое - "бесконечно малое число" (хотя бы и в этом контексте)? Пример хотя бы одного такого числа?
А результат - да, для неподвижной лодки будет тот же. :) Но ведь нам нужен общий случай, а не частный...
Возможно, ошибкой, которую упомянул Анатолий, является вообще использование вероятности - так как движение лодки не случайно.
Я тоже подумала сначала о счетных множествах, но это направление показалось бесперспективным (на основании каких-то бессвязных ощущений). Интересно, действительно, каково их доказательство.

[ska-o.livejournal.com]

Если быть строгим, то я вообще не употребил термин "бесконечно малое число", хотя ничего бы страшного в этом не было. Если угодно, вероятность поражения одним выстрелом -- бесконечно малая величина, а не нулевая. По-моему, ошибкой является то, что Вы не зрите в корень :-)

Вообще-то, мы отвлеклись от решения задачи...