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

244 группа

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

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 №8 №9 №10 №12 Тест 2 №13 Тест 3
29 1 2 3 1 2 3 1 2 1 2 3 4 1 2 3 1 2 1 1 1 2 1 2
Алексей Гирин 2
Бахметьев Владимир
Долгополова Мария
Емельянова Ирина 1
Зайнуллин Егор
Ольга Пушина 19
Петрова Екатерина 7
Сушенцев Денис

Задачи

Тест 3. 16.12.16
  1. Дана строка, изображающая двоичную запись целого положительного числа. Вывести строку, изображающую десятичную запись этого же числа

  2. Дан файл следующего формата: первая строка --- пара чисел n m, n --- число строк матрицы, m --- число столбцов. Дальше идут n строк по m чисел в каждой. Вывести эту матрицу в файл out1.txt в форме сходящейся спирали, начинающейся с первого элемента первой строки. Вывести в файл out2.txt все ненулевые элементы матрицы в произвольном порядке. Вывести в файл out3.txt матрицу, каждый элемент которой является квадратом соответствующего элемента исходной матрицы.

  3. Распечатать вершины графа в каком-либо из порядков при обходе в ширину. Граф задаётся в файле матрицей смежности, первая строчка в файле — количество вершин в графе, дальше — сама матрица (n строк по n элементов в каждой).

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

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

Тест 2. 26.11.16
  1. Дан файл, в котором встречаются даты. Каждая дата – это число, месяц и год (например, 09.11.2009). Найти наибольшую дату.

  2. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:

    • 0 – выйти
    • 1 – добавить значение в заданную позицию в двусвязный список
    • 2 – удалить значение в заданной позиции из списка
    • 3 – распечатать список

    Позиции задаются целыми числами, 0 соответствует голове списка.

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

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

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

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

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

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

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

  2. Собрать какую-либо из предыдущих задач в консоли каким-либо из рассмотренных на паре инструментов, приложить скриншот успешной сборки.

Домашняя работа 7. 22.10.16
Презентация про деревья
Презентация про 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, прислать его мне на почту и добавить меня в коллабораторы (мой аккаунт на гитхабе: https://github.com/yurii-litvinov). Выложить туда в master уже зачтённые задачи (при этом придумав разумную структуру папок), все незачтённые выложить в отдельные ветки и сделать пуллреквесты. Имеет смысл посмотреть презентацию, https://git-scm.com/book/ru/v1 и поставить графический клиент типа https://tortoisegit.org/ для облегчения жизни. Не бояться экспериментировать со своим репозиторием и спрашивать препода.

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

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

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

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

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

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

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

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

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

  3. В некоторых языках программирования однострочные комментарии задаются не //, как в С++, а символом ";" (комментарий начинается с ; и заканчивается концом строки). Задача - вывести на консоль все комментарии такого вида из входного файла (вместе с символом ";"). До комментария в строке может быть значимый текст, его выводить не надо. Конец строки представляется символом \n, могут быть полезны функции fgetc и feof.

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

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

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

Домашняя работа 3. 15.09.16
Презентация с пары про сортировки
Визуализаторы для разных алгоритмов сортировки
Конспект с пары соседней подгруппы про сортировки (с интересными ссылками)
Презентация с пары про тестирование
  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. 08.09.16
Как не надо оформлять код
Как надо оформлять код
Презентация с пары про стайлгайд
Презентация с пары про сложность
  1. Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.

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

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

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

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