Лабораторная работа 1: Java-Сразу к делу

JJava позволяет нам программировать с объектами. Мы используем классы, по одному для каждого файла, чтобы описать, как эти объекты работают - план, если хотите. Вот код для простого класса, который представляет двумерную точку:

/ **

* двумерный класс точки.

**/

общедоступный класс Point2d {

/ ** X координат точки **/

частный двойной xCoord;

/ ** Y координата точки **/

частный двойной yCoord;

/ ** Конструктор, чтобы инициализировать точку к (x, y) значение. **/

общедоступный Point2d (удваивают x, дважды y) {

xCoord = x;

yCoord = y;

}

/ ** Конструктор без параметров: значения по умолчанию к точке в источнике. **/

общедоступный Point2d () {

//Вызовите конструктор с двумя параметрами и определите источник.

это (0, 0);

}

/ ** Верните X координат точки. **/

общественность удваивает getX () {

верните xCoord;

}

/ ** Возвратите координату Y точки. **/

общественность удваивает getY () {

верните yCoord;

}

/ ** Набор X координат точки. **/

общественность освобождает setX (удвойте val) {

xCoord = val;

}

/ ** Набор координата Y точки. **/

общественность освобождает setY (удвойте val) {

yCoord = val;

}

}

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

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

Point2d myPoint = новый Point2d ();//создает точку в (0,0)

Point2d myOtherPoint = новый Point2d (5,3);//создает точку в (5,3)

Point2d aThirdPoint = новый Point2d ();

Будьте осторожны: myPoint! = aThirdPoint, даже при том, что их значения - те же. Это вызвано тем, что оператор равенства == (и его инверсия, оператор неравенства ! =) сравните эти две ссылки объекта на предмет равенства. Другими словами, == верните true, если эти две ссылки указывают на тот же объект. В этом коде myPoint и aThirdPoint каждый обращается к различному экземпляру класса Point2d, таким образом, myPoint == aThirdPoint возвращает false, даже при том, что их значения - те же!

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

Прежде чем Вы начнете кодировать ...

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

К сожалению, значение хорошего стиля кодирования часто изучается только болезненным опытом... Но, CS11 - хорошая возможность изучить и попрактиковать хороший стиль кодирования. Прежде чем вы начнете это задание, рассмотрите Инструкции по Стилю CS11 Java. На кластере CS есть даже полезная программа проверки стиля, которая сообщит о любых проблемах с вашей программой.

Ваша задача:

1. Создайте новый класс Point3d чтобы представить, что эти точки представлены в трехмерном Евклидовом пространстве. Должно быть возможно:

· создание нового Point3d, описанный любыми тремя, с плавающей точкой (тип дважды) значениями,

· создание нового Point3d в (0.0, 0.0, 0.0) по умолчанию,

· получение доступа и видоизменение всех трех значений индивидуально,

· сравнение двух Point3ds для равенства значения, используя соответствующий равный метод.

Не следует непосредственно получать доступ к внутренним элементам данных любого объекта Point3d.

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

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

· Ввод трех упорядоченных утраивается от пользователя, каждый представляя координаты одной точки с тремя пространствами. Генерируйте три объекта Point3d от этих данных. (На данный момент Вы можете принять, что пользователь не вводит недопустимые данные.)

Если Вы не знаете, как получить ввод пользователя, Вы можете использовать функцию в этом файле. Поместите его как статический метод в Ваш класс Lab1. Обратите внимание на то, что этот метод использует классы в комплекс java.io, который не видим вашему коду по умолчанию. Чтобы сделать его видимым, добавьте его к очень главному из Вашего файла:

импорт java.io.*;

Это делает все классы в комплексе java.io видимыми Вашему коду Lab1. (Вы не должны делать этого с классами комплекса java.lang , так как те сделаны доступными для ваших классов по умолчанию.)

· Запишите второй статический метод computeArea, который берет три Point3d и вычисляет область в треугольнике, ограниченном ими. (Вы можете использовать формулу Heron's.) Верните эту область как двойную.

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

Прежде чем Вы вызовете computeArea, проверьте равенство значения между всеми тремя Point3d. Если какая-либо пара точек "равна", сообщите об этом пользователю и не вычисляйте область.

4. Соберите оба из своих исходных файлов вместе:

javac Point3d.java Lab1.java

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

5. Когда Вы закончите с лабораторией 1, Вы можете представить свои файлы на csman веб-сайте.

Лабораторная работа 3: Java-Я звезда!

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

Один очень широко используемый алгоритм для этого вида проблемы называют А* (произносится "A-звезда"), и это - очень эффективный алгоритм для новаторства в компьютерной программе. Алгоритм концептуально довольно прост. Запускаясь с начального расположения, алгоритм постепенно создает путь от источника до места назначения, всегда используя "до сих пор лучший путь ", чтобы сделать следующий шаг. Это гарантирует, что завершающий путь также будет оптимальным. (Если Вы хотите узнать больше о А* новаторский алгоритм, Вы можете открыть статьи Wikipedia на А* и следовать по ссылкам, которые дает статья.)

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

Вы можете щелкнуть по различным квадратам, чтобы превратить их в барьеры (красные) или проходимые клетки (белые). Синие клетки обозначают запуск и конец пути. Нажатие по кнопке "Find Path" вычислит путь, используя А*, и затем выведет на экран его в зеленом. Или, если не будет никакого пути от запуска, чтобы завершиться, программа просто не покажет пути.

A* алгоритм имеет много информации, чтобы отслеживать, и набор классов Java идеально подходит для такого рода задач. Есть два основных вида информации, которыми A* должно осуществлять управление:

· Локации – это просто наборы координат конкретных клеток на двухмерной карте. A* алгоритм должен иметь возможность ссылаться на определенные места на карте. Путевые точки- это отдельные шаги на пути, которые А* алгоритм генерирует. Например, вышеперечисленные шаги зеленого пути -это просто последовательность точек через карту. Каждая точка содержит несколько элементов информации, связанные с ней:

· Расположение ячейке как точка пути.

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

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

· Эвристическая оценка (предположение, другими словами) оставшейся стоимости передвижения от этого места до конечного пункта назначения.

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

· Первый набор "открытые точки", или точки, которые еще должны быть рассмотрены алгоритмом А*.

· Второй набор "закрытые точки", или точки, которые уже были рассмотрены алгоритмом A* и их не надо будет снова рассматривать.

Каждая итерация А* алгоритма довольно проста: найти наименее дорогостоящий пункт из набора открытых точек, сделать шаг в любом направлении от этой точки для создания новой открытой точки, а затем переместить путевую точку из открытого набор в закрытый набор. Это повторяется до тех пор, пока текущая точка не достигнет пункта назначения! Если во время этого процесса алгоритм открытых точек заканчивается, то нет пути от начальной точки до пункта назначения. Такая обработка в первую очередь зависит от расположения точек, поэтому он очень полезен для хранения путевых точек как отображение от места до соответствующих точек. Таким образом, вы будете использовать хранилище java.util. hashmap для каждого из этих наборов с Расположением объектов в качестве кодов, и путевых точек объектов в качестве значений.

Прежде чем начать

Прежде чем начать, вы должны скачать исходные файлы для данной лабораторной работы:

· Map2D.java - представляет собой карту, по которой А* алгоритм двигается, в том числе проходимы ли клетки или нет

· Location.java - этот тип представляет собой координаты конкретной ячейки на карте

· Waypoint.java - представляет отдельные точки в созданный путь

· AStarPathfinder.java - этот тип реализует А* алгоритм поиска пути как статический метод

· AStarState.java - этот тип хранит набор открытых точек и закрытых точек, и обеспечивает базовые операции, необходимые для функционирования алгоритма поиска А*.

· AStarApp.java - простое Swing-приложение, которое обеспечивает редактируемый вид 2D карты, и запускает поиск пути по запросу

· JMapCell.java - это обычай Swing -компонент, который используется для отображения состояния клеток на карте

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

Размещение

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

· Обеспечение реализации метода equals ().

· Обеспечение реализации метода hashcode().

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

А*Форма

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

Как упоминалось ранее, А* форма состоит из двух наборов путевых точек, одна из открытых точек, и другие из закрытых точек. Чтобы облегчить алгоритм, путевые точки будут храниться в хэш-карте, в месте, в котором находятся коды, путевые точки и сами значения. Таким образом, у вас будет тип такой:

Хранилище <Расположение, Точка>

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

Добавить две (нестатические) области класса AStarState с этим типом, одна для "открытых точек" и другая для "закрытых точек." Кроме того, убедитесь, что нужно инициализировать каждую из этих областей, чтобы отнести в новую пустую коллекцию.

Если у вас есть созданные и инициализированые области, вы должны реализовать следующие методы типа AStarState:

public int numOpenWaypoints()

Этот метод просто возвращает количество точек в набор открытых точек. (Да, это будет остроумное замечание...)

public Waypoint getMinOpenWaypoint()

Эта функция должна проверить все точки в наборе открытых точек, и вернуть ссылку на точку с наименьшей общей стоимостью. Если нет точки в "открытых" наборах, вернитесь NULL.

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

public boolean addOpenWaypoint(Waypoint newWP)

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

· Если в настоящее время нет точек для этого места в "открытых точках" набора, то просто добавить новую точку.

· Если точка уже в этом месте в "открытой точки" набора, то потом добавить новый пункт, только Если "старая цена" за новую точку меньше "старой цены" за текущую точку. (Убедитесь, что используете прежнюю стоимость, а не общую стоимость.) Другими словами, если новая точка представляет собой более короткий путь к этому месту, чем текущий маршрут, заменить текущую точку на новую

Вы можете увидеть, что вам придется вернуть существующую маршрутную точку с «открытого"набора, если он есть, и действовать в соответствии. К счастью, это очень просто - заменить предыдущую точку на новую; просто используйте метод hashmap. put () как обычно, и он заменит старый код, а значения сопоставит с новым кодом.

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

public boolean isLocationClosed(Location loc)

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

public void closeWaypoint(Location loc)

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

Удалите соответствие точки указанному расположению из набора «открытого точек».
Добавьте точку, которую Вы просто удалили из набора закрытых точек. Конечно, ключ должен быть расположением точки.

Компиляция и тестирование

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

javac*.java
java AStarApp

После того, как Вы уверены, что все работает правильно, представьте свою работу на csman!