Классические задачи Computer Science на языке Java

Благодарности

Хочу сказать спасибо издательству Manning и всем, кто помогал в создании этой книги. Особенно хочу поблагодарить редактора Дженни Стаут (Jenny Stout) за ее доброту и поддержку в самые трудные для меня времена; редактора отдела технического развития Фрэнсис Буонтемпо (Frances Buontempo) за внимание к деталям; рецензента Брайана Сойера (Brian Sawyer) за то, что он всегда верил в развитие компьютерных наук и всегда был нашим голосом разума; редактора Энди Кэрролла (Andy Carroll) за обнаружение моих недочетов; Радмилу Эрчеговац (Radmila Ercegovac) за помощь в продвижении книг по всему миру; технического редактора Жан-Франсуа Морена (Jean-Fran 151154.png ois Morin) за поиск способов сделать код более чистым и современным. Выражаю особую благодарность редактору моего проекта Дейрдре Хиам (Deirdre Hiam), корректору Кэти Теннант (Katie Tennant) и научному редактору Алексу Драгосавлевичу (Aleks Dragosavljevi 151156.png ). Я очень благодарен всем специалистам издательства Manning за содействие в подготовке этой книги.

Спасибо Брайану Гетцу (Brian Goetz) за очень занимательное и увлекательное, а главное, полезное для читателей интервью. Для меня было большой честью побеседовать с таким человеком.

Спасибо моей жене Ребекке и маме за неизменную поддержку в этот сложный год.

Благодарю всех рецензентов: Андреса Сакко (Andres Sacco), Эзре Симелоффа (Ezra Simeloff), Яна ван Нимвегена (Jan van Nimwegen), Келума Прабата Сенанаяке (Kelum Prabath Senanayake), Кимберли Уинстон-Джексон (Kimberly Winston-Jackson), Рафаэлле Вентаглио (Raffaella Ventaglio), Раушана Джа (Raushan Jha), Саманту Берк (Samantha Berk), Саймона Чоке (Simon Tsch 151158.png ke), Виктора Дурана (V 151160.png ctor Dur 151162.png n) и Уильяма Уиллера (William Wheeler). Ваши идеи сделали эту книгу лучше. Я ценю внимание каждого и время, затраченное на рецензирование этой книги.

А самое главное, я благодарен читателям, поддержавшим серию книг «Классические задачи Computer Science». Если вам понравилась эта книга, пожалуйста, оставьте свои отзывы. Мы будем рады получить их!

Об авторе

Дэвид Копец — старший преподаватель на кафедре компьютерных наук и инноваций в колледже Шамплейн в Берлингтоне, штат Вермонт. Он опытный разработчик программного обеспечения и автор книг Classic Computer Science Problems in Python¹ (Manning, 2019), Classic Computer Science Problems in Swift (Manning, 2018) и Dart for Absolute Beginners (Apress, 2014). А еще Дэвид ведет подкаст.

1Копец Д. Классические задачи Computer Science на языке Python. — СПб.: Питер, 2020.

Об иллюстрации на обложке

Иллюстрация на обложке называется «Леди с Варварийского берега во всей своей красе»² (второе название: «Парадное одеяние знатной дамы из Берберии, 1700 год»³) и позаимствована из книги «Коллекция платьев разных народов, старинных и современных»⁴, изданной в Лондоне в 1757–1772 годах. Как указано на титульном листе, это гравюры, выполненные на медных пластинах и раскрашенные гуммиарабиком.

Томаса Джеффериса (1719–1771) называли географом короля Георга III. Он был английским картографом, ведущим поставщиком карт своего времени. Он гравировал и печатал карты для правительственных и других государственных учреждений, выпускал множество коммерческих карт и атласов, особенно Северной Америки. В ходе работы интересовался особенностями одежды населения тех земель, которые обследовал и нанес на карту. Зарисовки костюмов блестяще представлены в этом издании. В конце XVIII века увлечение далекими землями и путешествия ради удовольствия были относительно новым явлением, и коллекции, подобные этой, были популярны, позволяя как туристам, так и тем, кто путешествует, не вставая с кресла, познакомиться с жителями других стран.

Разнообразие иллюстраций в книгах Джеффериса — яркое свидетельство уникальности и оригинальности народов мира в то время. С тех пор тенденции в одежде сильно изменились, а региональные и национальные различия, которые были такими значимыми 200 лет назад, постепенно сошли на нет. В наши дни часто сложно отличить друг от друга жителей разных континентов. Оптимисты могут сказать, что взамен культурному и визуальному многообразию мы получили более насыщенную и интересную личную жизнь (или по крайней мере ее интеллектуальную и техническую стороны).

В то время как большинство компьютерных изданий мало чем отличаются друг от друга, компания Manning выбирает для своих книг обложки, показывающие богатое региональное разнообразие, которое Джефферис продемонстрировал в своих иллюстрациях два столетия назад. Это ода находчивости и инициативности современной компьютерной индустрии.

2 Dame de la C 151164.png te de Barbarie dans tout sa parure.

3 Full dress of a lady of quality in Barbary, in 1700.

4 A Collection of the Dresses of Different Nations, Ancient and Modern.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

Введение

Благодарю вас за покупку книги «Классические задачи Computer Science на языке Java». На протяжении двух десятилетий Java был одним из самых популярных языков программирования. Сегодня он доминирует в разработке корпоративных приложений, приложений в сфере высшего образования и мобильных приложений для Android. В этой книге я постараюсь научить вас чему-то большему, чем просто язык программирования. Я надеюсь, что вы начнете думать о Java как об инструменте для решения вычислительных задач. Задачи, описанные в этой книге, среднего уровня. С их помощью опытные программисты смогут освежить свои знания в области информатики, изучив некоторые расширенные возможности языка. Студенты и программисты-самоучки смогут быстрее обучиться программированию, рассматривая общеприменимые методы решения проблем. Эта книга охватывает такое разнообразие методов решения задач, что каждый найдет в ней что-то для себя.

Это издание не является введением в Java. На эту тему есть множество других превосходных книг, выпущенных как в Manning, так и в других издательствах. В книге предполагается, что вы уже программист среднего или высокого уровня на Java. Для примеров использовалась относительно свежая версия Java 11, но вам не нужно знать все тонкости последней версии языка. Фактически примеры были подобраны так, чтобы они послужили учебным материалом, помогающим читателям достичь высокого уровня мастерства. Однако эта книга не подходит для читателей, совершенно не знакомых с Java.

Есть мнение, что компьютеры в информатике — то же самое, что телескопы в астрономии. Если это так, то, возможно, язык программирования подобен объективу телескопа. В любом случае термин «классические задачи программирования» здесь означает «задачи программирования, которые обычно преподают в курсе информатики для студентов».

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

Задачи варьируются от тривиальных, которые решаются написанием нескольких строк кода, до сложных, требующих построения систем на протяжении нескольких глав. Одни относятся к области искусственного интеллекта, другие требуют простого здравого смысла. Некоторые из них практичны, другие — причудливы.

Для кого эта книга

Java используется в самых разных сферах, таких как разработка мобильных приложений, создание корпоративного программного обеспечения, e-commerce и многое другое. Java иногда критикуют за многословность и отсутствие некоторых современных функций. Однако сегодня Java — один из самых популярных языков программирования. Первоначально его создатель, Джеймс Гослинг, задумывал Java как более совершенную версию языка C++. Он стремился создать более мощный объектно-ориентированный язык программирования с функциями безопасности, оптимизируя некоторые из наиболее слабых сторон C++. В этом отношении, на мой взгляд, язык Java добился больших успехов.

Java — мощный объектно-ориентированный язык программирования. Однако многие люди, будь то разработчики Android или создатели корпоративных приложений, в основном пользуются «гибридными API». Вместо того чтобы работать над решением интересных вопросов, они тратят время, изучая каждый нюанс SDK или библиотеки. Цель этой книги — упорядочить ваши знания. А еще существуют разработчики, не имеющие специального образования в области программирования. Если вы один из таких программистов с опытом разработки на языке Java, но не знакомы с CS, эта книга будет очень полезна для вас.

Обычно Java изучают как второй, третий, четвертый или пятый язык, много лет проработав в сфере разработки программного обеспечения. Таким специалистам видение старых проблем, с которыми они сталкивались, работая с другими языками, поможет ускорить изучение Java. Для них эта книга может быть хорошим справочником, который стоит пролистать перед собеседованием при приеме на работу. Также в ней можно найти некоторые способы решения проблем, которые разработчики ранее и не думали использовать в своей работе. В первую очередь я бы посоветовал изучить оглавление, чтобы увидеть, есть ли в этой книге темы, которые вас волнуют.

Эта книга предназначена как для начинающих, так и для опытных программистов. Последние, желая усовершенствовать свои знания в Java, найдут здесь темы для углубленного изучения. Программисты среднего уровня смогут изучить темы на свой выбор. Также эта книга будет ценным справочным материалом для подготовки к собеседованию.

Издание полезно не только для профессиональных программистов, но и для студентов, обучающихся по программам бакалавриата и интересующихся Java. Эту книгу нельзя считать строгим введением в структуры данных и алгоритмы. Это не учебник по структурам данных и алгоритмам. Здесь вы не найдете доказательств или широкого использования нотации «О большого». Книга представляет собой доступное практическое руководство по методам решения проблемных вопросов, которые должны стать конечным продуктом изучения структуры данных, алгоритмов и классов искусственного интеллекта.

В книге описаны синтаксис и семантика Java. Читатель без опыта программирования мало что извлечет из нее, а программист без опыта программирования на Java наверняка столкнется с трудностями. Иначе говоря, это издание, предназначенное для разработчиков с опытом программирования на языке Java и студентов, изучающих компьютерные технологии.

Какие задачи представлены в издании

Глава 1 познакомит вас с методами решения задач, которые, вероятно, известны большинству читателей. Такие действия, как рекурсия, запоминание и манипулирование битами, — важные строительные блоки других методов, которые будут рассмотрены в последующих главах.

За этим плавным вступлением идет глава 2, посвященная задачам поиска. Тема поиска столь обширна, что к ней, вероятно, можно отнести большинство задач этой книги. В главе 2 представлены наиболее важные алгоритмы поиска, включая бинарный поиск, поиск в глубину, поиск в ширину и A*. Алгоритмы поиска будут часто использоваться в остальной части книги.

В главе 3 мы построим структуру для решения широкого круга задач, которые могут быть абстрактно определены переменными ограниченных областей изменения (limited domains). Это такая классика, как задача восьми ферзей, задача о раскрашивании карты Австралии и криптоарифметика SEND + MORE = MONEY.

В главе 4 исследуется мир графовых алгоритмов, применение которых оказывается удивительно широким для непосвященных. В этой главе вы построите графовую структуру данных и с ее помощью решите несколько классических задач оптимизации.

В главе 5 исследуются генетические алгоритмы — менее детерминистская методика, чем большинство описанных в этой книге. Она иногда позволяет решить задачи, с которыми традиционные алгоритмы не способны справиться за разумное время.

Глава 6 посвящена кластеризации методом k-средних и, пожалуй, является самой алгоритмически специфичной главой в этой книге. Данный метод кластеризации прост в реализации, легок для понимания и широко применим.

Глава 7 призвана объяснить, что такое нейронная сеть, и дать читателю представление о том, как выглядит простейшая нейронная сеть. Здесь не ставится цель всесторонне раскрыть эту захватывающую развивающуюся область. В этой главе вы построите нейронную сеть на чисто теоретической основе, не используя внешние библиотеки, чтобы по-настоящему прочувствовать, как работает такая сеть.

Глава 8 посвящена состязательному поиску в идеальных информационных играх для двух игроков. Вы изучите алгоритм поиска, известный как минимакс, который можно применять для разработки искусственного противника, способного хорошо играть в такие игры, как шахматы, шашки и Connect Four.

Глава 9 охватывает интересные и забавные задачи, которые не совсем вписываются в остальные главы этой книги.

Глава 10 представляет собой интервью с Брайаном Гетцем, архитектором языка Java в Oracle. В ней я приведу несколько мудрых советов Брайана.

Об исходном коде

Исходный код в этой книге написан в соответствии с версией 11 языка Java. В нем используются функции, которые стали доступными только в Java 11, поэтому часть кода не будет работать на более ранних версиях Java. Вместо того чтобы пытаться заставить примеры работать в более ранней версии, просто загрузите последнюю версию Java, прежде чем начинать работу с книгой. Я выбрал версию 11, так как это самая последняя LTS (с долгосрочной поддержкой) версия Java, выпущенная на момент написания книги. Код должен работать с более поздними (и будущими) версиями Java. Фактически значительная часть кода будет работать с версиями Java начиная с Java 8. Я знаком с программистами, которые по разным причинам все еще применяют Java 8 (cough Android), но чтобы подчеркнуть ценность изучения новых функций языка, я стану использовать более новую его версию.

В этой книге применяется только стандартная библиотека Java, поэтому весь приведенный в ней код должен работать на любой платформе, где поддерживается Java (macOS, Windows, GNU/Linux и т.п.). Код был протестирован только на OpenJDK (основная реализация Java, доступная на http://openjdk.java.net), хотя, скорее всего, большая его часть будет работать в любой реализации Java.

В книге не объясняется, как использовать инструменты Java, такие как редакторы, IDE и отладчики. Исходный код книги доступен в интернете в репозитории GitHub по адресу https://github.com/davecom/ClassicComputerScienceProblemsInJava. Исходный код разделен на папки по главам. Имена исходных файлов вы увидите в тексте глав в заголовках листингов кода. Эти исходные файлы находятся в соответствующих папках хранилища.

Обратите внимание на то, что репозиторий организован как рабочее пространство Eclipse. Eclipse — это популярная бесплатная программная платформа с открытым исходным кодом Java IDE, существующая для всех основных операционных систем и доступная на eclipse.org. Самый простой способ использовать репозиторий исходного кода — открыть его как рабочее пространство Eclipse после его загрузки. Затем для решения данного вопроса вы можете развернуть каталог src, развернуть архив, представляющий главу, щелкнуть правой кнопкой мыши (или щелкнуть, удерживая клавишу Control на Mac) на файле, содержащем метод main(), и выбрать в раскрывающемся меню пункт RunAs 151226.png JavaApplication (Запуск от имени 151229.png Приложение Java). Я не буду предоставлять учебное пособие по Eclipse, так как, думаю, для большинства программистов среднего уровня это нецелесообразно. Также я предполагаю, что многие программисты предпочтут использовать эту книгу с альтернативными средами Java.

Поскольку мы работаем с классическим языком Java, вы можете запустить любой исходный код из этой книги в выбранной вами среде IDE, будь то NetBeans, IntelliJ или другая удобная для вас. Если вы решите это сделать, обратите внимание на то, что я не смогу предложить поддержку импорта проектов в выбранную вами среду. Большинство IDE можно импортировать из Eclipse.

Если вы только начинаете изучать Java, то самый простой способ настроить свой компьютер с использованием исходного кода из этой книги — сделать следующее.

1. Загрузить и установить релиз Java 11 или более новый с сайта openjdk.java.net.

2. Загрузить и установить Eclipse с сайта eclipse.org.

3. Загрузить исходный код книги из репозитория https://github.com/davecom/ClassicComputerScienceProblemsInJava.

4. Открыть репозиторий целиком в виде рабочей области в Eclipse.

5. Щелкнуть правой кнопкой мыши на файле исходного кода, который нужно запустить, и выбрать команду меню RunAs 151235.png JavaApplication (Запуск от имени 151240.png Приложение Java).

В этой книге нет примеров, которые формировали бы графический вывод или применяли графический пользовательский интерфейс (GUI). Почему? Цель ее состоит в том, чтобы решить поставленные задачи с помощью максимально кратких и удобочитаемых методов. Зачастую вывод графики мешает или делает решения значительно более сложными, чем нужно, чтобы проиллюстрировать рассматриваемые методику или алгоритм.

Кроме того, если не применять какую-либо платформу с графическим интерфейсом, то весь код, представленный в этой книге, становится в высшей степени переносимым. Он может так же легко работать в консольном режиме на дистрибутиве Java, встроенном в Linux, как и на компьютере под управлением Windows. Кроме того, было принято сознательное решение использовать пакеты из стандартной библиотеки Java вместо любых внешних библиотек, как делается в большинстве книг по углубленному изучению Java. Почему? Потому что цель этой книги состоит в том, чтобы научить читателя методам решения задач на основе базовых принципов, а не способом «установить решение». Я надеюсь, что благодаря необходимости решать каждую задачу с нуля вы начнете понимать, что происходит внутри популярных библиотек. Как минимум, работая в этой книге только со стандартной библиотекой, мы получим легче переносимый и более простой в применении код.

Это не означает, что в некоторых случаях графические решения более наглядны для реализации выбранного алгоритма, чем текстовые решения. Просто они не являются темой этой книги и их использование лишь усложнило бы ее.

Дополнительные онлайн-ресурсы

Это третья книга из серии «Классические задачи Computer Science», опубликованная издательством Manning. Первой была Classic Computer Science Problems in Swift, вышедшая в 2018 году, а затем Classic Computer Science Problems in Python, увидевшая свет в 2019-м. В каждой книге этой серии мы стремимся представить видение конкретного языка в свете решения одних и тех же (в основном) задач программирования.

Если вам понравится эта книга и вы решите изучить другой язык, описанный в одной из книг серии, переход от одной к другой может оказаться простым способом улучшить знание этого языка. В настоящее время серия охватывает только Swift, Python и Java. Первые три книги я написал сам, потому что имею значительный опыт работы с обоими языками, но мы уже обсуждаем создание новых книг серии в соавторстве с экспертами в других языках. Если вам понравится эта книга, я призываю вас следить за выходом других изданий серии. Для получения дополнительной информации о них посетите сайт https://classicproblems.com/.

1. Простые задачи

Для начала рассмотрим пару простых задач, которые можно решить с помощью нескольких сравнительно коротких функций. Несмотря на свою простоту, эти задачи все же позволят нам изучить некоторые интересные методы решения. Считайте их хорошей разминкой.

1.1. Ряд Фибоначчи

Ряд Фибоначчи — это такая последовательность чисел, в которой любое число, кроме первого и второго, является суммой двух предыдущих:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Первое число в последовательности Фибоначчи — 0, четвертое — 2. Отсюда следует, что для получения значения любого числа n в последовательности Фибоначчи можно использовать формулу

fib(n) = fib(n — 1) + fib(n — 2)

1.1.1. Первый вариант рекурсии

Приведенная формула для определения числа в последовательности Фибоначчи (рис. 1.1) представляет собой псевдокод, который можно легко перевести в рекурсивный метод Java. (Рекурсивным называется метод, который вызывает сам себя.) Такой механический перевод станет нашей первой попыткой написать метод, возвращающий заданное значение последовательности Фибоначчи (листинг 1.1).

Листинг 1.1. Fib1.java

package chapter1;

public class Fib1 {

    // Этот метод вызывает ошибку java.lang.StackOverflowError

private static int fib1(int n) {

returnfib1(n — 1) + fib1(n — 2);

    }

Рис. 1.1. Рост каждого человечка равен сумме роста двух предыдущих

Попробуем запустить этот метод, вызвав его и передав ему значение (листинг 1.2).

Листинг 1.2. Fib1.java (продолжение)

public static void main(String[] args) {

        // Не запускайте это!

        System.out.println(fib1(5));

    }

}

Ой-ой-ой! При попытке запустить fib1.java получаем ошибку превышения максимальной глубины рекурсии:

Exception in thread main java.lang.StackOverflowError

Проблема в том, что функция fib1() будет работать вечно, не возвращая окончательный результат. Каждый вызов fib1() приводит к двум другим вызовам fib1(), и так без конца. Такую ситуацию называют бесконечной рекурсией (рис. 1.2), она подобна бесконечному циклу.

Рис. 1.2. Рекурсивная функция fib(n) вызывает сама себя с аргументами n – 1 и n – 2

1.1.2. Использование базовых случаев

Обратите внимание: до тех пор, пока мы не запустили fib1(), среда Java никак не сообщает о том, что с функцией что-то не так. Избегать бесконечной рекурсии — обязанность программиста, а не компилятора или интерпретатора. Причина бесконечной рекурсии заключается в том, что мы нигде не указали базовый случай. В рекурсивной функции базовый случай служит точкой остановки.

Естественные базовые случаи для последовательности Фибоначчи — это два первых специальных значения последовательности — 0 и 1. Ни 0, ни 1 не являются суммой двух предыдущих чисел последовательности. Это два первых специальных значения. Давайте попробуем указать их в качестве базовых случаев (листинг 1.3).

ПРИМЕЧАНИЕ

В отличие от первоначального предложения версия fib2() метода Фибоначчи возвращает 0 для аргумента, равного нулю (fib2(0)), а не единице. В контексте программирования это имеет смысл, поскольку мы привыкли к последовательностям, начинающимся с нулевого элемента.

Листинг 1.3. Fib2.java

package chapter1;

public class Fib2 {

private static int fib2(int n) {

if (n < 2) { return n; }

returnfib2(n - 1) + fib2(n - 2);

    }

Метод fib2() может быть успешно вызван и возвращает правильные результаты. Попробуйте вызвать его для нескольких небольших значений (листинг 1.4).

Листинг 1.4. Fib2.java (продолжение)

public static void main(String[] args) {

        System.out.println(fib2(5));

        System.out.println(fib2(10));

    }

}

Не пытайтесь вызывать метод fib2(40). Он будет выполняться очень долго! Почему? Потому что каждый вызов fib2() приводит к двум новым вызовам fib2() — рекурсивным вызовам fib2(n-1) и fib2(n-2) (рис. 1.3). Другими словами, дерево вызовов растет в геометрической прогрессии. Например, вызов fib2(4) приводит к такой последовательности вызовов:

fib2(4) -> fib2(3), fib2(2)

fib2(3) -> fib2(2), fib2(1)

fib2(2) -> fib2(1), fib2(0)

fib2(2) -> fib2(1), fib2(0)

fib2(1) -> 1

fib2(1) -> 1

fib2(1) -> 1

fib2(0) -> 0

fib2(0) -> 0