• Тесты:
  • https://www.kgeorgiy.info/git/geo/prog-intro-2022/
  • https://www.kgeorgiy.info/git/geo/paradigms-2023

Первый семестр

Домашнее задание 11. Выражения

• Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide для вычисления выражений с одной переменной в типе int (интерфейс Expression).

• Классы должны позволять составлять выражения вида

  new Subtract(
  new Multiply(
      new Const(2),
          new Variable("x")
      ),
      new Const(3)
  ).evaluate(5)
  

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

• Метод toString должен выдавать запись выражения в полноскобочной форме. Например

  new Subtract(
      new Multiply(
          new Const(2),
          new Variable("x")
      ),
      new Const(3)
  ).toString()
  

  должен выдавать ((2 * x) - 3).

• Сложный вариант. Метод toMiniString (интерфейс ToMiniString) должен выдавать выражение с минимальным числом скобок. Например

  new Subtract(
      new Multiply(
          new Const(2),
          new Variable("x")
      ),
      new Const(3)
  ).toMiniString()
  

  должен выдавать 2 * x - 3.

• Реализуйте метод 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.

• Для тестирования программы должен быть создан класс Main, который вычисляет значение выражения x^2−2x+1, для x, заданного в командной строке.

• При выполнении задания следует обратить внимание на:

  • Выделение общего интерфейса создаваемых классов.
  • Выделение абстрактного базового класса для бинарных операций.

Модификации

• Base
  • Реализуйте интерфейс Expression
• Triple
  • Дополнительно реализуйте поддержку выражений с тремя переменными: x, y и z.
  • Интерфейс TripleExpression.
• Double
  • Дополнительно реализуйте вычисления в типе double.
  • Интерфейс DoubleExpression.

Домашнее задание 12. Разбор выражений

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

  x * (x - 2)*x + 1
  

• В записи выражения могут встречаться:

  • бинарные операции: умножение *, деление /, сложение + и вычитание -;
  • унарный минус -;
  • переменные x, y и z;
  • целочисленные константы в десятичной системе счисления, помещающиеся в 32-битный знаковый целочисленный тип;
  • круглые скобки для явного обозначения приоритета операций;
  • произвольное число пробельных символов в любом месте, не влияющем на однозначность понимания формулы (например, между операцией и переменной, но не внутри констант).

• Приоритет операций, начиная с наивысшего

  • унарный минус;
  • умножение и деление;
  • сложение и вычитание.

• Разбор выражений рекомендуется производить методом рекурсивного спуска.

  • Алгоритм должен работать за линейное время.
  • Лексический анализ (токенизация) не требуется.

Модификации

• Base
  • Класс ExpressionParser должен реализовывать интерфейс TripleParser
  • Результат разбора должен реализовывать интерфейс TripleExpression
• SetClear
  • Дополнительно реализуйте бинарные операции (минимальный приоритет):
    • set – установка бита, 2 set 3 равно 10;
    • clear – сброс бита, 10 clear 3 равно 2.
• Count
  • Дополнительно реализуйте унарную операцию count – число установленных битов, count -5 равно 31.

Второй семестр

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

• Добавьте в программу, вычисляющую выражения, обработку ошибок, в том числе:

  • ошибки разбора выражений;
  • ошибки вычисления выражений.

• Для выражения 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) означает, что в процессе вычисления произошло деление на ноль (переполнение).

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

• Человеко-читаемые сообщения об ошибках должны выводиться на консоль.

• Программа не должна «вылетать» с исключениями (как стандартными, так и добавленными).

Модификации

• Base
  • Класс ExpressionParser должен реализовывать интерфейс TripleParser
  • Классы CheckedAdd, CheckedSubtract, CheckedMultiply, CheckedDivide и CheckedNegate должны реализовывать интерфейс TripleExpression
  • Нельзя использовать типы long и double
  • Нельзя использовать методы классов Math и StrictMath
• SetClear
  • Дополнительно реализуйте бинарные операции (минимальный приоритет):
    • set – установка бита, 2 set 3 равно 10;
    • clear – сброс бита, 10 clear 3 равно 2.
• Count
  • Дополнительно реализуйте унарную операцию count – число установленных битов, count -5 равно 31.
• PowLog10
  • Дополнительно реализуйте унарные операции:
    • log10 – логарифм по уснованию 10, log10 1000 равно 3;
    • pow10 – 10 в степени, pow10 4 равно 10000.

Домашнее задание 2. Бинарный поиск

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

Модификации

• Базовая
  • Класс BinarySearch должен находиться в пакете search
• Oddity
  • Если сумма всех чисел во входе чётная, то должна быть использоваться рекурсивная версия, иначе — итеративная.
• Uni
  • На вход подается массив полученный приписыванием в конец массива отсортированного (строго) по возрастанию, массива отсортированного (строго) по убыванию. Требуется найти минимальную возможную длину первого массива.
  • Класс должен иметь имя BinarySearchUni

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

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

Модификации

• Базовая
  • Классы должны находиться в пакете queue
• Deque
  • Дополнительно реализовать методы
    • push – добавить элемент в начало очереди;
    • peek – вернуть последний элемент в очереди;
    • remove – вернуть и удалить последний элемент из очереди.
• DequeToArray
  • Реализовать модификацию Deque;
  • Реализовать метод toArray, возвращающий массив, содержащий элементы, лежащие в очереди в порядке от головы к хвосту.

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

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

Модификации

• Базовая
• Contains
  • Добавить в интерфейс очереди и реализовать методы
    • contains(element) – проверяет, содержится ли элемент в очереди
    • removeFirstOccurrence(element) – удаляет первое вхождение элемента в очередь и возвращает было ли такое
  • Дублирования кода быть не должно

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

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

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

  • Аргументы

    • mode — режим работы

       Режим	Тип
      
       i	int с детекцией переполнений
       d	double
       bi	BigInteger
      

    • expression — вычисляемое выражение;

    • x1, x2; y1, y2; z1, z2 — диапазоны изменения переменных (включительно).

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

• Доработайте интерфейс командной строки:

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

    Опция	Тип
    -i	int с детекцией переполнений
    -d	double
    -bi	BigInteger
    

  • Вторым аргументом командной строки программа должна принимать выражение для вычисления.

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

• Реализация не должна содержать непроверяемых преобразований типов.

• Реализация не должна использовать аннотацию @SuppressWarnings.

• При выполнении задания следует обратить внимание на простоту добавления новых типов и операциий.

Модификации

• Base
  • Класс GenericTabulator должен реализовывать интерфейс Tabulator и строить трехмерную таблицу значений заданного выражения.
    • mode – режим вычислений:
      • i – вычисления в int с проверкой на переполнение;
      • d – вычисления в double без проверки на переполнение;
      • bi – вычисления в BigInteger.
    • expression – выражение, для которого надо построить таблицу;
    • x1, x2 – минимальное и максимальное значения переменной x (включительно)
    • y1, y2, z1, z2 – аналогично для y и z.
    • Результат: элемент result[i][j][k] должен содержать значение выражения для x = x1 + i, y = y1 + j, z = z1 + k. Если значение не определено (например, по причине переполнения), то соответствующий элемент должен быть равен null.
• Asm
  • Дополнительно реализуйте унарные операции:
    • abs – модуль числа, abs -5 равно 5;
    • square – возведение в квадрат, square 5 равно 25.
  • Дополнительно реализуйте бинарную операцию (максимальный приоритет):
    • mod – взятие по модулю, приоритет как у умножения (1 + 5 mod 3 равно 1 + (5 mod 3) равно 3).
• Uls
  • Дополнительно реализуйте поддержку режимов:
    • u – вычисления в int без проверки на переполнение;
    • l – вычисления в long без проверки на переполнение;
    • s – вычисления в short без проверки на переполнение.