Домашние задания, контрольные работы, осень 2015, 144 группа
Табличка с результатами домашних заданий и контрольных работ, условия заданий
Домашние задания:
В табличке:пусто - задачу не получал
? - задачу получал, но ещё не смотрел
0 - задача не зачтена
0.5 - в целом правильно, но надо кое-что поправить
1 - задача зачтена
- означает дополнительную задачу, которую делать не обязательно, потому что соответствующее ей домашнее задание сдано в срок
зелёным выделены работы, зачтённые полностью
задачи со звёздочкой - дополнительные, для тех, кто не сдал домашнее задание через две недели после того, как оно было выдано
Контрольные работы:
В табличке:- - задачу не получал
0 - задача не зачтена
1, x - задача зачтена (1 - написана с первого раза, количество x-ов равно количеству переписываний)
На переписывании надо решить только незачтённые задачи, то есть, например, если решены две задачи из трёх, на переписывании надо решить одну, по теме, к которой относится незачтённая задача
Зачёт:
В табличке:- - задачу не получал
0 - задача не зачтена
1, x - задача зачтена (1 - написана с первого раза, количество x-ов равно количеству переписываний)
На переписывании надо решить только незачтённые задачи, то есть, например, если решены две задачи из трёх, на переписывании надо решить одну, по теме, к которой относится незачтённая задача
Все сдаваемые задачи должны соответствовать стайлгайду, сопровождаться набором тестов (для типичного случая, ошибочного ввода и пограничных случаев) и комментариев (каждая функция в заголовочном файле должна иметь комментарий, поясняющий, что она делает, какие параметры принимает и что возвращает).
Условия задач:
1. 10.09.2015
- Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x + 1 за два умножения.
- Написать программу нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения.
- Дан массив целых чисел x[1]...x[m + n], рассматриваемый как соединение двух его отрезков: начала x[1] ... x[m] длины m и конца x[m + 1] ... x[m + n] длины n. Не используя дополнительных массивов, переставить начало и конец (обращением двух частей массива, а потом его самого).
- Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних), подсчётом числа билетов с заданной суммой трёх цифр.
- Написать программу проверки баланса скобок в исходной строке (т.е. число открывающих скобок равно числу закрывающих и выполняется правило вложенности скобок).
- Заданы две строки: S и S1. Найти количество вхождений S1 в S как подстроки.
- Написать программу, печатающую все простые числа, не превосходящие заданного числа.
- Написать программу, считающую количество нулевых элементов в массиве.
2. 17.09.2015
- Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.
- Реализовать возведение в степень - в лоб и придумать, как быстрее, за О(log n)
- Написать сортировки пузырьком и подсчётом
- Написать программу, которая заполняет массив случайными значениями (с использованием функции rand из stdlib.h), потом преобразует его без использования дополнительных массивов так, что в начале массива будут элементы, меньшие первого, а в конце - большие первого. Программа должна работать за линейное время.
3. 24.09.2015
Визуализаторы для разных алгоритмов сортировки- Реализовать qsort, который для сортировки кусков массива размером меньше 10 использует сортировку вставкой.
- Решить задачу с одной из лопатинских тренировок: получить с клавиатуры 2 числа, n и k (1 <= n <= 5000, 1 <= k <= 300000), сгенерировать массив из n чисел от 0 до 10^9, сгенерировать k целых чисел от 0 до 10^9 , для каждого из них проверить, содержится ли оно в массиве. Лобовое решение на тренировке не укладывалось во временные ограничения, так что здесь надо придумать алгоритм с временной сложностью O(n log n + k log n), или лучший.
- Найти наиболее часто встречающийся элемент в массиве быстрее, чем за O(n^2).
4. 01.10.2015
Штука для перевода десятичных чисел во внутреннее представление- Ввести два числа, перевести в двоичное представление (в каком-либо из кодов) и напечатать, сложить, вывести сумму, перевести в десятичное, вывести результат в десятичном виде. Все сообщения писать по-русски, для этого будет полезна функция setlocale.
- Переделать задачу 3 из прошлого задания так, чтобы сортировка была в отдельном модуле и читала входные данные из файла.
- Написать программу, которая считает количество непустых строк в исходном файле. Строка считается пустой, если состоит только из пробелов и табуляций (символ \t), или в ней нет символов вообще.
5. 08.10.2015
Презентация с парыПрезентация с дополнительной пары про ООП
Необязательная задача про ООП:
- Описать интерфейс (абстрактный класс, у которого все методы абстрактные) для списка, поддерживающий как минимум операции добавления в произвольную позицию (задающуюся натуральным числом), получения элемента по заданной позиции, удаления элемента в заданной позиции, получения длины списка. Реализовать этот интерфейс в двух классах --- списке на основе массивов и списке на основе указателей. Написать основную программу, которая позволяет выполнять эти базовые операции в диалоговом режиме, при этом она должна работать со списком по интерфейсу. Сначала программа должна спросить у пользователя, какую реализацию списка он хочет. Конкретные реализации списков программа может вызывать напрямую только с одной целью --- для создания объекта нужного класса.
6. 15.10.2015
Презентация с пары- Написать программу - телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции:
0 - выйти
1 - добавить запись (имя и телефон)
2 - найти телефон по имени
3 - найти имя по телефону
4 - сохранить текущие данные в файл
При запуске программа должна читать данные из файла, если файла нет - начинать с пустой базы номеров. Размер базы ограничен сотней записей, так что для внутреннего представления можно использовать массив. Формат представления данных в файле придумать самостоятельно. - Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
0 - выйти
1 - добавить значение в сортированный список
2 - удалить значение из списка
3 - распечатать список
Все операции должны сохранять сортированность. Начинаем с пустого списка. Надо использовать список на указателях. - "Считалочка" --- отряд из 41-го сикария, защищавший галилейскую крепость Массада, не пожелал сдаваться в плен блокировавшим его превосходящим силам римлян. Сикарии стали в круг и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. Самоубийство — тяжкий грех, но тот, кто в конце концов останется последним, должен будет его совершить. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам. В нашем случае участвует n воинов и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который должен будет остаться последним. Считать с помощью циклического списка.
7. 22.10.2015
- Реализовать сортировку слиянием. Во входном файле последовательность записей "имя - номер телефона". Программа должна отсортировать эти записи либо по имени, либо по номеру телефона, в зависимости от выбора пользователя, и вывести результат на экран. Количество записей неизвестно, так что реализовывать списками на указателях.
- Написать программу для вычисления арифметического выражения в постфиксной форме. С клавиатуры вводится последовательность цифр (для простоты) и операций +, -, *, /, представляющая выражение в постфиксной форме, должен выводиться результат вычисления. Например, на тесте 9 6 - 1 2 + * должно получиться 9.
- Написать программу проверки баланса скобок в строке, скобки могут быть трёх видов: (), [], {}. Скобочная последовательность вида ({)} считается некорректной, ({}) - корректной.
- Написать программу, преобразующую выражение из инфиксной формы в постфиксную. В выражении могут быть знаки +, -, *, /, скобки и цифры. Пример: (1 + 1) * 2 должно преобразовываться в 1 1 + 2 *. Алгоритм перевода предлагается найти самостоятельно (алгоритм "сортировочной станции" Э. Дейкстры).
28.10.2015
Код с пары про стековый калькулятор в виде класса8. 29.10.2015
Презентация с пары про git- Реализовать два варианта АТД "список": список на массиве и список на указателях, реализовать с помощью методов этого АТД сортировку слиянием, сделать так, чтобы можно было менять реализацию АТД, с которой работает сортировка, изменением всего нескольких строчек кода.
- Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках.
- По дереву разбора арифметического выражения вычислить его значение. Дерево разбора хранится в файле в виде (<операция> <операнд1> <операнд2>), где <операнд1> и <операнд2> сами могут быть деревьями, либо числами. Например, выражение (1 + 1) * 2 представляется в виде (* (+ 1 1) 2). Должны поддерживаться операции +, -, *, / и целые числа в качестве аргументов. Требуется построить дерево в явном виде, распечатать его (не обязательно так же, как в файле), и посчитать значение выражения обходом дерева. Может быть полезна функция ungetc (если не '(', возвращаем символ в поток и читаем число fscanf-ом). Можно считать, что входной файл корректен. Пример - по входному файлу (* (+ 1 1) 2) может печататься ( * ( + 1 1 ) 2 ) и выводиться 4.
- Завести аккаунт с разумным именем на https://github.com, прислать его мне на почту и добавить меня в коллабораторы. Выложить туда уже зачтённые задачи, все незачтённые выложить в отдельные ветки и сделать пуллреквесты. Если в условии этой задачи есть незнакомые слова, посмотреть презентацию.
9. 05.11.2015
- Посчитать частоты встречаемости слов в тексте с помощью хеш-таблицы. На входе файл с текстом, вывести на консоль все слова, встречающиеся в этом тексте с количеством раз, которое встречается каждое слово. Словом считается последовательность символов, разделённая пробелами, разные словоформы считаются разными словами. Хеш-таблицу реализовать в отдельном модуле, использующем модуль "Список".
10. 12.11.2015
- Есть множество городов и дороги, связывающие эти города. Для каждой дороги задана её длина. Задача - распределить города между государствами по такому алгоритму: задаются k столиц каждого государства, далее по очереди каждому государству добавляется ближайший незанятый город, непосредственно связанный дорогой с каким-либо городом, уже принадлежащим государству (столицей или каким-либо городом, добавленным на одном из предыдущих шагов). Процесс продолжается до тех пор, пока все города не будут распределены. Граф дорог связный. Во входном файле: n - число городов и m - число дорог. Далее следуют сами дороги в формате: i j len, i и j - номера городов, len - длина дороги. Далее задано число k - число столиц, далее - k чисел - номера столиц. Надо вывести на консоль номера государств и списки городов, принадлежащих государствам.
- Алгоритмы Прима и Краскала - Альберт Мухаммадиев
- Алгоритм Кнута-Морриса-Пратта - Артур Нагаев
презентация - Алгоритм Рабина-Карпа - Денис Травин
- Алгоритм Бойера-Мура - Юлия Бережнова
презентация
11. 20.11.2015
Презентация с пары про парадигмы программированияПрезентация с дополнительной пары про шаблоны в C++
12. 26.11.2015
Код с пары про граф и алгоритм Флойда- Реализовать поиск подстроки любым из рассмотренных алгоритмов. Из файла читается текст, с консоли - строка, программа должна выводить на консоль позицию первого вхождения введённой строки в файле.
- По данному неориентированному графу построить минимальное остовное дерево одним из рассмотренных алгоритмов. В файле задаётся матрица смежности, программа должна вывести на консоль минимальное остовное дерево в каком-либо представлении.
13. 04.12.2015
Презентация про лексический анализ- Реализовать с помощью switch по состоянию лексический анализатор, проверяющий, является ли введённая последовательность символов вещественным числом (вещественное число задаётся регулярным выражением digit+ (. digit+)? (E(+ | -)? digit+)?, где digit - [0..9]).
- С помощью ДКА с явной таблицей состояний вывести на консоль все комментарии С++ вида /* комментарий */ из входного файла (вместе с символами "/* */").
Код с дополнительной пары про шаблонный стековый калькулятор над произвольным полем, использующий разные реализации стека