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

144 группа

Юрий Литвинов

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 №8 №9 №10 Тест 2 №11
382 1 2 3 4 5 6 7 8 1 2 3 4 1 2 3 4 1 2 3 1 2 3 1 2 1 2 3 4 1 2 1 1 2 1 1 2 Доклады 2 3
Бадмаев Чингис 39
Бочаров Глеб 39
Виктория Фомина 10
Вологин Дмитрий 21
Донина Дарья 17
Дорожкин Сергей 20
Егорова Лада 18
Зиннатулин Тимур 19
Катричко Ульяна 17
Ким Юния 14
Ключников Даниил 26
Костин Павел 27
Липаев Савелий 8
Мамро Никита 13
Мирошникова Мария 19
Паршин Максим 8
Соболевская Надежда 10
Терентьев Даниил 39
Хованов Виктор 18

Задачи

Домашняя работа 11. 07.12.18
Обзор парадигм программирования, часть 2 (слайды)
Алгоритм Кнута-Морриса-Пратта
Алгоритмы Прима и Краскала, СНМ
Статья про алгоритм A*
Статья про алгоритм A* без анимации
  1. Доклады
  2. Реализовать поиск подстроки любым из рассмотренных алгоритмов. Из файла читается текст, с консоли - строка, программа должна выводить на консоль позицию первого вхождения введённой строки в файле.

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

Тест 2. 30.11.18
Обзор парадигм программирования (слайды)
  1. Даны числа a и b. За один просмотр файла f, элементами которого являются целые числа, и без использования дополнительных файлов переписать его элементы в файл g так, чтобы первоначально были записаны все числа, меньше заданного a, затем все числа из отрезка [a,b], затем все остальные. Взаимный порядок в каждой из групп должен быть сохранен, предположений о количестве элементов делать нельзя (пользоваться контейнерами из стандартной библиотеки – тоже).

  2. Проверить список на симметричность. В файле даны натуральные числа, построить по ним список и определить, симметричен ли он. Например, список из 1 2 3 2 1 симметричен, 1 2 3 4 2 1 - нет.

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

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

  2. Написать мейкфайл и собрать какую-либо из задач д/з 6 в консоли с помощью утилиты make (или nmake или mingw32-make), выложить мейкфайл и приложить скриншот успешной сборки.

Домашняя работа 8. 09.11.18
Самобалансирующиеся деревья (слайды)
  1. Реализовать ассоциативный массив с ключами и значениями типа string на основе АВЛ-дерева. Должны поддерживаться следующие операции:

    • Добавить значение по заданному ключу в ассоциативный массив. Если такой ключ уже есть, значение заменяется на новое.
    • Получить значение по заданному ключу из ассоциативного массива. Если такого ключа нет, возвращается пустая строка.
    • Проверить наличие заданного ключа.
    • Удалить заданный ключ и связанное с ним значение из ассоциативного массива. Если такого ключа нет, функция ничего не делает.

    Ассоциативный массив должен быть реализован отдельным модулем.

Домашняя работа 7. 02.11.18
Деревья (слайды)
  1. Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках.

  2. По дереву разбора арифметического выражения вычислить его значение. Дерево разбора хранится в файле в виде (<операция> <операнд1> <операнд2>), где <операнд1> и <операнд2> сами могут быть деревьями, либо числами. Например, выражение (1 + 1) * 2 представляется в виде (* (+ 1 1) 2). Должны поддерживаться операции +, -, *, / и целые числа в качестве аргументов. Требуется построить дерево в явном виде, распечатать его (не обязательно так же, как в файле), и посчитать значение выражения обходом дерева. Может быть полезна функция ungetc (если не '(', возвращаем символ в поток и читаем число fscanf-ом). Можно считать, что входной файл корректен. Пример - по входному файлу (* (+ 1 1) 2) может печататься ( * ( + 1 1 ) 2 ) и выводиться 4.

Домашняя работа 6. 26.10.18
Абстрактные типы данных (слайды)
  1. Написать программу для вычисления арифметического выражения в постфиксной форме. С клавиатуры вводится последовательность цифр (для простоты) и операций +, -, *, /, представляющая выражение в постфиксной форме, должен выводиться результат вычисления. Например, на тесте 9 6 - 1 2 + * должно получиться 9.

  2. Написать программу проверки баланса скобок в строке, скобки могут быть трёх видов: (), [], {}. Скобочная последовательность вида ({)} считается некорректной, ({}) - корректной.

  3. Написать программу, преобразующую выражение из инфиксной формы в постфиксную. В выражении могут быть знаки +, -, *, /, скобки и цифры. Пример: (1 + 1) * 2 должно преобразовываться в 1 1 + 2 *. Алгоритм перевода предлагается найти самостоятельно (алгоритм "сортировочной станции" Э. Дейкстры).

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

  4. Реализовать сортировку слиянием. Во входном файле последовательность записей "имя - номер телефона". Программа должна отсортировать эти записи либо по имени, либо по номеру телефона, в зависимости от выбора пользователя, и вывести результат на экран. Количество записей заранее неизвестно, так что надо реализовывать списками на указателях.

Домашняя работа 5. 19.10.18
“Динамические” структуры данных (слайды)
Списки (слайды)
  1. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
    0 – выйти
    1 – добавить значение в сортированный список
    2 – удалить значение из списка
    3 – распечатать список
    Все операции должны сохранять сортированность. Начинаем с пустого списка.

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

Тест 1. 12.10.18
О разработке программных продуктов (слайды)
Картинка про размеры ПО
  1. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
    0 – выйти

    1 – заполнить массив чисел случайными значениями
    2 – отсортировать массив
    3 – развернуть массив
    4 – посчитать среднее арифметическое элементов массива

  2. Реализовать сортировку Шелла.

  3. Посчитать, сколько раз встречается каждый символ в файле и вывести на экран. Если символ в файле не встречается, его можно не выводить.

Домашняя работа 4. 05.10.18
Внутреннее представление данных (слайды)
Структуры, указатели, модули, файлы (слайды)
  1. Ввести два числа, перевести в двоичное представление в дополнительном коде и напечатать, сложить в столбик в двоичном представлении, вывести сумму, перевести в десятичное, вывести сумму в десятичном виде. Все сообщения писать по-русски (рекомендуется использовать функцию setlocale, чтобы сообщения выводились по-русски и под Windows тоже).

  2. Переделать задачу 3 из прошлого задания так, чтобы сортировка была в отдельном модуле и читала входные данные из файла.

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

Домашняя работа 3. 28.09.18
Сортировки (слайды)
Системы контроля версий, git (слайды)
Визуализаторы для разных алгоритмов сортировки
  1. Реализовать qsort, который для сортировки кусков массива размером меньше 10 использует сортировку вставкой.

  2. Получить с клавиатуры 2 числа, n и k (1 <= n <= 5000, 1 <= k <= 300000), сгенерировать массив из n чисел от 0 до 109, сгенерировать k целых чисел от 0 до 109 , для каждого из них проверить, содержится ли оно в массиве. Надо придумать алгоритм с временной сложностью O(n log n + k log n), или лучший.

  3. Найти наиболее часто встречающийся элемент в массиве быстрее, чем за O(n2 ).

  4. Завести аккаунт с разумным именем на https://github.com. Выложить туда в master уже зачтённые задачи (при этом придумав разумную структуру папок), все незачтённые выложить в отдельные ветки и сделать пуллреквесты. Имеет смысл посмотреть презентацию, https://git-scm.com/book/ru/v1 и поставить графический клиент типа https://tortoisegit.org/ для облегчения жизни. Не бояться экспериментировать со своим репозиторием и спрашивать препода.

Домашняя работа 2. 21.09.18
Сложность алгоритмов (слайды)
Тестирование и отладка (слайды)
Как не надо оформлять код
Как надо оформлять код
  1. Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.

  2. Реализовать возведение в степень --- в лоб (за линейное время) и за О(log n).

  3. Написать сортировки пузырьком и подсчётом.

  4. Написать программу, которая заполняет массив случайными значениями (с использованием функции rand из stdlib.h), потом преобразует его без использования дополнительных массивов так, что в начале массива будут элементы, меньшие первого, а в конце --- большие либо равные первому. Программа должна работать за линейное время.

    Тесты и строгое следование стайлгайду обязательны

Домашняя работа 1. 14.09.18
Введение, разбор задач (слайды)
  1. Написать программу, считающую значение формулы x4 + x3 + x2 + x + 1 за два умножения.

  2. Написать программу нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения.

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

  4. Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних), подсчётом числа билетов с заданной суммой трёх цифр.

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

  6. Заданы две строки: S и S1. Найти количество вхождений S1 в S как подстроки.

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

  8. Написать программу, считающую количество нулевых элементов в массиве.

© 2014-2018 HwProj