Парадигмы программирования

Условия домашних заданий

Java

Домашнее задание 1. Хэширование

Разработайте Java-программу CalcMD5, которая подсчитывает MD5-хэши файлов.
- Программа должна принимать один аргумент командной строки — имя файла, в котором содержатся имена файлов, для которых требуется подсчитать хэши. Файлы перечислены по одному на строке.
- Программа должна выдать на стандартный вывод MD5-хэши файлов в порядке их перечисления во входном файле. Хэши должны выдаваться в виде 32-значных шестнадцатеричных чисел.
- Например, если файл input.txt содержит только input.txt (9 символов), то при запуске java CalcMD5 input.txt, на консоль должно быть выведено A8546347050ADC932FBEC189DC9FD50D.
- Примечания.
- Стандартная библиотека Java содержит реализацию алгоритма MD5.
- Вы можете рассчитывать, что все файлы помещаются в память.
- Можно написать решение, состоящее из четырех содержательных строк.

Решение

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

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

Решение

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

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

Решение

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

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

Решение

Домашнее задание 5. Вычисление выражений

Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide для вычисления выражений с одной переменной.
- Классы должны позволять составлять выражения вида ```
  new Subtract( new Multiply( new Const(2), new Variable(“x”) ), new Const(3) ).evaluate(5)
```
При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра методу evaluate (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7. * Для тестирования программы должен быть создан класс Mathlog.src.Main, который вычисляет значение выражения x2−2x+1, для x`, заданного в командной строке. * При выполнение задания следует обратить внимание на: * Выделение общего интерфейса создаваемых классов. * Выделение абстрактного базового класса для бинарных операций.

Решение

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

Доработайте предыдущее домашнее задание, так что бы выражение строилось по записи вида
```
x * (y - 2)*z + 1
```
Для этого реализуйте класс ExpressionParser с методом TripleExpression parse(String).
- В записи выражения могут встречаться:
- умножение *
- деление /
- сложение +
- вычитание -
- унарный минус -
- целочисленные константы (в десятичной системе счисления, которые помещаются в 32-битный знаковый целочисленный тип)
- круглые скобки
- переменные (x, y и z)
- произвольное число пробельных символов в любом месте (но не внутри констант). * Приоритет операторов, начиная с наивысшего
- унарный минус;
- умножение и деление;
- сложение и вычитание. * Для выражения 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. Вычисление в различных типах

Добавьте в программу вычисляющую выражения поддержку различных типов.
- Первым аргументом командной строки программа должна принимать указание на тип, в котором будут производится вычисления:
  - -i int
  - -d double
  - -bi BigInteger
- Реализация не должна содержать непроверяемых преобразований типов.
- Реализация не должна использовать аннотацию @SuppressWarnings. * При выполнении задания следует обратить внимание на легкость добавления новых типов и операциий.

Решение

Javascript

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

Разработайте функции cnst, variable, add, subtract, multiply, divide для вычисления выражений с одной переменной.

Функции должны позволять производить вычисления вида: ``` var expr = subtract( multiply( cnst(2), variable(“x”) ), cnst(3) ); println(expr(5));

При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра функции `expr` (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число `7`.
       * Тестовая программа должна вычислять выражение `x2−2x+1`, для `x` от `0` до `10`.
       * **Усложненный вариант.** Требуется написать функцию parse, осуществляющую разбор выражений, записанных в [обратной польской записи.](https://en.wikipedia.org/wiki/Reverse_Polish_notation) Например, результатом

parse("x x 2 - * x * 1 +")(5)

``` должно быть число 76. * При выполнение задания следует обратить внимание на:

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

Решение

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

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

Пример описания выражения 2x-3:

                              var expr = new Subtract(
                                  new Multiply(
                                      new Const(2),
                                      new Variable("x")
                                  ),
                                  new Const(3)
                              );
      

   * Метод `evaluate(x)` должен производить вычисления вида: При вычислении такого выражения вместо каждой переменной подставляется значение `x`, переданное в качестве параметра функции `evaluate` (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число `7.`
   * Метод `toString()` должен выдавать запись выражения в [обратной польской записи.](https://en.wikipedia.org/wiki/Reverse_Polish_notation) Например, `expr.toString()` должен выдавать `2 x * 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)
                      )

так же будут считаться правильным ответом )
       * **Бонусный вариант.** Требуется написать метод `simplify()`, производящий вычисления константных выражений. Например,

 parse("x x 2 - * 1 *").diff("x").simplify().toString()

``` должно возвращать x x 2 - +. * При выполнение задания следует обратить внимание на:

Применение инкапсуляции.
Выделение общего кода для бинарных операций.

Решение

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

Добавьте в предыдущее домашнее задание функцию parsePrefix(string), разбирающую выражения, задаваемые записью вида (- (* 2 x) 3). Если разбираемое выражение некорректно, метод parsePrefix должен бросать человеко-читаемое сообщение об ошибке.
- Добавьте в предыдущее домашнее задание метод prefix(), выдающий выражение в формате, ожидаемом функцией parsePrefix.
- При выполнение задания следует обратить внимание на:
- Применение инкапсуляции.
- Выделение общего кода для бинарных операций.
- Обаботку ошибок.
- Минимизацию необходимой памяти.

Решение

Clojure

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

Условия задачи

Разработайте функции constant, variable, add, subtract, multiply и divide для представления арифметических выражений.
- Пример описания выражения 2x-3:
```
                               (def expr 
                                 (subtract
                                   (multiply 
                                     (constant 2) 
                                     (variable "x")) 
                                   (constant 3)))
                                        
```
- Выражение должно быть функцией, возвращающей значение выражение при подстановке элементов, заданных отображением. Например, (expr {"x" 2}) должно быть равно 1. * Разработайте разборщик выражений, читающий выражения в стандартной для Clojure форме. Например, ``` (parseFunction “(- (* 2 x) 3)”)

   должно быть эквивалентно expr.
* **Усложненный вариант.** Функции `add`, `subtract`, `multiply` и должны принимать произвольное число аргументов. Разборщик так же должен допускать произвольное число аргументов для `+`, `-`, `*`.
* При выполнение задания следует обратить внимание на:
   * Выделение общего кода для операций.

###   [Решение](/Ifmo-code/Paradigm/clojure/expression.clj)


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


1. Разработайте конструкторы `Constant`, `Variable`, `Add`, `Subtract`, `Multiply` и `Divide` для представления выражений с одной переменной.
   1. Пример описания выражения `2x-3`:
      ```
                                    (def expr 
                                      (Subtract
                                        (Multiply
                                          (Constant 2)
                                          (Variable "x"))
                                        (Const 3)))
      
      ```
   * Функция `(evaluate expression vars)` должна производить вычисление выражения `expression` для значений переменных, заданных отображением `vars`. Например, `(evaluate expr {"x" 2})` должно быть равно `1`.
   * Функция `(toString expression)` должна выдавать запись выражения в стандартной для Clojure форме.
   * Функция `(parseObject "expression")` должна разбирать выражения, записанные в стандартной для Clojure форме. Например,
      ```
          (parseObject "(- (* 2 x) 3)")
      ```
   должно быть эквивалентно expr.
   * Функция `(diff expression "variable")` должена возвращать выражение, представляющее производную исходного выражения по заданой пермененной. Например, `(diff expression "x")` должен возвращать выражение, эквивалентное `(Constant 2)`, при этом выражения `(Subtract (Const 2) (Const 0))` и
      ```
                                    (Subtract
                                      (Add
                                        (Multiply (Const 0) (Variable "x"))
                                        (Multiply (Const 2) (Const 1)))
                                      (Const 0))
         
      ```   
   так же будут считаться правильным ответом.
* **Усложненный вариант.** Функция `(parseObjectInfix "expression")` должна разбирать выражения, записанные в инфиксной форме. Например,

    (parseObjectInfix "2 * x - 3")

``` должно быть эквивалентно expr.

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

Ifmo-code

Ifmo hometasks and contests

Парадигмы программирования

Java

Домашнее задание 1. Хэширование

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

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

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

Домашнее задание 5. Вычисление выражений

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

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

Javascript

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

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

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

Clojure

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

Условия задачи