T.M. SoftStudio

feci quod potui, faciant meliora potentes

Купить полную версию курса "Введение в вычисления с Java" (русскоязычная версия, лекции, тесты, лабораторные работы)

Введение в вычисления с Java. Абстрактные типы данных (ADT). Eclipse

Неделя 10

Лекция 37

Введение

Темой этой лекции является абстрактный тип данных или ADT.

Вы сейчас должны быть хорошо знакомы с различными видами типов данных, в том числе примитивными типами данных, такими как int для целых и double для чисел с плавающей точкой.

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

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

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

Когда мы используем тип String, методы, такие как charAt, compareTo и substring часто используются для манипулирования строкой символов, которую он представляет.

В общем, абстрактный тип данных (ADT) представляет собой структуру данных, которая определяет характеристики набора данных и операции, которые можно выполнять с набором данных.

Но подробности о том, как данные представлены, и реализация скрыты от пользователей.

Например, когда мы используем строку символов, мы не должны знать, как строка символов представлена ​​внутренне и как метод charAt реализуется, пока он возвращает char значение выбранной позиции строки, как указано в спецификации метода charAt.

Таким образом, ключевой концепцией ADT является то, что он скрывает детали реализации от пользователей.

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

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

Я буду использовать ADT, известный как стек, чтобы проиллюстрировать полезность ADT.

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

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

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

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

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

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

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

Стек часто называют last-in-first out структурой данных (LIFO).

Две важные операции, поддерживаемые стеком абстрактных типов данных, являются push и pop.

Операция push добавляет запись на вершину стека и pop является операцией по удалению записи из верхней части стека.

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

Другие ADT также часто доступны в большинстве объектно-ориентированных языков программирования.

Другой ADT, похожий на стек, называется очередью.

В отличие от стека, добавление записей в очереди, можно проводить только в хвосте или в конце очереди.

Это похоже на то, когда вы выстраиваетесь купить билет или ждать своей очереди в супермаркете,

Вы должны встать в конец очереди.

Если же вы встанете в начало или в середину очереди, я уверен, что на вас кричали бы все другие, которые уже в очереди.

Удаление же записей, подобно стеку, может быть осуществлено только в начале очереди.

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

Два широко используемые операции это addLast для добавления объекта в конец очереди и removeFirst для удаления и возвращения объекта в начало очереди.

Пример стека

Вот некоторые примеры, иллюстрирующие использование push и pop для стека.

Предположим, что стек целых чисел уже создан.

Фигура здесь, кажется, указывает, что стек фиксированного размера.

Стек может фактически быть реализован с помощью динамического размера.

Операция push 1 разместит значение 1 в пустой стек.

push 2 поместит значение 2 сверху 1.

Операция pop, которая не принимает никаких аргументов, вернет верхний элемент из стека, который несет значение 2.

push 3 добавит 3 на вершину стека.

push 4 добавит еще один элемент 4 на вершину стека.

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

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

pop удаляет, а также возвращает значение на вершину стека, в данном случае, со значением 4.

Давайте рассмотрим простой пример с использованием стека для преобразования десятичного числа в двоичное число.

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

Для данного числа n повторяется процесс:

- Находится остаток от деления на 2.

- Остаток выводится.

- n обновляется до n/2.

Мы хотим сначала найти остаток от деления числа на два.

Например, дается число 29, и первый остаток будет 1.

n затем обновляется на n/2 с использованием целочисленного деления, в данном случае, 29/2 приведет к 14.

Продолжая процесс, следующий остаток 0, и далее следуют три 1.

Результат, полученный данным процессом, будет 10111, если остатки выводятся в порядке их создания.

Но правильный ответ должен быть 11101.

Так или иначе, мы должны хранить промежуточные результаты перед выводом их.

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

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

Предложенный подход будет push остатки в стек, а затем выводить результат, удаляя запись по одной из вершины стека.

Вот реализация идеи, использования стека для вывода десятичного числа в двоичном виде.

Пустой стек целого типа настроен изначально.

Двоичное число n, которое должно быть преобразовано, вводится в метод outputBinary в качестве параметра.

В этом while цикле, остатки n вычисляются и помещается в переменную bit.

Остаток вносится в целочисленный стек s.

n затем заменяется на n/2 с использованием целочисленного деления.

Обратите внимание, что мы явно обеспечиваем объект Integer как оболочку целого типа с помощью метода valueOf для класса Integer.

Когда while цикл завершается, стек должен содержать список остатков в обратном порядке, как они были получены.

2-й while цикл будет удалять остатки по одному сверху с помощью метода pop для стека s и присваивать bit.

Каждый из остатков, удаленных из стека, будет выводиться с помощью System.out.print.

Опять же, мы преобразовываем объект оболочки целого типа в целый типа, используя метод intValue.

Вот еще один вариант предыдущего примера.

Единственное различие заключается в том, что тип данных для внесения в стек или удаления из стека не был преобразован в объект Integer явно.

Здесь, мы можем просто использовать bit вместо целого объекта в качестве параметра, чтобы push потому что Java автоупаковка преобразует bit, параметр push, в "Integer.valueOf (bit)" во время компиляции.

Точно так же, для присвоения s.pop(), которое, как предполагается, возвращает объект Integer, автораспаковка будет конвертировать левую часть в s.pop(). intValue() во время компиляции.

Таким образом, обе программы будут эффективно вычислять то же самое.

Задача n-ферзей

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

В основном, в представлении пространства состояний, задача представляется в виде множества состояний.

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

Два состояния связаны, если существует операция, которая может превратить одно состояние в другое.

Один из примеров, которые мы использовали для иллюстрации представления пространства состояний, это игра в крестики-нолики.

Таким образом, игра начинается с начального состояния и может закончиться набором конечных состояний.

Два промежуточных состояний связаны, если существует операция между двумя состояниями.

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

Широко используемая стратегия для поиска решения в пространстве состояний называется откатом.

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

Легче всего проиллюстрировать, как откат работает с использованием примеров.

Классическим примером использования отката в поиске решения является проблема n-ферзей.

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

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

В шахматной игре, каждый игрок имеет только одного ферзя, но в задаче n-ферзей, есть в общей сложности n ферзей, то есть, для обычной 8x8 шахматной доски, там будет 8 ферзей.

В общем, n может быть любым числом.

Цель задачи n-ферзей является размещение n ферзей на шахматной доске nxn так, чтобы никакие два ферзя не смогут нападать друг на друга.

Давайте использовать n равный 5 в качестве примера. Вот 5x5 шахматная доска.

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

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

Точно так же, поскольку ферзь может двигаться по вертикали и по диагонали, ни один другой ферзь не может быть размещен в 0-м столбце и на основной диагонали.

Так, после размещения первого ферзя на 0-й строке, все эти позиции с крестом были исключены.

На 2-й строке, первая доступная позиция в 3-м столбце или столбце с индексом 2.

Размещение этого второго ферзя устранит все остальные позиции в этой строке и все другие позиции в столбце с индексом 2.

Что касается диагонали, в действительности существует два диагонали, как показано на схеме здесь.

По аналогии разместим остальных ферзей и у нас есть наше первое решение проблемы 5-ферзей.

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

Прежде чем двигаться дальше, вы можете сначала подумать о том, существуют ли другие варианты решения проблемы 5-ферзей.

Теперь, когда вы понимаете, что представляет собой проблема n-ферзей, давайте подумаем о том, как мы можем решить эту проблему.

Я буду использовать пример здесь, чтобы проиллюстрировать стратегию, которую мы собираемся использовать, чтобы решить проблему n-ферзей.



Мы разместим ферзей с первой строки по последней строки, и будем двигаться от самого левого столбца до самого правого столбца в каждой строке.

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

Значение, сохраненное в стеке, является меткой столбца, в данном случае, 0.

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

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

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

Мы начнем с 1-го столбца, это не является правильным шагом.

И мы постараемся двигать ферзя вправо или на 2-й столбец.

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

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

Теперь мы можем попытаться поместить третьего ферзя в 3-й строке, начиная с 1-го столбца.

Конфликт возникает с первым ферзем, так что он перемещается в следующий столбец.

Это не хорошо, потому что конфликт возникает со 2-м ферзем.

Следующий столбец тоже не хорош, потому что это находится в противоречии как с 1-м, так и со 2-м ферзем.

Точно так же, 4-й столбец также исключен из-за 2-го ферзя.

Так мы остались в последнем столбце, и к счастью, нет конфликтов с остальными ферзями.

И позиция 4 теперь может быть записана в стек.

Размещение 4 ферзя может быть получена с использованием той же стратегии и метка 1 записывается в стек.

Точно так же, правильное размещение получается и для последнего ферзя и метка 3 помещается в стек.

Так что это первое решение, которое мы получили в задаче 5-ферзей.

Что делать, если мы хотим получить все решения?

Где мы должны возвратиться к предыдущему шагу и определить, где продолжать искать другое решение.

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

Установлено, что 5-й ферзь был помещен в столбец с меткой 3, так что вместо того, чтобы начинать с самого левого столбца, как то, что мы делали раньше, мы можем начать проверять следующий столбец с этой позиции.

Установлено, что эта позиция в конфликте с обеими, первым и третьим ферзем.

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

Это означает, что не будет другого решения с текущим размещением предыдущих 4 ферзей.

Так что мы должны вернуться к предыдущей строке, и начать поиск решения.

Чтобы узнать текущее размещение ферзя на 4-й строке, верхний элемент в стеке удаляется и дает метку 1 или второй столбец.

Так он может двигаться вправо от этой позиции, а не из первого столбца.

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

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

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

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

Таким образом, мы должны двигаться на одну строку вверх снова.

Мы обнаружили, что второй ферзь в настоящее время в столбце с меткой 2.

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

Таким образом, второе решение будет: