Домашние задания, контрольные работы, осень 2015, 144 группа

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

В табличке:
пусто - задачу не получал
? - задачу получал, но ещё не смотрел
0 - задача не зачтена
0.5 - в целом правильно, но надо кое-что поправить
1 - задача зачтена
- означает дополнительную задачу, которую делать не обязательно, потому что соответствующее ей домашнее задание сдано в срок
зелёным выделены работы, зачтённые полностью
задачи со звёздочкой - дополнительные, для тех, кто не сдал домашнее задание через две недели после того, как оно было выдано

Контрольные работы:

В табличке:
- - задачу не получал
0 - задача не зачтена
1, x - задача зачтена (1 - написана с первого раза, количество x-ов равно количеству переписываний)
На переписывании надо решить только незачтённые задачи, то есть, например, если решены две задачи из трёх, на переписывании надо решить одну, по теме, к которой относится незачтённая задача

Зачёт:

В табличке:
- - задачу не получал
0 - задача не зачтена
1, x - задача зачтена (1 - написана с первого раза, количество x-ов равно количеству переписываний)
На переписывании надо решить только незачтённые задачи, то есть, например, если решены две задачи из трёх, на переписывании надо решить одну, по теме, к которой относится незачтённая задача



Все сдаваемые задачи должны соответствовать стайлгайду, сопровождаться набором тестов (для типичного случая, ошибочного ввода и пограничных случаев) и комментариев (каждая функция в заголовочном файле должна иметь комментарий, поясняющий, что она делает, какие параметры принимает и что возвращает).

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

1. 10.09.2015

1. Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x + 1 за два умножения.
4. Написать программу нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения.
5. Дан массив целых чисел x[1]...x[m + n], рассматриваемый как соединение двух его отрезков: начала x[1] ... x[m] длины m и конца x[m + 1] ... x[m + n] длины n. Не используя дополнительных массивов, переставить начало и конец (обращением двух частей массива, а потом его самого).
6. Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних), подсчётом числа билетов с заданной суммой трёх цифр.
7. Написать программу проверки баланса скобок в исходной строке (т.е. число открывающих скобок равно числу закрывающих и выполняется правило вложенности скобок).
8. Заданы две строки: S и S1. Найти количество вхождений S1 в S как подстроки.
9. Написать программу, печатающую все простые числа, не превосходящие заданного числа.
10. Написать программу, считающую количество нулевых элементов в массиве.

2. 17.09.2015

1. Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.
2. Реализовать возведение в степень - в лоб и придумать, как быстрее, за О(log n)
3. Написать сортировки пузырьком и подсчётом
4. Написать программу, которая заполняет массив случайными значениями (с использованием функции rand из stdlib.h), потом преобразует его без использования дополнительных массивов так, что в начале массива будут элементы, меньшие первого, а в конце - большие первого. Программа должна работать за линейное время.

3. 24.09.2015

Визуализаторы для разных алгоритмов сортировки

1. Реализовать qsort, который для сортировки кусков массива размером меньше 10 использует сортировку вставкой.
2. Решить задачу с одной из лопатинских тренировок: получить с клавиатуры 2 числа, n и k (1 <= n <= 5000, 1 <= k <= 300000), сгенерировать массив из n чисел от 0 до 10^9, сгенерировать k целых чисел от 0 до 10^9 , для каждого из них проверить, содержится ли оно в массиве. Лобовое решение на тренировке не укладывалось во временные ограничения, так что здесь надо придумать алгоритм с временной сложностью O(n log n + k log n), или лучший.
3. Найти наиболее часто встречающийся элемент в массиве быстрее, чем за O(n^2).

4. 01.10.2015

Штука для перевода десятичных чисел во внутреннее представление

1. Ввести два числа, перевести в двоичное представление (в каком-либо из кодов) и напечатать, сложить, вывести сумму, перевести в десятичное, вывести результат в десятичном виде. Все сообщения писать по-русски, для этого будет полезна функция setlocale.
2. Переделать задачу 3 из прошлого задания так, чтобы сортировка была в отдельном модуле и читала входные данные из файла.
3. Написать программу, которая считает количество непустых строк в исходном файле. Строка считается пустой, если состоит только из пробелов и табуляций (символ \t), или в ней нет символов вообще.

5. 08.10.2015

Презентация с пары

Презентация с дополнительной пары про ООП
Необязательная задача про ООП:

1. Описать интерфейс (абстрактный класс, у которого все методы абстрактные) для списка, поддерживающий как минимум операции добавления в произвольную позицию (задающуюся натуральным числом), получения элемента по заданной позиции, удаления элемента в заданной позиции, получения длины списка. Реализовать этот интерфейс в двух классах --- списке на основе массивов и списке на основе указателей. Написать основную программу, которая позволяет выполнять эти базовые операции в диалоговом режиме, при этом она должна работать со списком по интерфейсу. Сначала программа должна спросить у пользователя, какую реализацию списка он хочет. Конкретные реализации списков программа может вызывать напрямую только с одной целью --- для создания объекта нужного класса.

6. 15.10.2015

Презентация с пары

1. Написать программу - телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции:
   0 - выйти
   1 - добавить запись (имя и телефон)
   2 - найти телефон по имени
   3 - найти имя по телефону
   4 - сохранить текущие данные в файл
   При запуске программа должна читать данные из файла, если файла нет - начинать с пустой базы номеров. Размер базы ограничен сотней записей, так что для внутреннего представления можно использовать массив. Формат представления данных в файле придумать самостоятельно.
2. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
   0 - выйти
   1 - добавить значение в сортированный список
   2 - удалить значение из списка
   3 - распечатать список
   Все операции должны сохранять сортированность. Начинаем с пустого списка. Надо использовать список на указателях.
3. "Считалочка" --- отряд из 41-го сикария, защищавший галилейскую крепость Массада, не пожелал сдаваться в плен блокировавшим его превосходящим силам римлян. Сикарии стали в круг и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. Самоубийство — тяжкий грех, но тот, кто в конце концов останется последним, должен будет его совершить. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам. В нашем случае участвует n воинов и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который должен будет остаться последним. Считать с помощью циклического списка.

7. 22.10.2015

1. Реализовать сортировку слиянием. Во входном файле последовательность записей "имя - номер телефона". Программа должна отсортировать эти записи либо по имени, либо по номеру телефона, в зависимости от выбора пользователя, и вывести результат на экран. Количество записей неизвестно, так что реализовывать списками на указателях.
2. Написать программу для вычисления арифметического выражения в постфиксной форме. С клавиатуры вводится последовательность цифр (для простоты) и операций +, -, *, /, представляющая выражение в постфиксной форме, должен выводиться результат вычисления. Например, на тесте 9 6 - 1 2 + * должно получиться 9.
3. Написать программу проверки баланса скобок в строке, скобки могут быть трёх видов: (), [], {}. Скобочная последовательность вида ({)} считается некорректной, ({}) - корректной.
4. Написать программу, преобразующую выражение из инфиксной формы в постфиксную. В выражении могут быть знаки +, -, *, /, скобки и цифры. Пример: (1 + 1) * 2 должно преобразовываться в 1 1 + 2 *. Алгоритм перевода предлагается найти самостоятельно (алгоритм "сортировочной станции" Э. Дейкстры).

Задачи 2, 3 и 4 решаются с помощью стека - его надо реализовать единожды в отдельном модуле, и использовать во всех этих задачах.

28.10.2015

Код с пары про стековый калькулятор в виде класса

8. 29.10.2015

Презентация с пары про git

1. Реализовать два варианта АТД "список": список на массиве и список на указателях, реализовать с помощью методов этого АТД сортировку слиянием, сделать так, чтобы можно было менять реализацию АТД, с которой работает сортировка, изменением всего нескольких строчек кода.
2. Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках.
3. По дереву разбора арифметического выражения вычислить его значение. Дерево разбора хранится в файле в виде (<операция> <операнд1> <операнд2>), где <операнд1> и <операнд2> сами могут быть деревьями, либо числами. Например, выражение (1 + 1) * 2 представляется в виде (* (+ 1 1) 2). Должны поддерживаться операции +, -, *, / и целые числа в качестве аргументов. Требуется построить дерево в явном виде, распечатать его (не обязательно так же, как в файле), и посчитать значение выражения обходом дерева. Может быть полезна функция ungetc (если не '(', возвращаем символ в поток и читаем число fscanf-ом). Можно считать, что входной файл корректен. Пример - по входному файлу (* (+ 1 1) 2) может печататься ( * ( + 1 1 ) 2 ) и выводиться 4.
4. Завести аккаунт с разумным именем на https://github.com, прислать его мне на почту и добавить меня в коллабораторы. Выложить туда уже зачтённые задачи, все незачтённые выложить в отдельные ветки и сделать пуллреквесты. Если в условии этой задачи есть незнакомые слова, посмотреть презентацию.

9. 05.11.2015

1. Посчитать частоты встречаемости слов в тексте с помощью хеш-таблицы. На входе файл с текстом, вывести на консоль все слова, встречающиеся в этом тексте с количеством раз, которое встречается каждое слово. Словом считается последовательность символов, разделённая пробелами, разные словоформы считаются разными словами. Хеш-таблицу реализовать в отдельном модуле, использующем модуль "Список".

10. 12.11.2015

1. Есть множество городов и дороги, связывающие эти города. Для каждой дороги задана её длина. Задача - распределить города между государствами по такому алгоритму: задаются k столиц каждого государства, далее по очереди каждому государству добавляется ближайший незанятый город, непосредственно связанный дорогой с каким-либо городом, уже принадлежащим государству (столицей или каким-либо городом, добавленным на одном из предыдущих шагов). Процесс продолжается до тех пор, пока все города не будут распределены. Граф дорог связный. Во входном файле: n - число городов и m - число дорог. Далее следуют сами дороги в формате: i j len, i и j - номера городов, len - длина дороги. Далее задано число k - число столиц, далее - k чисел - номера столиц. Надо вывести на консоль номера государств и списки городов, принадлежащих государствам.

Доклады:

1. Алгоритмы Прима и Краскала - Альберт Мухаммадиев
2. Алгоритм Кнута-Морриса-Пратта - Артур Нагаев
   презентация
3. Алгоритм Рабина-Карпа - Денис Травин
4. Алгоритм Бойера-Мура - Юлия Бережнова
   презентация

11. 20.11.2015

Презентация с пары про парадигмы программирования
Презентация с дополнительной пары про шаблоны в C++

12. 26.11.2015

Код с пары про граф и алгоритм Флойда

1. Реализовать поиск подстроки любым из рассмотренных алгоритмов. Из файла читается текст, с консоли - строка, программа должна выводить на консоль позицию первого вхождения введённой строки в файле.
2. По данному неориентированному графу построить минимальное остовное дерево одним из рассмотренных алгоритмов. В файле задаётся матрица смежности, программа должна вывести на консоль минимальное остовное дерево в каком-либо представлении.

13. 04.12.2015

Презентация про лексический анализ

1. Реализовать с помощью switch по состоянию лексический анализатор, проверяющий, является ли введённая последовательность символов вещественным числом (вещественное число задаётся регулярным выражением digit+ (. digit+)? (E(+ | -)? digit+)?, где digit - [0..9]).
2. С помощью ДКА с явной таблицей состояний вывести на консоль все комментарии С++ вида /* комментарий */ из входного файла (вместе с символами "/* */").

Код с дополнительной пары про шаблонный стековый калькулятор над произвольным полем, использующий разные реализации стека