Выполненные задания к курсу "Программирование" за первые два семестра

Выполнение тестов производится с помощью Makefile. Все тесты, используемые в

Тесты к курсу «Программирование» - II семестр

Тесты к курсу «Программирование» - I семестр

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

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. Программа не должна «вылетать» с исключениями (как стандартными, так и добавленными).

Модификации

• Базовая
  • Класс ExpressionParser должен реализовывать интерфейс Parser
  • Классы CheckedAdd, CheckedSubtract, CheckedMultiply, CheckedDivide и CheckedNegate должны реализовывать интерфейс TripleExpression
  • Нельзя использовать типы long и double
  • Нельзя использовать методы классов Math и StrictMath
• Простая
  • Дополнительно реализовать унарные операции:
    • log2 — логарифм по уснованию 2, log2 10 равно 3;
    • pow2 — два в степени, pow2 4 равно 16.
• Простая
  • Дополнительно реализовать унарные операции:
    • abs — модуль числа, abs -5 равно 5;
    • sqrt — квадратный корень, sqrt 24 равно 4.
• Сложная
  • Реализовать операции простой модификации.
  • Дополнительно реализовать бинарные операции (минимальный приоритет):
    • min — минимум, 2 min 3 равно 2;
    • max — максимум, 2 max 3 равно 3.

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

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

            x * (x - 2)*x + 1
   

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

3. Приоритет операторов, начиная с наивысшего

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

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

Модификации

• Базовая
  • Класс ExpressionParser должен реализовывать интерфейс Parser
  • Результат разбора должен реализовывать интерфейс TripleExpression
• Простая
  • Дополнительно реализовать бинарные операции:
    • << — сдвиг влево, минимальный приоритет (1 << 5 + 3 равно 1 << (5 + 3) равно 256);
    • >> — сдвиг вправо, минимальный приоритет (1024 >> 5 + 3 равно 1024 >> (5 + 3) равно 4);
• Сложная
  • Дополнительно реализовать унарные операции (приоритет как у унарного минуса):
    • Дополнительно реализовать бинарные операции:
    • & — побитное И, приоритет меньше чем у + (6 & 1 + 2 равно 6 & (1 + 2) равно 2);
    • ^ — побитный XOR, приоритет меньше чем у & (6 ^ 1 + 2 равно 6 ^ (1 + 2) равно 5);
    • | — побитное ИЛИ, приоритет меньше чем у ^ (6 | 1 + 2 равно 6 | (1 + 2) равно 7);
    • ~ — побитное отрицание, ~-5 равно 4;
    • count — число установленных битов, count -5 равно 31.
• 39 группа
  • Дополнительно реализовать операции из простой и сложной модификации.

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

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

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

3. При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра методу evaluate (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7.
4. Для тестирования программы должен быть создан класс Main, который вычисляет значение выражения x2−2x+1, для x, заданного в командной строке.
5. При выполнение задания следует обратить внимание на:
   • Выделение общего интерфейса создаваемых классов.
   • Выделение абстрактного базового класса для бинарных операций. Модификации

• Базовая
  • Реализовать интерфейс Expression
• Простая
  • Реализовать интерфейс DoubleExpression
• Сложная
  • Реализовать интерфейсы DoubleExpression и TripleExpression

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

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

Модификации

• Базовая
• Простая
  • Добавить в интерфейс очереди и реализовать метод toArray, возвращающий массив, содержащий элементы, лежащие в очереди в порядке от головы к хвосту
  • Исходная очередь должна оставаться неизменной
  • Дублирования кода быть не должно
• Сложная
  • Добавить в интерфейс очереди и реализовать методы
    • filter(predicate) – создать очередь, содержащую элементы, удовлетворяющие предикату
    • map(function) – создать очередь, содержащую результаты применения функции
  • Исходная очередь должна остаться неизменной
  • Тип возвращаемой очереди должен соответствовать типу исходной очереди
  • Взаимный порядок элементов должен сохраняться
  • Дублирования кода быть не должно

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

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

Модификации

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

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

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

Модификации

• Базовая
  • Класс BinarySearch должен находиться в пакете search
• Простая
  • Если в массиве a отсутствует элемент, равный x, то требуется вывести индекс вставки в формате, определенном в Arrays.binarySearch.
  • Класс должен иметь имя BinarySearchMissing
• Сложная
  • Требуется вывести два числа: начало и длину диапазона элементов, равных x. Если таких элементов нет, то следует вывести пустой диапазон, у которого левая граница совпадает с местом вставки элемента x.
  • Не допускается использование типов long и BigInteger.
  • Класс должен иметь имя BinarySearchSpan

Домашнее задание 6. Подсчет слов++

• Для всех групп нужно использовать самописный Scanner
• Группам 36-37 можно использовать по символьное чтение
• Группам 38-39 нужно использовать побайтовое считывание

Модификации

• LineIndex
  • В выходном файле слова должны быть упорядочены в лексикографическом порядке
  • Вместо номеров вхождений во всем файле надо указывать <номер строки>:<номер в строке>
  • Класс должен иметь имя WordStatLineIndex

1. Разработайте класс WordStatIndex, который будет подсчитывать статистику встречаемости слов во входном файле.
2. Словом называется неперывная последовательность букв, апострофов и тире (Unicode category Punctuation, Dash). Для подсчета статистики, слова приводятся к нижнему регистру.
3. Выходной файл должен содержать все различные слова, встречающиеся во входном файле, в порядке их появения. Для каждого слова должна быть выведена одна строка, содежащая слово, число его вхождений во входной файл и номера вхождений этого слова среди всех слов во входном файле.
4. Имена входного и выходного файла задаются в качестве аргументов командной строки. Кодировка файлов: UTF-8.
5. Программа должна работать за линейное от размера входного файлам время.
6. Для реализации программы используйте Collections Framework.
7. Примеры работы программы:

Входной файл:
    To be, or not to be, that is the question:
Выходной файл:
    to 2 1 5
    be 2 2 6
    or 1 3
    not 1 4
    that 1 7
    is 1 8
    the 1 9
    question 1 10
Входной файл:
    Monday's child is fair of face.
    Tuesday's child is full of grace.
Выходной файл:
    monday's 1 1
    child 2 2 8
    is 2 3 9
    fair 1 4
    of 2 5 11
    face 1 6
    tuesday's 1 7
    full 1 10
    grace 1 12
Входной файл:
    Шалтай-Болтай
    Сидел на стене.
    Шалтай-Болтай
    Свалился во сне.
Выходной файл:
    шалтай-болтай 2 1 5
    сидел 1 2
    на 1 3
    стене 1 4
    свалился 1 6
    во 1 7
    сне 1 8

Домашнее задание 5. Быстрый реверс

• Для групп 36-39 надо написать Scanner используя побайтовое считывание, то есть нельзя использовать BufferedReader и аналоги!
• Для групп 38-39 запрешено использовать регулярные выражения, функцию split, класс StringTokenizer и аналоги.

Модификации

• Минимум
  • Рассмотрим входные данные как (не полностью определенную) матрицу, вместо каждого числа выведите минимум из чисел в его столбце и строке.
  • Сравнить время работы вашего сканера и встроенного в java
  • Класс должен иметь имя ReverseMin
• Сумма
  • Рассмотрим входные данные как (не полностью определенную) матрицу, вместо каждого числа выведите сумму чисел в его столбце и строке.
  • Класс должен иметь имя ReverseSum

1. Реализуйте свой аналог класса Scanner. Разработайте класс Reverse, читающий числа из стандартного входа, и выводящий их на стандартный вывод в обратном порядке.
2. Примените разработанный Scanner для решения задания "Реверc".
3. Модифицируйте решени задания "Реверc" так, что бы оно работало за линейное время.

Домашнее задание 4. Подсчет слов

Модификации

• Words
  • В выходном файле слова должны быть упорядочены в лексикографическом порядке
  • Класс должен иметь имя WordStatWords

1. Разработайте класс WordStatInput, который будет подсчитывать статистику встречаемости слов во входном файле.
2. Словом называется неперывная последовательность букв, апострофов и тире (Unicode category Punctuation, Dash). Для подсчета статистики, слова приводятся к нижнему регистру.
3. Выходной файл должен содержать все различные слова, встречающиеся во входном файле, в порядке их появения. Для каждого слова должна быть выведена одна строка, содежащая слово и число его вхождений во входной файл.
4. Имена входного и выходного файла задаются в качестве аргументов командной строки. Кодировка файлов: UTF-8.
5. Примеры работы программы:

     Входной файл:
         To be, or not to be, that is the question:
     Выходной файл:
         to 2
         be 2
         or 1
         not 1
         that 1
         is 1
         the 1
         question 1
     Входной файл:
         Monday's child is fair of face.
         Tuesday's child is full of grace.
     Выходной файл:
         monday's 1
         child 2
         is 2
         fair 1
         of 2
         face 1
         tuesday's 1
         full 1
         grace 1
     Входной файл:
         Шалтай-Болтай
         Сидел на стене.
         Шалтай-Болтай
         Свалился во сне.
     Выходной файл:
         шалтай-болтай 2
         сидел 1
         на 1
         стене 1
         свалился 1
         во 1
         сне 1

Домашнее задание 3. Сумма чисел в файле

Модификации

• Abc
  • На вход подаются числа, представленные буквами. Нулю соответствует буква a, единице – b и так далее
  • Ввод регистронезависим
  • Класс должен иметь имя SumAbcFile
• Hex
  • На вход подаются десятичные и шестнадцатеричные числа
  • Шестнадцатеричные числа имеют префикс 0x
  • Ввод регистронезависим
  • Класс должен иметь имя SumHexFile

1. Разработайте класс SumFile, записывающий сумму чисел из входного файла в выходной файл.
2. Числа во входном файле разделены переводами строк и/или пробельными символами.
3. Имена входного и выходного файла задаются в качестве аргументов командной строки.
4. Примеры работы программы:

    Входной файл:
        1 2 3
    Выходной файл:
        6
    Входной файл:
        1 2 -3
    Выходной файл:
        0
    Входной файл:
        1 2
          3
    Выходной файл:
        6     

5. При выполнении задания можно считать что для представления входных данных и промежуточных результатов достаточен тип int.
6. В этом и последующих домашних заданиях, метод main не должен выбрасывать никаких исключений при любых (в том числе некорректных) входных данных.
7. В этом и последующих домашних заданиях, все ресурсы должны закрываться при любых (в том числе некорректных) входных данных.

Домашнее задание 2. Реверс

Модификации

• Транспозиция
  • Рассмотрим входные данные как (не полностью определенную) матрицу, выведите ее в транспонированном виде
  • Класс должен иметь имя ReverseTranspose
• Максимум
  • Рассмотрим входные данные как (не полностью определенную) матрицу, вместо каждого числа выведите максимум из чисел в его столбце и строке.
  • Класс должен иметь имя ReverseMax

1. Разработайте класс Reverse, читающий числа из стандартного входа, и выводящий их на стандартный вывод в обратном порядке.
2. В каждой строке входа содержится некоторое количество целых чисел (может быть 0). Числа разделены пробелами. Каждое число помещается в тип int.
3. Порядок строк в выходе должен быть обратным по сравнению с порядком строк во входе. Порядок чисел в каждой строки так же должен быть обратным к порядку чисел во входе.
4. Примеры работы программы:

    Вход:
        1 2
        3
    Выход:
        3
        2 1
    Вход:
        1
   
        2 -3
    Выход:
        -3 2
   
        1
   

Домашнее задание 1. Сумма чисел

• SumHex

  • Входные данные помещаются в тип int либо десятичные, либо шестнадцатиричное начинается с 0x
  • Класс должен иметь имя SumHex
  • Нельзя использоваться классы Long и BigInteger

• BigIntegerDigit

  • Входные данные помещаются в тип BigInteger
  • Класс должен иметь имя SumBigInteger
  • Числа имеют вид [знак]цифры

1. Разработайте класс Sum, который при запуске из командной строки будет складывать переданные в качестве аргументов целые числа и выводить их сумму на консоль.
2. Примеры запуска программы:

   java Sum 1 2 3
   	Результат: 6
   java Sum 1 2 -3
   	Результат: 0
   java Sum "1 2 3"
   	Результат: 6
   java Sum "1 2" " 3"
   	Результат: 6
   

   Аргументы могут содержать цифры и произвольные пробельные символы.
3. При выполнении задания можно считать что для представления входных данных и промежуточных результатов достаточен тип int.
4. При выполнении задания полезно ознакомиться с документацией к классам String и Integer.

Для того, чтобы протестировать исходную программу:

1. Скачайте откомпилированные тесты (SumTest.jar)
2. Откомпилируйте Sum.java
3. Проверьте, что создался Sum.class
4. В каталоге, в котором находится Sum.class выполните команду

      java -jar <путь к SumTest.jar>
   

   • Например, если SumTest.jar находится в текущем каталоге, выполните команду

       java -jar SumTest.jar