?

Log in

No account? Create an account
задачки и головоломки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачки и головоломки [авг. 3, 2002|11:05 am]
Anatoly Vorobey
Интересный ресурс: хранилище задач и головоломок, используемых во время интервьюирования программистов. Много знакомых и хорошо известных, но много и незнакомых. Большинство простые, но есть сложные и интересные.

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

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


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

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

Comments:
From: ex_olg
2002-08-03 01:16 am

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

интересно, а на русском есть подобные ресурсы? не встречали?
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 01:23 am

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

С добрым утром и Вас ;) нет, не встречал.
(Ответить) (Parent) (Thread)
From: ex_olg
2002-08-03 10:45 pm

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

ну, ладно. пожалуй, тогда вывешу в ЖЖ свою любимую загадку.
(Ответить) (Parent) (Thread)
[User Picture]From: lz
2002-08-03 03:25 am

Анатолий

Мне кажется, Вам будет интересна эта головоломка:
http://vad.spb.ru/www/xlam/WebLomka.htm
Спецально для интернет-профессионалов, да простится мне это новообразование.
На мой взгляд - есть очень красивые уровни
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 07:57 pm

Re: Анатолий

Спасибо ;) Честно говоря, лень немножко её проходить, да и похожую англоязычную я уже проходил когда-то. Но сам тип головоломки интересен, согласен.
(Ответить) (Parent) (Thread)
[User Picture]From: zc2
2002-08-04 09:40 am

Re: Анатолий

занятная штука... кто-нибудь прошел 9-й уровень? Я на нем заткнулся... :-(
(Ответить) (Parent) (Thread)
[User Picture]From: nechaman
2002-09-03 01:47 pm

Re: Анатолий

А я вот на седьмом застряла.
Перепробовола кучу вариантов. Вроде один файл явно другой, и больше, и вообще, пробовала картинки накладывать, выделять разные оттенки, но ничего не вышло, явно не в том направлении мыслю...
Может подскажете?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2002-08-03 11:54 am
Извините, вы не могли бы опубликовать решение задачи о дискретно движущихся подводных лодках, очень интересно было бы узнать ответ.
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 12:25 pm

Re:

Могу, конечно, но давайте я хотя бы день ещё подожду, дам возможность людям самим решить.
(Ответить) (Parent) (Thread)
[User Picture]From: pingva
2002-08-03 02:46 pm
подлодка движется по формуле:

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)

Черт, не успею додумать :), надо убегать.
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 07:01 pm
Значит, будем стрелять по ((-1)^n)*2*(n^3)

Вот этот шаг неверный, не поймаете так ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vrml
2002-08-03 04:20 pm
Значит, дано, что мы не знаем ни скорости лодки, ни положения. Следовательно, вероятность поражения лодки одним выстрелом - нулевая (согласно определению вероятности - т.к. число точек бесконечно), независимо от выбора точки. Допустим, мы пальнули в некую точку. Ничего нового про местоположение и скорость лодки мы при этом не узнали. Что изменится на втором выстреле? - тоже ничего. По индукции, во время любого n-го выстрела мы остаемся "при своих" - как и во время первого. Лодка где-то себе плавает, по-прежнему с неизвестной скоростью и неизвестно где. То есть все алгоритмы выстрелов, включая случайную последовательность, равноправны в том, что никакой гарантии поражения не дают.
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 04:24 pm

Re:

Выглядит убедительно, но верным не является ;)
Не буду пока указывать на ошибку в этом рассуждении, но замечу, что решение у задачи есть.
(Ответить) (Parent) (Thread)
[User Picture]From: ska_o
2002-08-03 08:31 pm
Не нулевая, а бесконечно малая. Две большие разницы :-)
(Ответить) (Parent) (Thread)
[User Picture]From: vrml
2002-08-04 03:55 am
Нет уж - лбо нулевая, либо ненулевая :)
Бесконечно малыми бывают не числа, а относительные величины.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: snyders
2002-08-03 04:58 pm
Показать что множество точек с координатами (x,y), x in N -- начальное положение, y in Z -- скорость равномощно N.

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

Кажется, лодке еще можно разрешить менять направление движения конечное число раз.
(Ответить) (Thread)
[User Picture]From: avva
2002-08-03 05:43 pm

Re:

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

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

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

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

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

Боюсь, правда, что твой и мой комменты многим остануться непонятными, так что надо будет отдельную запись написать и там разъяснить решение подробнее.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: barabek
2002-08-04 09:14 am

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

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

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

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

(Ответить) (Thread)
[User Picture]From: avva
2002-08-04 09:38 am

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

Это только при условии, что она вышла из точки 0 и движется вправо. Ни то, ни другое неверно (она может начать с любой точки и двигаться влево).
(Ответить) (Parent) (Thread)
[User Picture]From: gvadelupa
2002-08-05 03:11 am

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

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

Avva, вы обещали выложить решение, не пора?
(Ответить) (Parent) (Thread) (Развернуть)
From: cybergoblin
2002-08-09 02:30 pm
Решение в корне неверное:

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

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

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

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

Эта задача (с такой формулировкой условия) не имеет решения!
(Ответить) (Thread)
[User Picture]From: nechaman
2002-09-03 03:19 pm
Нарисуем табличку ixj, где i и j меняются от минус бесконечности до плюс бесконечности.
i пусть будет сдвиг в первый момент, а j - скорость.
Будем обходить табличку начиная с 1x1, скажем по спирали.
И в каждой точке стрелять в направлении i+j*t, где t-номер шага.
Вроде так мы любую лодку раньше или позже поймаем...

(Ответить) (Thread)
[User Picture]From: avva
2002-09-03 03:51 pm

Да, всё правильно.
(Ответить) (Parent) (Thread)
[User Picture]From: nechaman
2002-09-03 10:59 pm
Да, кстати, забыла добавить.
Если движение лодки определяется конечным числом параметров, допустим n (например разрешить ей двигаться по плоскости или в пространстве, а не по прямой), то естественно можно то же самое сделать, только построить надо будет n-мерную таблицу.
А то, что лодка сможет упредить наш выстрел, это по-моему не верно, потому что предполагается в задаче, что стрелку известен общий алгоритм движеня лодки, за исключением значения параметров, а вот лодке не известно, какого алгоритма придерживается стрелок, и во всяком случае, она не сможет его менять в соответствии со стратегией принятой стрелком.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2006-01-17 10:57 pm

ja dibil

eeeeeeeee...kak re6itj pervij urovenj?:D:D:D:D
(Ответить) (Parent) (Thread)