Глава 13.

08.09.2021

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

  1. В этой главе мы определим класс Card и напишем методы, которые работают с картами и массивами карт.
  2. В главе 14 мы создадим класс Deck и напишем методы, которые работают с Deck s.
  3. В главе 15 я представлю объектно-ориентированное программирование (ООП), и мы преобразуем классы Card и Deck в более стиль ООП.

Я думаю, что такой способ движения делает дорогу более гладкой; недостаток в том, что мы увидим несколько версий одного и того же кода, что может сбивать с толку. Если это поможет, вы можете загружать код для каждой главы по мере продвижения. Код этой главы находится здесь: http://thinkapjava.com/code/Card1.java.

13.2 Объекты карты

Если вы не знакомы с обычными игральными картами, сейчас самое время получить колоду, иначе эта глава может не иметь особого смысла. Или прочтите http://en.wikipedia.org/wiki/Playing_card.

В колоде 52 карты; каждая принадлежит одной из четырех мастей и одной из 13 рангов. Масти - это пики, червы, бубны и трефы (в порядке убывания в бриджах). Ранги: туз, 2, 3, 4, 5, 6, 7, 8, 9, 10, валет, дама и король. В зависимости от того, в какую игру вы играете, туз может считаться выше короля или ниже 2.

Если мы хотим определить новый объект для представления игральной карты, довольно очевидно, какими должны быть переменные экземпляра: ранг и масть. Не так очевидно, какого типа должны быть переменные экземпляра. Один из возможных вариантов - String s, содержащий такие вещи, как «Spade» для мастей и «Queen» для рангов. Одна из проблем с этой реализацией заключается в том, что будет нелегко сравнить карты, чтобы увидеть, какие из них имеют более высокий ранг или масть.

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

Лопаты3
Сердца2
Бриллианты1
Клубы0

Очевидной особенностью этого сопоставления является то, что масти отображаются в целые числа по порядку, поэтому мы можем сравнивать масти, сравнивая целые числа. Отображение рангов довольно очевидно; каждый числовой ранг соответствует соответствующему целому числу, а для лицевых карт:

разъем11
Королева12
король13

Причина, по которой я использую математические обозначения для этих сопоставлений, заключается в том, что они не являются частью программы. Они являются частью дизайна программы, но никогда не появляются в коде явно. Определение класса для типа Card выглядит так:

Как обычно, я предоставляю два конструктора: один принимает параметр для каждой переменной экземпляра; другой не принимает параметров.

Чтобы создать объект, представляющий тройку клубов, мы вызываем new:

Первый аргумент, 0 представляет масть треф.

13.3 Метод printCard

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

Чтобы напечатать объекты Card таким образом, чтобы люди могли их легко читать, мы хотим отобразить целочисленные коды в слова. Естественный способ сделать это - использовать массив String s. Вы можете создать массив String s так же, как вы создаете массив примитивных типов:

Затем мы можем установить значения элементов массива.

Создание массива и инициализация элементов - настолько распространенная операция, что Java предоставляет для нее специальный синтаксис:

Этот оператор эквивалентен отдельному объявлению, распределению и присваиванию. Диаграмма состояний этого массива выглядит так:

Элементы массива являются ссылками на String s, а не на сами String.

Теперь нам нужен еще один массив String s для декодирования рангов:

Причина для "narf" состоит в том, чтобы действовать как хранитель места для нулевого элемента массива, который никогда не используется (или не должен использоваться). Допустимые только ранги 1–13. Чтобы избежать потери этого элемента, мы могли бы начать с 0, но отображение будет более естественным, если мы закодируем 2 как 2, а 3 как 3 и т. Д.

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

выражение Suits [c.suit] означает «использовать переменную экземпляра suit из объекта c в качестве индекса в массиве с именем Suits и выбрать соответствующую строку». Вывод этого кода

Бубновый валет.

13.4 Метод sameCard

Слово «то же самое» - одна из тех вещей, которые встречаются в естественном языке, которые кажутся совершенно ясными, пока вы не задумаетесь над ним, а затем поймете, что это нечто большее, чем вы ожидали.

Например, если я говорю: «У нас с Крисом одна и та же машина», я имею в виду, что его машина и моя одной марки и модели, но это две разные машины. Если я говорю: «У нас с Крисом одна и та же мать», я имею в виду, что его мать и моя - одно лицо. Итак, идея «одинаковости» различается в зависимости от контекста.

Когда вы говорите об объектах, возникает аналогичная двусмысленность. Например, если две карты одинаковы, означает ли это, что они содержат одни и те же данные (ранг и масть), или они на самом деле являются одним и тем же объектом карты?

Чтобы узнать, относятся ли две ссылки к одному и тому же объекту, мы используем оператор ==. Например:

Ссылки на один и тот же объект идентичны. Ссылки на объекты с одинаковыми данными эквивалентны.

Чтобы проверить эквивалентность, обычно пишут метод с таким именем, как sameCard.

Вот пример, который создает два объекта с одинаковыми данными и использует sameCard, чтобы проверить, эквивалентны ли они:

Если ссылки идентичны, они также эквивалентны, но если они эквивалентны, они не обязательно идентичны.

В этом случае card1 и card2 эквивалентны, но не идентичны, поэтому диаграмма состояний выглядит так:

Как это выглядит, когда card1 и card2 идентичны?

В Разделе 8.10 я сказал, что вы не должны использовать оператор == в String s, потому что он не делает того, что вы ожидаете. Вместо сравнения содержимого String (эквивалентность) он проверяет, являются ли две String одним и тем же объектом (идентичностью).

13.5 Метод compareCard

Для примитивных типов условные операторы сравнивают значения и определяют, когда одно больше или меньше другого. Эти операторы ( и другие) не работают для типов объектов. Для String Java предоставляет метод compareTo. Для Card мы должны написать свою собственную, которую мы назовем compareCard. Позже мы будем использовать этот метод для сортировки колоды карт.

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

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

Чтобы карты были сопоставимы, мы должны решить, что важнее, ранг или масть. Выбор произвольный, но когда вы покупаете новую колоду карт, в ней будут отсортированы все трефы вместе, затем все бубны и так далее. Итак, допустим, что костюм более важен.

После этого мы можем написать compareCard. Он принимает две карты в качестве параметров и возвращает 1, если первая карта выигрывает, -1, если вторая карта выигрывает, и 0, если они эквивалентны.

Сначала сравним костюмы:

Если ни одно из утверждений не соответствует действительности, масти должны быть равны, и мы должны сравнить ранги:

Если ни одно из этих условий не соответствует действительности, ранги должны быть равны, поэтому мы возвращаем 0.

13.6 Массивы карт

К настоящему времени мы увидели несколько примеров композиции (способность сочетать языковые особенности в различных аранжировках). Одним из первых увиденных нами примеров было использование вызова метода как части выражения. Другой пример - вложенная структура операторов: вы можете поместить оператор if в цикл while или в другой оператор if и т. Д.

Увидев этот шаблон и узнав о массивах и объектах, вы не должны удивляться, узнав, что вы можете создавать массивы объектов. И вы можете определять объекты с массивами как переменные экземпляра; вы можете создавать массивы, содержащие массивы; вы можете определять объекты, которые содержат объекты, и так далее. В следующих двух главах мы увидим примеры этих комбинаций с использованием объектов Card.

В этом примере создается массив из 52 карт:

Вот диаграмма состояний этого объекта:

Массив содержит ссылки на объекты; он не содержит самих объектов Card. Элементы инициализируются нулевым значением. Вы можете получить доступ к элементам массива обычным способом:

Но если вы попытаетесь получить доступ к переменным экземпляра несуществующей карты, вы получите исключение NullPointerException.

Но это правильный синтаксис для доступа к рангу «нулевой» карты в колоде. Это еще один пример композиции, сочетающей синтаксис для доступа к элементу массива и переменной экземпляра объекта.

Самый простой способ заполнить колоду объектами Card - написать вложенные циклы for (т.е. один цикл внутри тела другого):

Внешний цикл перечисляет масти от 0 до 3. Для каждой масти внутренний цикл перечисляет ранги от 1 до 13. Поскольку внешний цикл выполняется 4 раза, а внутренний цикл выполняется 13 раз, тело выполняется 52 раза.

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

13.7 Метод printDeck

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

Так как карты имеют тип Card [], элемент карт имеет тип Card. Итак, card [i] - это законный аргумент в пользу printCard.

13.8 Поиск

Следующий метод, который я напишу, - это findCard, который ищет в массиве Card s, чтобы узнать, содержит ли он определенную карту. Этот метод дает мне возможность продемонстрировать два алгоритма: линейный поиск и поиск пополам.

Линейный поиск довольно очевиден; мы проходим по колоде и сравниваем каждую карту с той, которую ищем. Если мы ее находим, то возвращаем указатель, в котором находится карточка. Если его нет в колоде, возвращаем -1.

Аргументами findCard являются карта и карты. Может показаться странным иметь переменную с тем же именем, что и тип (переменная card имеет тип Card). Мы можем заметить разницу, потому что переменная начинается со строчной буквы.

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

Если карты в колоде не в порядке, нет возможности искать быстрее, чем это. Мы должны смотреть на каждую карту, потому что иначе мы не можем быть уверены, что нужной нам карты нет.

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

  1. Начните где-нибудь посередине.
  2. Выберите слово на странице и сравните его со словом, которое вы ищете.
  3. Если вы найдете искомое слово, остановитесь.
  4. Если искомое слово стоит после слова на странице, перейдите в другое место в словаре и перейдите к шагу 2.
  5. Если слово, которое вы ищете, стоит перед словом на странице, перейдите к более раннему месту в словаре и переходите к шагу 2.

Если вы когда-нибудь дойдете до того, что на странице есть два соседних слова, и ваше слово окажется между ними, вы можете сделать вывод, что вашего слова нет в словаре.

Возвращаясь к колоде карт, если мы знаем, что карты в порядке, мы можем написать более быструю версию findCard. Лучший способ написать поиск пополам - использовать рекурсивный метод, потому что деление пополам естественно рекурсивно.

Хитрость заключается в том, чтобы написать метод под названием findBisect, который принимает в качестве параметров два индекса, low и high, указывая сегмент массива, который следует искать (включая как низкий, так и высокий).

  1. Для поиска в массиве выберите индекс между низким и высоким (назовите его средним) и сравните его с картой, которую вы ищете.
  2. Если вы его нашли, остановитесь.
  3. Если средняя карта выше вашей, ищите диапазон от низкой до средней 1.
  4. Если средняя карта ниже вашей, ищите диапазон от mid + 1 до high.

Шаги 3 и 4 подозрительно похожи на рекурсивные вызовы. Вот как это выглядит, переведенное в Java-код:

Этот код содержит ядро ​​поиска пополам, но в нем все еще отсутствует важная часть, поэтому я добавил комментарий TODO. Как написано, метод повторяется навсегда, если карты нет в колоде. Нам нужен базовый случай, чтобы справиться с этим условием.

Если high меньше, чем low, между ними нет карт, мы делаем вывод, что карты нет в колоде. Если мы справимся с этим случаем, метод работает правильно:

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

И получил следующий вывод:

Затем я составил карту, которой нет в колоде (15 бубен), и попытался ее найти. Получилось следующее:

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

Количество рекурсивных вызовов обычно составляет 6 или 7, поэтому мы вызываем compareCard только 6 или 7 раз, по сравнению с 52 раза, если бы мы выполняли линейный поиск. В общем, деление пополам выполняется намного быстрее, чем линейный поиск, и тем более для больших массивов.

Две распространенные ошибки в рекурсивных программах - это забвение включения базового случая и запись рекурсивного вызова, так что базовый вариант никогда не достигается. Любая из этих ошибок вызывает бесконечную рекурсию, которая вызывает исключение StackOverflowException. (Подумайте о диаграмме стека для рекурсивного метода, который никогда не заканчивается.)

13.9 Колоды и подколоды

Вот прототип (см. Раздел 8.5) findBisect:

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

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

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

Более общее определение «абстракции»: «Процесс моделирования сложной системы с упрощенным описанием для подавления ненужных деталей при фиксации соответствующего поведения».

13.10 Глоссарий

13.11 Упражнения

Напишите метод под названием handScore, который принимает в качестве аргумента массив карточек и возвращает общий счет.

  1. Напишите метод с именем suitHist, который принимает в качестве параметра массив карт и возвращает гистограмму мастей в руке. Ваше решение должно проходить через массив только один раз.
  2. Напишите метод с именем hasFlush, который принимает в качестве параметра массив Cards и возвращает true, если рука содержит флеш, и false в противном случае.

Сначала загрузите http://thinkapjava.com/code/CardTable.java и http://thinkapjava.com/code/cardset.zip в одну и ту же папку. Затем разархивируйте cardset.zip, который содержит подпапку cardset-oxymoron со всеми изображениями карточек. (Обратите внимание, что переменная cardset в CardTable.main - это имя этой папки.) Запустите CardTable.java, и вы должны увидеть изображения колоды карт, разложенных на зеленом столе.

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

Сергей Иващенко

08.09.2021

Подписывайтесь на наши социальные сети!