Java course

• BinarySearch
  1. Реализуйте итеративный и рекурсивный варианты бинарного поиска в массиве.
  2. На вход подается целое число x и массив целых чисел a, отсортированный по невозрастанию. Требуется найти минимальное значение индекса i, при котором a[i] <= x.
  3. Для функций бинарного поиска и вспомогательных функций должны быть указаны, пред- и постусловия. Для реализаций методов должны быть приведены доказательства соблюдения контрактов в терминах троек Хоара.
  4. Интерфейс программы.
     • Имя основного класса — BinarySearch.
     • Первый аргумент командной строки — число x.
     • Последующие аргументы командной строки — элементы массива a.
  5. Пример запуска: java BinarySearch 3 5 4 3 2 1. Ожидаемый результат: 2.

• ExpressionParser
  1. Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide для вычисления выражений с одной переменной в типе int.
  2. Классы должны позволять составлять выражения вида:
     new Subtract(new Multiply(new Const(2), new Variable("x")), new Const(3)).evaluate(5)
     При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра методу evaluate (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7.
  3. Метод toString должен выдавать запись выражения в полноскобочной форме. Например,
     new Subtract(new Multiply(new Const(2), new Variable("x")), new Const(3)).toString()
     должен выдавать ((2 * x) - 3).
  4. Метод toMiniString должен выдавать выражение с минимальным числом скобок. Например,
     new Subtract(new Multiply(new Const(2), new Variable("x")), new Const(3)).toMiniString()
     должен выдавать 2 * x - 3.
  5. Реализуйте метод equals, проверяющий, что два выражения совпадают. Например,
     new Multiply(new Const(2), new Variable("x")).equals(new Multiply(new Const(2), new Variable("x")))
     должно выдавать true, а
     new Multiply(new Const(2), new Variable("x")).equals(new Multiply(new Variable("x"), new Const(2)))
     должно выдавать false.
  6. Для тестирования программы должен быть создан класс Main, который вычисляет значение выражения
     x * x − 2 * x + 1, для x, заданного в командной строке.
  7. При выполнении задания следует обратить внимание на:
     • Выделение общего интерфейса создаваемых классов.
     • Выделение абстрактного базового класса для бинарных операций.

• ExpressionParserAdvanced
  1. Доработайте предыдущее домашнее задание, так что бы выражение строилось по записи вида
     x * (x - 2) * x + 1
  2. В записи выражения могут встречаться: умножение *, деление /, сложение +, вычитание -, унарный минус -, целочисленные константы (в десятичной системе счисления, которые помещаются в 32-битный знаковый целочисленный тип), круглые скобки, переменные x и произвольное число пробельных символов в любом месте (но не внутри констант).
  3. Приоритет операторов, начиная с наивысшего
     • унарный минус
     • умножение и деление
     • сложение и вычитание
  4. Разбор выражений рекомендуется производить методом рекурсивного спуска. Алгоритм должен работать за линейное время.
  5. Добавьте в программу вычисляющую выражения обработку ошибок, в том числе:
     • ошибки разбора выражений>/li>
     • ошибки вычисления выражений
  6. Для выражения 1000000 * x * x * x * x * x / (x - 1) вывод программы должен иметь следующий вид:

     x	f
     0	0
     1	division by zero
     2	32000000
     3	121500000
     4	341333333
     5	overflow
     6	overflow
     7	overflow
     8	overflow
     9	overflow
     10	overflow

     Результат division by zero (overflow) означает, что в процессе вычисления произошло деление на ноль (переполнение).
  7. При выполнении задания следует обратить внимание на дизайн и обработку исключений.
  8. Человеко-читаемые сообщения об ошибках должны выводится на консоль.
  9. Программа не должна «вылетать» с исключениями (как стандартными, так и добавленными).

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

     Опция	Тип
     -i	int
     -d	double
     -bi	BigInteger

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

• MdParser
  1. Разработайте набор классов для текстовой разметки.
  2. Класс Paragraph может содержать произвольное число других элементов разметки и текстовых элементов.
  3. Класс Text – текстовый элемент.
  4. Классы разметки Emphasis, Strong, Strikeout – выделение, сильное выделение и зачеркивание. Элементы разметки могут содержать произвольное число других элементов разметки и текстовых элементов.
  5. Все классы должны реализовывать метод toMarkdown(StringBuilder), которой должен генерировать Markdown-разметку по следующим правилам:
     • текстовые элементы выводятся как есть
     • выделенный текст окружается символами *
     • сильно выделенный текст окружается символами __
     • зачеркнутый текст окружается символами ~
  6. Следующий код должен успешно компилироваться:

     Paragraph paragraph = new Paragraph(List.of(
           new Strong(List.of(
               new Text("1"),
               new Strikeout(List.of(
                   new Text("2"),
                   new Emphasis(List.of(
                       new Text("3"),
                       new Text("4")
                   )),
                   new Text("5")
               )),
               new Text("6")
           ))
       ));

     Вызов paragraph.toMakdown(new StringBuilder()) должен заполнять переданный StringBuilder следующим содержимым:
     __1~2*34*5~6__
  7. Разработанные классы должны находиться в пакете markup

• MdToHtmlParser
  1. Разработайте конвертер из Markdown-разметки в HTML.
  2. Конвертер должен поддерживать следующие возможности:
     • Абзацы текста разделяются пустыми строками.
     • Элементы строчной разметки: выделение (* или _), сильное выделение (** или __), зачеркивание --, код `
     • Заголовки (# * уровень заголовка)
  3. Конвертер должен называться Md2Html и принимать два аргумента: название входного файла с Markdown-разметкой и название выходного файла c HTML-разметкой. Оба файла должны иметь кодировку UTF-8.
  4. Пример

• MyScanner
  1. Реализуйте свой аналог класса Scanner на основе Reader.
  2. Код, управляющий чтением должен быть общим.
  3. Код, выделяющий числа и слова должен быть общим.
  4. При реализации блочного чтения обратите внимание на слова/числа, пересекающие границы блоков, особенно — больше одного раза.

• Queues
  1. Найдите инвариант структуры данных «очередь». Определите функции, которые необходимы для реализации очереди. Найдите их пред- и постусловия, при условии что очередь не содержит null.
  2. Реализуйте класс ArrayQueue, представляющие циклическую очередь с применением массива.
     Должны быть реализованы следующие функции (процедуры) / методы:
     • enqueue – добавить элемент в очередь
     • element – первый элемент в очереди
     • dequeue – удалить и вернуть первый элемент в очереди
     • size – текущий размер очереди
     • isEmpty – является ли очередь пустой
     • clear – удалить все элементы из очереди
     Инвариант, пред- и постусловия записываются в исходном коде в виде комментариев.
     Обратите внимание на инкапсуляцию данных и кода во всех трех реализациях.
  3. Определите интерфейс очереди Queue и опишите его контракт.
  4. Реализуйте класс LinkedQueue — очередь на связном списке.
  5. Выделите общие части классов LinkedQueue и ArrayQueue в базовый класс AbstractQueue.

• TicTacToe
  1. Реализуйте игру m, n, k.
  2. Добавьте обработку ошибок ввода пользователя.
  3. Проверку выигрыша нужно производить за O(k).
  4. Предотвратите жульничество: у игрока не должно быть возможности достать Board из Position.