Домашние задания

Домашнее задание 1. Обработка ошибок

  1. Разработайте классы Checked*, выполняющие соответствующие операции с проверкой на переполнения и неверные аргументы.
  2. Добавьте в программу, вычисляющую выражения, обработку ошибок, в том числе:
    • ошибки разбора выражений;
    • ошибки вычисления выражений.
  3. Для выражения 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) означает, что в процессе вычисления произошло деление на ноль (переполнение).
  4. При выполнении задания следует обратить внимание на дизайн и обработку исключений.
  5. Человеко-читаемые сообщения об ошибках должны выводиться на консоль.
  6. Программа не должна «падать» с исключениями (как стандартными, так и добавленными).
  7. Код должен находиться в пакете expression.exceptions.

Репозиторий курса

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

Домашнее задание 3. Очередь на массиве

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

Домашнее задание 4. Очереди

  1. Определите интерфейс очереди Queue и опишите его контракт.
  2. Реализуйте класс LinkedQueue — очередь на связном списке.
  3. Выделите общие части классов LinkedQueue и ArrayQueue в базовый класс AbstractQueue.

Это домашнее задание связано с предыдущим.

Домашнее задание 5. Вычисление в различных типах

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

  1. Создайте класс expression.generic.GenericTabulator, реализующий интерфейс expression.generic.Tabulator: 

        public interface Tabulator {
        Object[][][] tabulate(
            String mode, String expression,
            int x1, int x2, int y1, int y2, int z1, int z2
        ) throws Exception;
    }

    Аргументы

    • mode — режим работы
      РежимТип
      iint с детекцией переполнений
      ddouble
      biBigInteger
    • expression — вычисляемое выражение;
    • x1, x2; y1, y2; z1, z2 — диапазоны изменения переменных (включительно).

    Возвращаемое значение — таблица значений функции, где R[i][j][k] соответствует x = x1 + i, y = y1 + j, z = z1 + k. Если вычисление завершилось ошибкой, в соответствующей ячейке должен быть null.

  2. Доработайте интерфейс командной строки:
    • Первым аргументом командной строки программа должна принимать указание на тип, в котором будут производиться вычисления:
      ОпцияТип
      -iint с детекцией переполнений
      -ddouble
      -biBigInteger
    • Вторым аргументом командной строки программа должна принимать выражение для вычисления.
    • Программа должна выводить результаты вычисления для всех целочисленных значений переменных из диапазона −2..2.
  3. Реализация не должна содержать непроверяемых преобразований типов.
  4. Реализация не должна использовать аннотацию @SuppressWarnings.
  5. При выполнении задания следует обратить внимание на простоту добавления новых типов и операций.

Домашнее задание 6. Функциональные выражения на JavaScript

  1. Разработайте функции cnst, variable, add, subtract, multiply, divide, negate для вычисления выражений с переменной x.
  2. Функции должны позволять производить вычисления вида: 
    let expr = subtract(
    multiply(
        cnst(2),
        variable("x")
    ),
    cnst(3)
);

println(expr(5));
    При вычислении выражения вместо переменной x подставляется значение, переданное в качестве аргумента функции expr. Таким образом, результатом вычисления приведенного примера должно быть число 7.
  3. Тестовая программа должна вычислять выражение x2−2x+1, для x от 0 до 10.
  4. Сложный вариант. Требуется дополнительно написать функцию parse, осуществляющую разбор выражений, записанных в обратной польской записи. Например, результатом 
    parse("x x 2 - * x * 1 +")(5)
    должно быть число 76.
  5. При выполнении задания следует обратить внимание на:
    • Применение функций высшего порядка.
    • Выделение общего кода для операций.

Домашнее задание 7. Объектные выражения на JavaScript

  1. Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide, Negate для представления выражений с тремя переменными: x, y и z.
    1. Пример описания выражения 2x-3: 
      let expr = new Subtract(
    new Multiply(
        new Const(2),
        new Variable("x")
    ),
    new Const(3)
);

println(expr.evaluate(5, 0, 0));
    2. При вычислении такого выражения вместо каждой переменной подставляется её значение, переданное в качестве аргумента метода evaluate. Таким образом, результатом вычисления приведенного примера должно стать число 7.
    3. Метод toString() должен выдавать запись выражения в обратной польской записи. Например, expr.toString() должен выдавать «2 x * 3 -».
  2. Функция parse должна осуществлять разбор выражений, записанных в обратной польской записи. Например, результатом 
    parse("x x 2 - * x * 1 +").evaluate(5, 0, 0)
    должно быть число 76, а результатом 
    parse("x x 2 - * x * 1 +").toString()
    — строка «x x 2 - * x * 1 +».
  3. Сложный вариант.
    Метод diff("x") должен возвращать выражение, представляющее производную исходного выражения по переменной x. Например, expr.diff("x") должен возвращать выражение, эквивалентное new Const(2). Выражения new Subtract(new Const(2), new Const(0)) и 
    new Subtract(
    new Add(
        new Multiply(new Const(0), new Variable("x")),
        new Multiply(new Const(2), new Const(1))
    )
    new Const(0)
)
    так же будут считаться правильным ответом.
  4. Бонусный вариант.
    Требуется написать метод simplify(), производящий вычисления константных выражений. Например, 
    parse("x x 2 - * 1 +").diff("x").simplify().toString()
    должно возвращать «x x 2 - +» или аналогичное по сложности эквивалентное выражение.
  5. При выполнении задания следует обратить внимание на:
    • Применение инкапсуляции.
    • Выделение общего кода для операций.
    • Минимизацию необходимой памяти.