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

244 группа

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

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 №8 №9 №10 Тест 2 №12 №13 Тест 3
29 1 2 3 4 5 6 7 8 1 2 3 4 1 2 3 1 2 3 1 2 3 1 2 1 2 3 4 1 2 3 1 1 1 1 2 1 2 1 2 1 2 3
Антонов Андрей 1
Балашов Илья
Ивашева Валерия
Камкова Екатерина
Мендалиев Роман
Панфилёнок Дмитрий
Пиккио Полина
Пономарёв Егор 28
Хомяков Василий

Задачи

Тест 3. 15.12.17
  1. Реализовать сортировку Bogosort (https://ru.wikipedia.org/wiki/Bogosort).

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

  3. Реализовать конечный автомат, проверяющий, является ли строка корректным ноемром группы на матмехе. Номер группы начинается с последних двух цифр года поступления, Дальше "B" (бакалавры), "M" (магистры) или "S" (специалисты), дальше номер группы (число от 1 до 10), дальше строка "-mm". Например, "17B10-mm" является корректным номером группы.

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

  2. С помощью ДКА с явной таблицей состояний, заданной в файле, вывести на консоль все комментарии С++ вида /* комментарий */ из входного файла (вместе с символами "/* */").

Домашняя работа 12. 02.12.17
Алгоритмы Прима и Краскала
Алгоритм Кнута-Морриса-Пратта
Алгоритм Бойера-Мура
  1. Реализовать поиск подстроки любым из рассмотренных алгоритмов. Из файла читается текст, с консоли - строка, программа должна выводить на консоль позицию первого вхождения введённой строки в файле.

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

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

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

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

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

Домашняя работа 8. 03.11.17
Презентация про самобалансирующиеся деревья
  1. Реализовать ассоциативный массив с ключами и значениями типа string на основе splay-дерева. Должны поддерживаться следующие операции:

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

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

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

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

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

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

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

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

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

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

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

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

Тест 1. 06.10.17
Презентация с пары о разработке ПО
  1. Проверить, является ли строка палиндромом - то есть, читается ли она одинаково в обоих направлениях. Заглавные и строчные буквы считаются разными, пробелы должны игнорироваться. Пример палиндрома: "я иду с мечем судия". Строку можно задать как константу в коде, можно сделать ввод с клавиатуры. Для определения длины строки можно использовать функцию strlen из string.h.

  2. Реализовать сортировку выбором. Сортируемый массив (размером в 10 элементов) вводится с клавиатуры. Сортировка выбором - это та, где в неотсортированной части массива ищется минимальный элемент и добавляется к отсортированной части.

  3. Считать текст из файла и вывести его на консоль, заменяя каждую последовательность повторяющихся символов одним символом. Например. aafgbbba должно выводиться как afgba.

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

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

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

Домашняя работа 3. 22.09.17
Презентация с пары про стайлгайд
Как надо оформлять код
Как не надо оформлять код
Презентация с пары про сортировки
  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 ).

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

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

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

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

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