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

144 группа

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

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 №8
306 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
Бадмаев Чингис 31
Бочаров Глеб 31
Виктория Фомина 10
Вологин Дмитрий 13
Донина Дарья 12
Дорожкин Сергей 13
Зиннатулин Тимур 14
Катричко Ульяна 15
Ким Юния 12
Ключников Даниил 18
Костин Павел 25
Лада Егорова 14
Липаев Савелий 9
Мамро Никита 12
Мирошникова Мария 13
Паршин Максим 6
Соболевская Надежда 10
Терентьев Даниил 31
Хованов Виктор 17

Задачи

Домашняя работа 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. Проверить, является ли строка палиндромом - то есть, читается ли она одинаково в обоих направлениях. Заглавные и строчные буквы считаются разными, пробелы должны игнорироваться. Пример палиндрома: "я иду с мечем судия". Строку можно задать как константу в коде, можно сделать ввод с клавиатуры. Для определения длины строки можно использовать функцию strlen из string.h.

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

  3. Дан файл f.txt, содержащий в себе целые числа, и файл g.txt, содержащий в себе одно целое число x. Создать файл h.txt, куда вывести все числа из файла f.txt, меньшие x, в том же порядке, что и в исходном файле.

Домашняя работа 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