Skip to content

Vedernikov/itmo-java-2018

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

58 Commits
artifacts
artifacts
 
 
java
java
 
 
README.md
README.md
 
 

Repository files navigation

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

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

Модификации

  • Базовая
    • Класс 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. Разбор выражений рекомендуется производить методом рекурсивного спуска. Алгоритм должен работать за линейное время.

Модификации

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

Домашнее задание 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. Напишите тесты реализованным классам.

Модификации

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

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

Модификации

Домашнее задание 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

Исходный код тестов:

Откомпилированные тесты: WordStatIndexTest.jar

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

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

Модификации

  • Минимум
    • Рассмотрим входные данные как (не полностью определенную) матрицу, вместо каждого числа выведите минимум из чисел в его столбце и строке.
    • Сравнить время работы вашего сканера и встроенного в java
    • Класс должен иметь имя ReverseMin
    • Исходный код тестов
    • Откомпилированные тесты
  • Сумма
  1. Реализуйте свой аналог класса Scanner. Разработайте класс Reverse, читающий числа из стандартного входа, и выводящий их на стандартный вывод в обратном порядке.
  2. Примените разработанный Scanner для решения задания "Реверc".
  3. Модифицируйте решени задания "Реверc" так, что бы оно работало за линейное время. Исходный код тестов:

Откомпилированные тесты: ReverseFastTest.jar

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

Модификации

  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

Исходный код тестов:

Откомпилированные тесты: WordStatInputTest.jar

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

Модификации

  1. Разработайте класс SumFile, записывающий сумму чисел из входного файла в выходной файл.
  2. Числа во входном файле разделены переводами строк и/или пробельными символами.
  3. Имена входного и выходного файла задаются в качестве аргументов командной строки.
  4. Примеры работы программы:
    Входной файл:
        1 2 3
    Выходной файл:
        6
    Входной файл:
        1 2 -3
    Выходной файл:
        0
    Входной файл:
        1 2
          3
    Выходной файл:
        6
  1. При выполнении задания можно считать что для представления входных данных и промежуточных результатов достаточен тип int.
  2. В этом и последующих домашних заданиях, метод main не должен выбрасывать никаких исключений при любых (в том числе некорректных) входных данных.
  3. В этом и последующих домашних заданиях, все ресурсы должны закрываться при любых (в том числе некорректных) входных данных. Исходный код тестов:

Откомпилированные тесты: SumFileTest.jar

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

Модификации

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

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

     1

Исходный код тестов:

Откомпилированные тесты: ReverseTest.jar

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

  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

Исходный код тестов:

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

5 stars

Watchers

1 watching

Forks

4 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages