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

[avva]

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

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

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

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

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

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

Comments

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

[ex-olg.livejournal.com]

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

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

[avva.livejournal.com]

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

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

[ex-olg.livejournal.com]

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

Анатолий

[lz.livejournal.com]

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

Re: Анатолий

[avva.livejournal.com]

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

Re: Анатолий

[zc2.livejournal.com]

занятная штука... кто-нибудь прошел 9-й уровень? Я на нем заткнулся... :-(

Re: Анатолий

[nechaman]

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

[(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)

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

[avva.livejournal.com]

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

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

[pingva.livejournal.com]

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

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

[vrml.livejournal.com]

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

Re:

[avva.livejournal.com]

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

[ska-o.livejournal.com]

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

[vrml.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?

Значится, так:

[barabek.livejournal.com]

Shot(1) = 1;
Shot(N) = Shot(N-1) + N;

T.e. выстрелы будут по точкам 1, 3, 6, 10 ...

Если скорость лодки - V, мы ее поразим через [2V - 1] выстрелов

Re: Значится, так:

[avva.livejournal.com]

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

Re: Значится, так:

[gvadelupa.livejournal.com]

Даже если она вышла из точки 0 и движется вправо непонятно как этот алгоритм может работать. Поясните, пожалуйста, например, для V=2.

Avva, вы обещали выложить решение, не пора?

[cybergoblin.livejournal.com]

Решение в корне неверное:

во первых: если отправная точка для лодки (0,0), то она никогда не сможет оказаться в точке (1,1) т.к. расстояние до этой точки не целое число.

во вторых: если стрелять "с упреждением" то, наверное, второй точкой будет (0,2) третей (-3,0) и т.д. Этот алгоритм имеет смысл, если лодка движется в одном из четырех направлений, по осям "х" или "у" и точно известно, что она начала движение из точки (0,0).

НО! лодка вполне может оказаться в точке (4,3) которая выпадает из этого алгоритма, т. к. на ее проверку уйдет лишняя минута, и вы упустите лодку. На проверку же точек уйдет несоизмеримо много времени.

в третьих: по условию начальное положение лодки не известно и она вполне может находиться, например, в точке (3,0) и двигаться со скоростью 1 ед. отрезок в минуту в сторону противоположную оси "х", в этом случае алгоритм с "упреждающей стрельбой" опять таки не ловит лодку.

Эта задача (с такой формулировкой условия) не имеет решения!

[nechaman]

Нарисуем табличку ixj, где i и j меняются от минус бесконечности до плюс бесконечности.
i пусть будет сдвиг в первый момент, а j - скорость.
Будем обходить табличку начиная с 1x1, скажем по спирали.
И в каждой точке стрелять в направлении i+j*t, где t-номер шага.
Вроде так мы любую лодку раньше или позже поймаем...

[avva.livejournal.com]

Да, всё правильно.