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

[avva]

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

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

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

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

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

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

Comments

[avva.livejournal.com]

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

[malenkiy-scot.livejournal.com]

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

[malenkiy-scot.livejournal.com]

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

[avva.livejournal.com]

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

[malenkiy-scot.livejournal.com]

По 3-й оси - сколько гонять алгоритм.

[avva.livejournal.com]

Да, а вот это уже - почти готовое решение, только несколько подробностей обсосать.

[malenkiy-scot.livejournal.com]

На работу берут? А то мне шибко надоело на своем старом месте :)

[malenkiy-scot.livejournal.com]

Нет, рано я радовался: что если алгоритм, которому следует лодка, медленнее, чем, рост времени, которое мы ему выделяем каждый раз? Это не просто деталь.

Re:

[avva.livejournal.com]

Не, это неважно. "Время", которое мы ему уделяем - один шаг машины Тюринга, которая выполняет данный алгоритм. Кол-во шагов откладывается на третьей оси.

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

[malenkiy-scot.livejournal.com]

Я не совсем понял. Перефразирую вопрос.

Конечно, время - это количество шагов. Я это и имел ввиду с самого начала. Вопрос вот какой: мы готовимся к выстрелу в момент n. Мы запускаем конечное число алгоритмов, которые может использовать лодка. Максимальное число шагов выделенное алгоритмам - m. Но что, если алгоритм, который использует лодка тратит для расчета положения в минуту n больше, чем m шагов? И ТАК ДЛЯ КАЖДОГО n, т.к. максимальное число шагов перед выстрелом n должна быть ограничено какой-то определенной функцией, как поручится, что алгоритм лодки будет использовать нe большее количество шагов, по крайней мере, начиная с какого-то n?

Re:

[avva.livejournal.com]

Но что, если алгоритм, который использует лодка тратит для расчета положения в минуту n больше, чем m шагов?

Да, правда Ваша. Действительно есть проблема; надо подумать.

[pingva.livejournal.com]

С произвольным алгоритмом-то Вы пожалуй погорячились :)

Не переформулируете ли еще раз, когда и как разрешим подлодке курс менять?

[snyders.livejournal.com]

Я попытался сделать это внизу. Не знаю, насколько успешно.

[pingva.livejournal.com]

ага, спасибо.

Только ниче путного мне в голову не приходит :)

[malenkiy-scot.livejournal.com]

Вот, похоже, доказательство того, что это невозможно (спасибо сослуживцу):

Предположим, мы нашли такой алгоритм (функцию) n = f(t) (в момент t мы треляем в точку n). Если лодка движется по функции f(t)+1, мы ее никогда не поразим.

[snyders.livejournal.com]

Честно говоря, не совсем понятно:

предполагается, что вычисления и на лодке и на стрелке происходят мгновенно? и можно мгновенно проверить M алгоритмов на глубину N шагов?

По моему нет четкой формулировки того, что мы хотим доказать, когда разрешаем лодке некий
алгоритм движения.

Вариант 1 -- лодка может менять направление движения конечное число раз, т.е. выбирается К произвольных чисел (моментов времени) T1 < T2 <.. < TK, в которые лодка меняет направление движения на противоположное. Как лодка получает эти Т нас не интересует.
(задача подразумевает, что вычислительные способности стрелка -- неограничены, ведь ему приходится выполнять действия над неограниченно большими числами за ограниченое время, за одну минуту; либо надо предположить, что стрелок может делать операции типа N+1 за фиксированое время).

Решабельно.


Вариант 2 -- у лодки есть алгоритм движения, задаваемый конечным автоматом с ограниченым числом шагов в минуту. Пусть, для простоты, алгоритм влияет только на направление, но не на скорость движения.

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

Вопрос: можно ли как-то усилить вычислительные способности лодки, или уменьшить их у стрелка, так, чтобы по-прежнему стрелок мог попасть в лодку?

[malenkiy-scot.livejournal.com]

Давайте формализируем условие, и тогда все станет понятней:

Дано: некое множество F рекурсивных функций N->Z (т.е. функций из натуральных в целые числа, алгоритмически вычисляемых для любого n в N). Вопрос: существует ли рекурсивная функция
f1:N->Z такая, что для любой функции f в F существует n такое, что f1(n)=f(n) ?

В изначальной задаче, F - это множество всех "линейных" функций. В общей - множество всех рекурсивных функций N->Z.

A теперь можно начинать играть с разными ограничениями на F. Например, если F рекурсивно (т.е. есть алгоритм, который позволяет определить, принадлежит ли данная функция F или нет), то такая функция f1 существует, и т.д.

[snyders.livejournal.com]

Да, приплыли :)

а обсужение интересное, если будет время, тоже попробую подключится.