Мы с детства знакомы с книжками "Занимательных Задач" - чаще всего, наверное, по математике и быть может физике - но существуют они и во многих других отраслях знаний, вплоть до географии и биологии.
А как же наш любимый программизьм? :) Мне известно не так много примеров. Зачем вообще программисту задачи? Для начинающего актуально, конечно, на них "нарабатывать практику" (или когда уже не новичок но осваивает новый для себя язык программирования) - но не только это. Задачки кроме того дают идеи. Программисты же народ творческий и хотя бы подсознательно постоянно в поиске идей.
Когда на сайте у меня количество задач перевалило за 400, пришло на ум что можно их собрать под одной обложкой - для любителей поразмышлять в отрыве от компьютера. Идея эта однако встала на паузу - но недавно мне о ней напомнили. Коллега с Хабра предположил возможность издания подобной книжки на русском языке.
Один из вопросов по которому мы не нашли пока консенсуса - размещение в подобной книжке "решений". Поэтому обращаюсь за помощью к общественности, к коллегам-айтишникам в первую очередь - ниже будет немного подробностей и примеров задач, по разделам - и опрос, насчет того в каком виде нужны (или не нужны) эти самые решения.
Общие замечания
Сайт и задачи о которых речь НЕ относятся в большинстве своём к "олимпиадному" или "спортивному" программированию. Наоборот они в большинстве своём достаточно простые, нацеленные больше "на широту, чем на глубину" - чтобы дать практику, м.б. развлечение - и по возможности познакомить с какими-то не очень известными вещами из нашей отрасли.
Они условно разделены на такие разделы:
Простые задачи - то что подходит для новичков, школьников - или когда только-только знакомишься с новым языком.
Задачи на реализацию - тоже несложные, но более объёмистые, чтобы можно было минимально хотя бы задуматься над композицией и декомпозицией кода и т.п.
Популярные алгоритмы - здесь большинство задач иллюстрируют и объясняют вещи начиная с любимых (ненавистных) сортировок и графов - и заканчивая ранжированием веб-страниц, криптографией и т.п.
Головоломки - тут собрались задачи в которых решение быть может неочевидно или очевидное решение оказывается ошибочным, а может неэффективным. Иногда нужно вспомнить подходящий алгоритм - но часто просто додуматься с какой стороны подойти. Здесь немало задач присланных пользователями.
Специальные - сюда попали задачи на Брейнфак и SQL, на машину Тьюринга и Ассемблер для intel-4004, игры с сервером по HTTP и всякое такое.
Почему решения в виде кода кажутся нежелательными:
сейчас много популярных языков - и книжка с примерами на Python или C++ вызовет легкое разочарование у тех кто использует Go или Java например
решения задач кроме простейших могут быть довольно объёмны - и раздувать книжку за счет листингов программ - выглядит нехорошо по отношению к читателю
не всем нам нравятся объяснения решений в виде кода - программисты не так уж любят вчитываться чужой код (хотя и приходится заниматься этим постоянно)
Отдельный вопрос - так называемый "псевдокод". Отношение к нему тоже неоднозначное, хотя в редких случаях быть может можно использовать его для пояснения мысли.
Итак, посмотрим на сами примеры - каким из них "решения" вообще актуальны.
Раздел "Простые Задачи"
Как упоминалось, эти задачи хороши для тех кто делает первые шаги в программировании. Читатель уже имеющий опыт может их пропустить или "просмотреть по диагонали". Решения для этого раздела в большинстве случаев отдельно писать не планируется - полезные указания и подсказки проще дать вместе с условием задачи.
СУММА "А+B" (#1)
Подобная "задача" это что-то вроде традиции, не будем нарушать её и мы. Она позволит проверить что мы хотя бы понимаем как собрать и запустить программу, как ввести числа с консоли (а не вбивать, "хардкодить" их прямо в тексте).
Пример:
входные данные:
355 113
ответ:
468
СУММЫ В ЦИКЛЕ (#3)
Теперь у нас несколько пар чисел - и мы хотим вывести сумму каждой пары. Нужно просто "обернуть" предыдущую программу в цикл. В первой строке указано количество пар, а сами они идут дальше, по паре на строку.
Пример:
входные данные:
3
100 8
15 245
1945 54
ответ:
108 260 1999
СУММА В ЦИКЛЕ (#2)
Небольшая модификация предыдущей задачи - теперь мы хотим найти общую сумму всех чисел поданных на вход. По хорошему нужно завести дополнительную переменную для накопления результата. В то же время, даже если вы уже знаете что такое массив, имейте в виду что он здесь не нужен (хотя в языке вроде Python трудновато от него избавиться). В первой строке указано количество чисел для суммирования, во второй сами числа.
Пример:
входные данные:
8
10 20 30 40 5 6 7 8
ответ:
126
ОКРУГЛЕНИЕ (#6)
В некоторых задачах нам нужно будет округлять ответ до целого. Оказывается, существует несколько способов сделать это - и нам нужно выбрать какой-то один, чтобы не запутаться. Будем использовать тот, которому учат в школе:
- если дробная часть абсолютной величины числа меньше 0.5, то округляем "в сторону нуля" (фактически, отбрасывая дробную часть)
- в противном случае округляем "от нуля" - к ближайшему целому бОльшему по модулю.
Заметим что в некоторых языках (в частности, в Python) встроенная функция округления работает немного иначе (так называемое "банковское" округление), поэтому возможно удобнее окажется встроенную функцию не использовать.
В первой строке указано количество пар чисел следующих далее. Для каждой пары нужно вывести результат деления первого числа на второе, со вышеописанным округлением.
Пример:
входные данные:
3
12 8
11 -3
400 5
ответ:
2 -4 80
РЕШЕТКА ИЗ ШЕСТИУГОЛЬНИКОВ (#73)
Во многих играх вроде пошаговых стратегий заметно что персонажи двигаются по "гексагональной" решетке (например в режиме битвы в классических Heroes of Might and Magic) - она улучшает "изотропность" игрового поля - и вообще красивее выглядит - но немного сложнее для программирования. В этой задаче мы попрактикуемся с ней!
Представьте что персонаж стоит в ячейке обозначенной X. Ему доступны шаги в 6 направлениях. Направление A означает шаг непосредственно вправо, а остальные (B, C, D, E, F) - против часовой стрелки от него. Вам будет задана последовательность ходов, обозначенных соответствующими буквами - и требуется в качестве ответа указать расстояние между начальной и конечной точкой (по прямой, то есть в "Евклидовом" смысле), считая расстояние между центрами соседних ячеек (то есть величину шага) за единицу.
Входные данные содержат количество "тесткейсов" в первой строке. Остальные строки содержат сами "тесткейсы" - каждый в виде строчки ходов, для которой нужно посчитать указанное расстоние по прямой. Ответ достаточно представить с точностью до 1e-7.
Пример:
входные данные:
3
AABF
FEDCBA
BCB
ответ:
3.0 0.0 2.64575131
Задачи на реализацию
Как упоминалось, здесь задачи тоже несложны, но более объёмны - поэтому и условия могут содержать довольно длинные объяснения. Конечно, если вы знаете, например, правила описываемой игры, при первом прочтении необязательно скрупулёзно их перечитывать.
КРЕСТИКИ-НОЛИКИ (#46)
На этот раз мы ещё не собираемся писать компьютерного “оппонента” для известной игры, но сделаем важный шаг на пути к этому – научимся определять, завершается ли игра очередным ходом, или нет. Как вы вероятно знаете, игра происходит на поле 3x3 клетки. Предположим что они пронумерованы следующим образом:
1 | 2 | 3
---+---+---
4 | 5 | 6
---+---+---
7 | 8 | 9Игроки по очереди ставят свои отметки (крестики “X” или нолики “О”) в ещё не занятые клетки. Тот кто очередным ходом “достраивает” линию из трёх своих отметок (по горизонтали, вертикали или диагонали – всего 8 возможных линий) – тот и выиграл. Например если игроки ходят по очереди в клетки с такими номерами:
7 (x), 5 (o), 4 (x), 1 (o), 9 (x), 2 (o), 8 (x)
То на поле получится такая позиция:
O | O |
---+---+---
X | O |
---+---+---
X | X | XОчевидно, первый игрок (крестики) выиграл последним ходом (в клетку 8).
Входные данные содержат несколько строк, описывающих несколько игр, в виде последовательностей ходов. Общее число игр (N) указано в самой первой строке. Ответ должен содержать N чисел, указывающих, на каком ходу была выиграна каждая из игр (0 означает что игра закончилась вничью).
Пример:
входные данные:
3
7 5 4 1 9 2 8 3 6
5 1 3 7 6 4 2 9 8
5 1 2 8 6 4 7 3 9
ответ:
7 6 0
ФРОДО И ЧЁРНЫЕ ВСАДНИКИ (#182)
Идея этой задачи возникла из предложения пользователя Laurent Petit на форуме.
В первой части книги “Властелин Колец” есть леденящая кровь сцена когда хоббит Фродо со своими спутниками прячутся от Чёрных Всадников из Мордора, которые догнали их по дороге из Хоббитона в Брыль.
Представим себе, что всё это происходит на квадратном пространстве, размером 100 на 100 ярдов. В нём присутствуют несколько Чёрных Всадников, пытающихся отыскать несчастных хоббитов. Каждый из Чёрных Всадников имеет ограниченное поле зрения – такую, как показано на картинке.
Предположим, Всадник стоит в точке (0, 0) и смотрит вдоль оси X. Конечно дальше всего он видит по направлению “вперед” – однако он может ограниченно чувствовать и присутствие теплокровных существ позади. В общем, граница где хоббит будет обнаружен, определяется простым уравнением в полярных координатах:
R = 20 + 15 * cos(theta)
Здесь theta – угол между направлением на заданную точку (в частности, хоббита) – и направлением взгляда Всадника. Например, если Всадник смотрит вдоль оси Y, а хоббит прячется в точке (30,30) – тогда он в безопасности (theta = pi/4), но если он ближе, в точке (10,10), то Всадник легко обнаружит беднягу...
Ваша задача – приблизительно оценить процент “безопасной территории” в квадрате, при заданном размещении всадников.
Входные данные содержат количество Всадников в первой строке (N=4..6) – а следующие строки содержат тройки чисел – координаты и угол в радианах (направление в котором ориентирован всадник).
Ответ должен содержать N+1 чисел. Сперва – процент площади которую не просматривает ни один Всадник. Далее процент площади которую контролирует только один Всадник, затем площадь под контролем какой либо пары Всадников и так далее. Значения округлить до целых чисел.
Пример:
входные данные:
4
20 81 0.6
39 35 0.5
90 16 -1.5
85 20 -1
ответ:
63 31 7 0 0
ИГРА "ЗМЕЙКА" (#96)
Эта игра, также называемая “червяк”, известна ещё с 1970-х годов: змейка ползает по прямоугольному полю, собирая “еду” и стараясь избежать столкновений с границами поля или с самой собой.
В этой задаче нужно написать программу эмулирующую такую игру. На поле “разбросаны” фрукты, и задана последовательность движений “змеи”. Требуется выполнить эти движения и определить, на каком ходу змея “врежется” в себя.
Начальное состояние поля подаётся на вход программы в виде прямоугольника 21 на 13 ячеек, например:
X X X - - - - - $ - - - - - $ - - $ $ - -
$ - - - - - - - - $ - - $ $ - - $ - $ - -
$ - - $ - $ $ - - - - - - - $ - - - - - -
- $ - - $ - - $ - - - - - $ $ $ $ $ - $ $
$ - - - $ $ - - - - - - - - - - - $ - - -
- $ $ - - - - - - - - - - - - $ - - - - $
$ - - - - - - - - $ - - - - - $ $ - - - -
$ - - - $ - - $ $ - - - $ - $ $ - - - - -
- - - - $ $ - - - - - - $ $ - - - - - - $
- $ - - - $ - - - - - - - $ - - - - $ - $
- - - - - $ - $ - - - - - $ $ - - - - - -
- - - - - $ - - $ - - $ - - - - - - - - $
- - $ - - $ - - - - - - $ - - - $ - - $ -Змея изначально всегда находится в левом верхнем углу и имеет длину 3 и направлена вправо. Последовательность движений подаётся на вход в таком виде:
12 D 4 L 10 U 1 R 6 D 7 R 9 U 9 L 16
Это следует читать так: сделать 12 шагов, сменить направление (D – вниз), сделать ещё 4 шага, сменить направление (L – влево), сделать ещё 10 шагов, сменить направление (U – вверх), сделать 1 шаг, сменить направление (R – вправо) и так далее. Заметим, что смена направления не считается отдельным ходом.
Каждый ход заключается в том что “голова” змеи сдвигается на 1 клетку в текущем направлении (лучше сказать “наращивается”). В то же время “хвост” укорачивается на 1
клетку. Если при данном ходе “голова” попала на место где лежал фрукт (они обозначены символом $), то фрукт считается съеденным, а длина змеи увеличивается на единицу (клетка в хвосте не стирается на этом ходу).
Ответ должен содержать координаты клетки где произошло столкновение и номер хода, на котором оно случилось. Координата верхнего левого угла (0, 0).
Пример:
входные данные:
X X X - $ - - $ $ - $ $ $ - - - - - - - $- - - $ - - - - - - - $ - - - - - $ $ $ -$ $ $ - - - - - $ - - - - $ $ - - - - $ $- $ - - - - - - $ $ - - - $ - - $ - - - -- $ $ - - - - $ - - - $ - - - - - - - - -$ - - $ - - $ - - $ - $ - - - - - - - - -- - - - - $ - - - - - - $ - - - - $ - - $- - - - - $ $ - $ - - $ - - - - $ $ - - -- $ - - - - - $ - $ - $ - - - - - - $ - -- $ $ - $ - - - - - - - $ - - - $ - $ - $- - - - - - - - - - - - - - $ $ $ - - - -- - - $ - - - - - - - - - $ - - - $ - - $- - - - - - - - - $ - - - - - - $ $ $ - -5 D 1 L 1 U 1 L 3
ответ:
6 0 8
Популярные Алгоритмы
ПЬЕР ФЕРМА ВЗЛАМЫВАЕТ ШИФР RSA (#153)
Если после решения задачи на реализацию ассиметричного шифрования RSA (#152) у вас осталось не очень чёткое представление о надёжности этого алгоритма, давайте рассмотрим следующу возможную "атаку" на него.
Вновь нужно расшифровать сообщение, но теперь мы не знаем p и q, а только их произведение n - именно в такой ситуации находится потенциальный взломщик. Шифрование всё равно можно осуществить используя e=65537 но к сожалению мы не знаем показатель степени d необходимый для расшифровки!
Мы заподозрили что человек, выбиравший ключи, был новичок в своём деле, и для удобства взял достаточно близкие значения p и q так что, вероятно, можно их найти попытавшись разбить n на множители.
Ферма не зря упомянут в названии задачи - скорее всего его алгоритм факторизации чисел понадобится вам как вспомогательная часть в решении данной проблемы. Его вы легко найдёте в интернете.
Преобразование чисел в данные осуществляется тем же способом как и в предыдущем упражнении. Входные данные содержат n в первой строке, во второй будет шифр, сгенерированный как a ^ 65537 % n, где a есть исходное сообщение, преобразованное в длинное целое. Ответ должен содержать расшифрованное сообщение.
Пример:
входные данные (длинное число разбито на несколько строк):
input data:
2005386240811006492510206908835874977464399827995998174235015291258
133373258958037573585627258926557618335589879504876460462075566
410747651590614428022205934562315249635550863811428
ответ:
EGG EAT SKI SHY ARM EON HIP FUN LOW
Головоломки
В этом разделе собрано больше 100 задач - все они требуют сначала немного подумать. Некоторые задачи могут быть решены неэффективным путём (полный перебор и пр) - что мы абсолютно не запрещаем вам попробовать (даже если ваш код будет работать несколько часов - невольно начинаешь уважать компьютер!) - но при этом всегда приветствуется если вы вернётесь к такой "неэффективно решённой" задаче в будущем, и сообразите как сделать лучше. Иногда для этого требуется какой-нибудь полезный алгоритм - но чаще просто смекалка.
Решения задач этого раздела вероятно не будут приведены просто чтобы не портить Вам удовольствие. Вы все их сможете решить со временем или найти решение в интернете.
ПАCХАЛЬНЫЕ КРОЛИКИ (#259)
Эту задачу предложил пользователь Mathias Kern
Вы познакомились с семейством Пасхальных Кроликов - все они забавные одномерные создания - и занимаются тем что особым образом размещают Пасхальные Яйца в одномерном массиве с ячейками, пронумерованными индексами 1, 2, 3, ...
Каждый из Кроликов характеризуется собственной длинной прыжка и оставляет в каждой посещённой ячейке массива яйцо, если его там не было. В противном случае он наоборот ворует яйцо из ячейки. Вот жадина!
У первого Крлика длина прыжка равна 2, и он оставляет яйца в ячейках 2, 4, 6, 8, 10, 12...
Второй кролик с длинной прыжка 3 оставляет яйцо в ячейке 3, ворует яйцо из ячейки 6, оставляет яйцо в ячейке 9, ворует из ячейки 12 и так далее.
Третий кролик, прыгая в каждую 4 ячейку, ворует из ячеек 4 и 8, оставляет яйцо в ячейке 12 и так далее.
Задача в том, чтобы для массива размера N определить сколько яиц в нём останется после того как по нему проскачут все кролики с длиннами прыжков от 2 до N. Значение N не более нескольких миллиардов.
Входные данные содержат несколько чисел N - разные размеры массивов для которых нужно решить задачу (просто разбейте строчку по пробелам). Ответ должен содержать столько же чисел - количество яиц оставшихся в каждом из массивов после посещения кроликами.
Пример:
входные данные:
3 8 15 97
ответ:
2 6 12 88
Специальные задачи
В этом разделе собраны задачи которые нужно решить на указанном языке (например, упражнения по SQL или головоломки на Brainfuck), игры в которых нужно написать код "сражающийся" против сервера и т.п.
САМОПЕЧАТАЮЩАЯСЯ ПРОГРАММА (#286)
Это старинное и классическое упражнение, в принципе такой трюк можно проделать на любом языке, но конечно нас не устраивают решения вроде открытия исходного файла и вывода его на экран. Если будете сдавать эту задачу на сайте, используйте встроенный интерпретатор языка BASIC - решения проверяются только на нем.
ПОСЛЕДОВАТЕЛЬНОСТЬ КВАДРАТОВ НА БФ (#126)
Упражнение на языке Brainfuck - напишите программу, которая получает на вход число X - и печатает квадраты чисел от 1 до X.
В этой задаче можно использовать дополнительные "фичи" версии BF используемой на сайте:: - эта команда печатает число из текущей ячейки на стандартный вывод; - эта наоборот считывает число в текущую ячейку со стандартного ввода# - копирует число из текущей ячейки на верхушку встроенного стека$ - выталкивает число из стека в текущую ячейку
Задачу можно решить и без этих дополнительных команд - но возможно в ходе решения предыдущих Вам уже надоело реализовывать вспомогательный функционал вроде операций ввода-вывода - и они просто сэкономят Ваше время.
Пример:
входные данные:
5
ответ:
1 4 9 16 25
ВЕБ-СКРЕЙПЕР ДЛЯ СОЦСЕТИ (#160)
За идею этой задачи благодарю мою коллегу Жанну Хаймеддинову
В современном интернете очень много информации. И неудивительно что информация предназначенная для людей часто извлекается и обрабатывается также и роботами.
В этой задаче вам нужно написать маленькую программу, которая собирает данные в социальной сети. Это не настощая соцсеть, поэтому Вам ничего не грозит :)
Начните со страницы пользователя по имени John Doe:
http://codeabbey.github.io/social-network/
Вы увидите что на каждой странице есть данные о дате рождения человека и его состоянии. Также видно, что можно перейти на страницы связанных с ним людей по ссылками. Например от John Doe можно перейти к Dan Wagner (через "Друзей") а отсюда к Dave Johnson (через "сообщения на стене").
Задача заключается в том чтобы посчитат суммарное состояние (в долларах) всех людей с заданной фамилией (например, Johnson), которых можно "достать" с исходной через любое количество ссылок.
Общий путь решения может быть таким:
напишите функцию скачивающую страницу по ссылке
напишите функцию извлекающую другие ссылки из скачанной страницы
также напишите код для извлечения фамилии и данных о состоянии
теперь сделайте цикл который обходит "социальный граф" (ориентируйтесь на подходящие задачи из раздела по алгоритмам)
останется только сложить значения для людей с заданной фамилией
Пример:
входные данные:
doe
ответ:
130000
Заключение
Книжка вероятно будет в какой-то момент скомпилирована и выложена на исходном, английском языке. Судьба же русскоязычного перевода зависит в большой степени от вашего отклика - так что не стесняйтесь и участвуйте, пожалуйста, в голосовании - и оставляйте комментарии по необходимости!
