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

[avva]

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

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

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

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

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

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

Comments

[avva.livejournal.com]

Значит, будем стрелять по ((-1)^n)*2*(n^3)

Вот этот шаг неверный, не поймаете так ;)

[pingva.livejournal.com]

да, я не успел додумать.

Snyder все испортил :) - свел все построению N<->Q, которое с первого курса анализа все помнят, и решать (т.е. именно писать алгоритм) сразу стало неинтересно :)

[snyders.livejournal.com]

Сорри, что испортил, кстати там внизу интересное продолжение.