Нужен ли код в книге Занимательных Задач по программированию?24.03.2025 08:31

Мы с детства знакомы с книжками «Занимательных Задач» — чаще всего, наверное, по математике и быть может физике -, но существуют они и во многих других отраслях знаний, вплоть до географии и биологии.

А как же наш любимый программизьм? :) Мне известно не так много примеров. Зачем вообще программисту задачи? Для начинающего актуально, конечно, на них «нарабатывать практику» (или когда уже не новичок, но осваивает новый для себя язык программирования) -, но не только это. Задачки кроме того дают идеи. Программисты же народ творческий и хотя бы подсознательно постоянно в поиске идей.

Когда на сайте у меня количество задач перевалило за 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)

На этот раз мы ещё не собираемся писать компьютерного «оппонента» для известной игры, но сделаем важный шаг на пути к этому — научимся определять, завершается ли игра очередным ходом, или нет. Как вы вероятно знаете, игра происходит на поле 3×3 клетки. Предположим что они пронумерованы следующим образом:

    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

Головоломки

В этом разделе собрано больше 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

Заключение

Книжка вероятно будет в какой-то момент скомпилирована и выложена на исходном, английском языке. Судьба же русскоязычного перевода зависит в большой степени от вашего отклика — так что не стесняйтесь и участвуйте, пожалуйста, в голосовании — и оставляйте комментарии по необходимости!