Программирование

20.Б10-мм группа

Тимофей Брыксин

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 Тест 2 №8 №9 Тест 3
20 1 2 3 Лексер Парсер 1 2 3
Биктагиров Булат 2
Волков Александр 1
Дегтярев Иван 7
Есин Максим
Искандяров Ринат 3
Касацкий Всеслав 2
Кропачева Алена 2
Куковеров Егор 1
Мищенко Станислав 2
Филимонов Игорь

Задачи

Тест 3. 15.12.20
  1. В массиве целых чисел найти число, сумма цифр которого была бы наибольшей. Если таких чисел несколько, вывести на экран все эти числа.

  2. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции с двусвязным списком:
    0 - выйти
    1 - заполнить список случайными значениями (размер списка и диапазон значений задаются с консоли)
    2 - развернуть список
    3 - распечатать список

  3. Реализовать конечный автомат, принимающий строки, задаваемые следующим регулярным выражением: [A-Za-z] ([A-Za-z] | [0-9] | _ ) *

Домашняя работа 9. 06.12.20
  1. Парсер

    Реализовать синтаксический анализатор, разбирающий арифметические выражения методом рекурсивного спуска. Входной поток составляют числа, разбираемые лексическим анализатором из прошлого задания, и знаки операций {+, -, /, *}. Функция main должна считывать с консоли выражение и проверять, удовлетворяет ли оно грамматике. Считайте, что на токены подаются на вход разделённые пробелом. Токен может состоять из нескольких символов.
    Примеры:
    1 + 20 * 300 -> valid
    1 + 20 * a -> invalid

    Задания на дополнительные баллы:
    1. Научиться отрисовывать дерево разбора. Формат вывода любой, например, для выражения 1 + 20 * 300 можно отрисовать как

    +
    ....*
    ........20
    ........300
    ....1

    2. Инкапсулируйте функцию для каждого нетерминала в АТД "Nonterminal". Для каждого нетерминала создаётся структура по заданным продукциям. После этого метод рекурсивного спуска легко инкапсулировать, при его инициализации достаточно указать на стартовый "Nonterminal".

    Баллы: 2 балла (+1 за отрисовку, +2 за АТД)
    Мягкий дедлайн: 20.12.20
    Жёсткий дедлайн: 28.12.20
    Reviewer: SokolovYaroslav

Домашняя работа 8. 22.11.20
  1. Лексер

    Реализовать лексический анализатор, проверяющий, является ли введённая последовательность символов вещественным числом (вещественное число задаётся регулярным выражением (+ | -)? digit+ (. digit+)? (E(+ | -)? digit+)?, где digit -- [0..9]).

    Баллы: 2 балла
    Мягкий дедлайн: 06.12.20
    Жёсткий дедлайн: 20.12.20
    Reviewer: nbirillo

Тест 2. 10.11.20
  1. Дан текстовый файл. Посчитать число появлений в нем каждой строчной буквы латинского алфавита и создать новый файл, строки которого имеют вид "a -- n", где a -- буква, а n -- число повторений этой буквы в файле. Буквы, отсутствующие в тексте, в файл не включать. Строки упорядочить по возрастанию кодов букв.

  2. Дан ориентированный граф в виде матрицы инцидентности. Написать функцию поиска всех вершин графа, недостижимых из заданной вершины.

Домашняя работа 7. 05.11.20
Слайды
Конспект
  1. Получив домашнее задание по программированию, группа студентов приступила к решению задач. Три студента с номерами 1, 2 и 3 честно сделали все задание самостоятельно, другие решили списать с кого-нибудь, кто уже имеет готовое решение — либо решенное самостоятельно, либо уже списанное с другого. При проверке выяснилось, что некоторых студентов следует немедленно отчислить, т.к. они не только не написали решение сами, но и поленились списать. Задача: Определить, какой студент какое решение сдавал, и кого надо отчислить. На входе: количество студентов и список пар чисел, где первое число — номер студента, второе — номер того, с кого было списано решение. Для студентов, которые ничего не сдали, второе значение будет -1. Требуется вывести список пар чисел, где первое число — номер студента, второе — 1, 2 или 3 — сданный вариант.

    Баллы: 2 балла
    Мягкий дедлайн: 25.11.20
    Жесткий дедлайн: 06.12.20
    Reviewer: SpirinEgor

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

    Баллы: 3 балла
    Мягкий дедлайн: 25.11.20
    Жесткий дедлайн: 06.12.20
    Reviewer: SpirinEgor

Домашняя работа 6. 30.10.20
Слайды
Конспект
  1. Hash table

    Реализовать структуру данных hash-таблица (разрешение коллизий методом открытой адресации, квадратичная последовательность проб).
    По данному тексту (читается из файла, не ограничен по размеру) посчитать число использований каждого слова. В конце работы вывести load factor, среднее и максимальное количество проб при добавлении элемента (и сами эти значения с максимальным количеством проб), общее число добавленных слов, число пустых ячеек таблицы. А также топ-10 самых встречаемых слов.

    Под словом понимается последовательность символов a...z без учёта регистра. Знаки препинания и другие символы необходимо игнорировать.

    К pull request приложите файл, на котором вы тестировали работу алгоритма. Условие на дополнительный балл: сделайте реализацию независимой от hash-функции и пробирования. Другими словами, реализация hash-таблицы ничего не должна знать про используемую hash-функцию и какой способ пробирования использования.

    Баллы: 3 балла (+2 балла дополнительно)
    Мягкий дедлайн: 15.11.20
    Жёсткий дедлайн: 29.11.20
    Reviewer: nbirillo

Домашняя работа 5. 23.10.20
Слайды (деревья поиска)
  1. BST

    Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме:
    1. Добавлять значения целого типа в множество
    2. Удалять значения
    3. Проверять, принадлежит ли значение множеству
    4. Печатать текущие элементы множества в возрастающем и убывающем порядках, а также в формате (a b c), где a — значение в узле, а b и c — аналогичные представления поддеревьев правого и левого потомка. Пример: "(5 (2 null null) (10 null (12 null null)))".

    Баллы: 2 балла
    Мягкий дедлайн: 08.11.20
    Жёсткий дедлайн: 22.11.20
    Reviewer: SokolovYaroslav

  2. AVL

    Реализовать АТД "множество" на основе AVL-дерева. Вся функциональность должна повторять предыдущее задание. Если сможете переиспользовать код для BST, то +1 балл. Переиспользование -- для AVL-дерева используется реализация BST + какая-то дополнительная логика по балансировке. Например, BSTNode и AVLTreeNode могут быть одним и тем же простым TreeNode (то есть нет необходимости заново объявлять структуру вершины).

    Баллы: 2 балла (+1 за переиспользование)
    Мягкий дедлайн: 08.11.20
    Жёсткий дедлайн: 22.11.20
    Reviewer: SokolovYaroslav

Тест 1. 13.10.20
  1. Реализовать структуру “Вектор“. Определить операции над ней, позволяющие находить скалярное произведение векторов, длину вектора, а также складывать и вычитать друг с другом.

Домашняя работа 4. 09.10.20
Слайды (представление данных)
Конспект (представление данных)
  1. Стек

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

    Баллы: 3 балла
    Мягкий дедлайн: 18.10.20
    Жёсткий дедлайн: 01.11.20

  2. По содержимому памяти вывести значение типа double в экспоненциальной форме: sm*q{Sp}, где s — знак мантиссы, m — мантисса, q — основание системы счисления, S — знак порядка, p — порядок числа. Примеры допустимого вывода:

    Enter a number: -2.5
    Result: -1.25*2^{1}
    Enter a number: 12312.323
    Result: +1.5029691162109375384*2^{13}

    Баллы: 1 балл
    Мягкий дедлайн: 18.10.20
    Жёсткий дедлайн: 01.11.20

  3. Ввести два числа, перевести в двоичное представление (в каком-либо из кодов) и в этом двоичном виде напечатать, сложить, вывести сумму в двоичном и десятичном виде (суммировать двоичные числа).

    Баллы: 1 балл
    Мягкий дедлайн: 18.10.20
    Жёсткий дедлайн: 01.11.20

Домашняя работа 3. 25.09.20
Слайды
Конспект
  1. Лист

    Реализовать АТД "Лист". Необходимо реализовать интерфейс, который поддерживает следующие операции:

    ListElement tail(List *list);
    ListElement head(List *list);
    bool insert(ListElement *value, int position, List *list);
    int locate(ListElement *value, List *list);
    ListElement retrieve(int position, List *list);
    bool delete(int position, List *list);

    Не забудьте про вспомогательные функции, которые нужны для удаления и создания листа. Весь код необходимо разместить в library, например, в list.h и list.c. Для демонстрации работоспособности в main напишите пример работы с листом (как делали на паре).

    Баллы: 3 балла
    Мягкий дедлайн: 11.10.20
    Жёсткий дедлайн: 25.10.20

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

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

    Баллы: 2 балла
    Мягкий дедлайн: 11.10.20
    Жёсткий дедлайн: 25.10.20

Домашняя работа 2. 17.09.20
Слайды
  1. Напечатать все представления натурального числа N суммой натуральных слагаемых. Перестановка слагаемых нового способа не дает.

    Баллы: 1 балл
    Мягкий дедлайн: 01.10.20
    Жёсткий дедлайн: 15.10.20

  2. Реализовать консольную игру "Быки и коровы" (http://goo.gl/J1LKti).

    Баллы: 1 балл
    Мягкий дедлайн: 01.10.20
    Жёсткий дедлайн: 15.10.20

  3. Дан массив размером n, в нём есть нули, надо их все переместить в конец, при этом не создавая новый массив.

    Баллы: 1 балл
    Мягкий дедлайн: 01.10.20
    Жёсткий дедлайн: 15.10.20

  4. Написать программу, которая переставляет цифры натурального числа таким образом, чтобы образовалось наименьшее число, записанное этими же цифрами.

    Баллы: 1 балл
    Мягкий дедлайн: 01.10.20
    Жёсткий дедлайн: 15.10.20

  5. Реализовать подсчет факториала (рекурсивно и итеративно).

    Баллы: 1 балл
    Мягкий дедлайн: 01.10.20
    Жёсткий дедлайн: 15.10.20

Домашняя работа 1. 10.09.20
Слайды
Style guide
  1. Дан массив размерностью n x n, n – нечетное число. Вывести элементы массива при обходе его по спирали, начиная с центра.

    Баллы: 1 балл
    Мягкий дедлайн: 24.09.20
    Жёсткий дедлайн: 08.10.20

  2. Дан массив целых чисел x[1]...x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]...x[m] длины m и конца x[m+1]...x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец.

    Баллы: 1 балл
    Мягкий дедлайн: 24.09.20
    Жёсткий дедлайн: 08.10.20

  3. Заданы две строки: s1 и s2. Найти количество вхождений s2 в s1 как подстроки.

    Баллы: 1 балл
    Мягкий дедлайн: 24.09.20
    Жёсткий дедлайн: 08.10.20

  4. Написать программу, печатающую все простые числа, не превосходящие заданного числа.

    Баллы: 1 балл
    Мягкий дедлайн: 24.09.20
    Жёсткий дедлайн: 08.10.20

  5. Найдите максимальный элемент массива, встречающийся более одного раза (массив неупорядоченный).

    Баллы: 1 балл
    Мягкий дедлайн: 24.09.20
    Жёсткий дедлайн: 08.10.20

© 2014-2021 HwProj