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

[avva]

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

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

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

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

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

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

Comments

с добрым утром :)

[ex-olg.livejournal.com]

интересно, а на русском есть подобные ресурсы? не встречали?

Re: с добрым утром :)

[avva.livejournal.com]

С добрым утром и Вас ;) нет, не встречал.

Анатолий

[lz.livejournal.com]

Мне кажется, Вам будет интересна эта головоломка:
http://vad.spb.ru/www/xlam/WebLomka.htm
Спецально для интернет-профессионалов, да простится мне это новообразование.
На мой взгляд - есть очень красивые уровни

[(Anonymous)]

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

Re:

[avva.livejournal.com]

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

[pingva.livejournal.com]

подлодка движется по формуле:

x(n) = x0 + n*v,

где v - скорость подлодки, n - номер минуты с начала охоты, x0 - начальное положение.

n - натуральное, а v и x0 - целые.

Упростим задачу.

положим x0=0, а v будем считать натуральным (т.е. разрешив движение подлодки только "вправо")

Теперь перебираем возможные скорости, предполагая, что скорости v из {1,2,3,...} и перехватывая подлодку метким выстрелом в момент n по координате v*n, полагая v = n, т.е. стреляем по n^2.

Теперь положим, что двигаться она может в двух направлениях. Тогда каждый четный выстрел будем делать вправо, а каждый нечетный - влево, ((-1)^n)*2*n*n

Теперь разрешим подлодке двигаться из любой точки

тогда нам нужно будет перебирать еще и по всем возможным точкам (к черту оптимизацию, по крайней мере пока)

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

Черт, не успею додумать :), надо убегать.

[vrml.livejournal.com]

Значит, дано, что мы не знаем ни скорости лодки, ни положения. Следовательно, вероятность поражения лодки одним выстрелом - нулевая (согласно определению вероятности - т.к. число точек бесконечно), независимо от выбора точки. Допустим, мы пальнули в некую точку. Ничего нового про местоположение и скорость лодки мы при этом не узнали. Что изменится на втором выстреле? - тоже ничего. По индукции, во время любого n-го выстрела мы остаемся "при своих" - как и во время первого. Лодка где-то себе плавает, по-прежнему с неизвестной скоростью и неизвестно где. То есть все алгоритмы выстрелов, включая случайную последовательность, равноправны в том, что никакой гарантии поражения не дают.

Re:

[avva.livejournal.com]

Выглядит убедительно, но верным не является ;)
Не буду пока указывать на ошибку в этом рассуждении, но замечу, что решение у задачи есть.

[snyders.livejournal.com]

Показать что множество точек с координатами (x,y), x in N -- начальное положение, y in Z -- скорость равномощно N.

Какой-нибудь простой порядок обхода (если бы y > 0, то заметать угол например) накапливать счетчик t и стрелять в x+ty.

Кажется, лодке еще можно разрешить менять направление движения конечное число раз.

Re:

[avva.livejournal.com]

Только x in Z as well.

то заметать угол например

А так можно концентрические квадратики заметать, например.

лодке еще можно разрешить менять направление движения конечное число раз

Или вообще двигаться согласно любому алгоритму.

Боюсь, правда, что твой и мой комменты многим остануться непонятными, так что надо будет отдельную запись написать и там разъяснить решение подробнее.

[snyders.livejournal.com]

Да раз x in Z то самое естественное ходить по спирали.

>Или вообще двигаться согласно любому алгоритму.

Алгоритму неизвестному стрелку (я имел в виду, что можно позволить менять курс, в неизвестные стрелку моменты)?
Это мысль интересная -- алгоритмов счетное число, вопрос, как написать алгоритм, который будет перечислять все алгоритмы (это вроде можно сделать), и для данного алгоритма M получать M(t) = (x,y) координаты лодки. Это, разве, не эквивалентно to the halting problem?

Re:

[avva.livejournal.com]

Алгоритму неизвестному стрелку (я имел в виду, что можно позволить менять курс, в неизвестные стрелку моменты)?

Ага.

...как написать алгоритм, который будет перечислять все алгоритмы (это вроде можно сделать), и для данного алгоритма M получать M(t) = (x,y) координаты лодки. Это, разве, не эквивалентно to the halting problem?

То, что ты сказал, действительно эквивалентно - т.к. для данного алгоритма невозможно в общем случае определить, что он вообще останавливается и выдаёт какие-то координаты. Но задача тем не менее решаема, хотя обход получается менее тривиальным и решение, пожалуй, лучше оставить в качестве дополнительной задачи для тебя и для тех, кто прочитает этот коммент и понимает, о чём мы тут вообще беседуем ;)

[avva.livejournal.com]

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

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

Re: Анатолий

[avva.livejournal.com]

Спасибо ;) Честно говоря, лень немножко её проходить, да и похожую англоязычную я уже проходил когда-то. Но сам тип головоломки интересен, согласен.

[ska-o.livejournal.com]

Не нулевая, а бесконечно малая. Две большие разницы :-)

Re: с добрым утром :)

[ex-olg.livejournal.com]

ну, ладно. пожалуй, тогда вывешу в ЖЖ свою любимую загадку.

[pingva.livejournal.com]

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

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

[malenkiy-scot.livejournal.com]

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

[avva.livejournal.com]

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

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

[malenkiy-scot.livejournal.com]

Вот, видимо, наметка на решения общего случая: по 3-й оси (z) откладываем "алгоритмы" - n-нный знак в двоичном представлении z - направление движения в минуту n. И обметываем концентрические пожерьности кубиков.

[malenkiy-scot.livejournal.com]

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

[avva.livejournal.com]

Мне кажется, Вы под 'алгоритмом' поняли алгоритм изменения направления каждую минуту (при постоянной скорости), в то время как я имел в виду нечто куда более общее: алгоритм, решающий в минуту номер n, где быть лодке (без ограничений на скорость или её постоянство).

[malenkiy-scot.livejournal.com]

Вы шутите! Неужели, есть решение?

[malenkiy-scot.livejournal.com]

Аь, ну да: по одной оси - алгоритм (их, как известно, можно пронумеровать), по другой - время. Так?

[avva.livejournal.com]

Нет. Когда нумерация выдаст на-гора алгоритм, что с ним будем делать? Невозможно запустить его в надежде получить нужную координату, т.к. в общем случае не можем знать, остановится ли он когда-нибудь.