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

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

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

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

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

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

  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. При выполнении задания следует обратить внимание на простоту добавления новых типов и операций.
  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.

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

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

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

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

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

Домашнее задание 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. При выполнении задания следует обратить внимание на:
    • Применение инкапсуляции.
    • Выделение общего кода для операций.
    • Минимизацию необходимой памяти.