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

144 группа

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

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7
158 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 1 2 3 4 1 2 3 1 2 1 2 3 1 2 3 1 2 3
Артём Вяткин 16
Вильданов Эмир 23
Власов Илья 16
Держко Александр 19
Пяйве Олег 19
Уткин Илья 17
Фадеев Матвей 22
Шумаков Антон 26

Задачи

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

  2. Описать модуль для работы с АТД "Строка" со следующими операциями: создание, удаление, копирование (функцию clone(), возвращающую полную копию строки), конкатенация (дописывание строки-аргумента к текущей), сравнение на равенство, вычисление длины, проверка на пустоту, выделение подстроки, преобразование к char*. Строка должна быть потенциально расширяемой в неограниченных пределах.

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

Домашняя работа 6. 23.10.19
Слайды
Конспекты
  1. По содержимому памяти вывести значение типа double в экспоненциальной форме: sm*q{Sp}, где s — знак мантиссы, m — мантисса, q — основание системы счисления, S — знак порядка, p — порядок числа. Примеры допустимого вывода:
    Enter a number: -2.5
    Result: -1.25*21
    Enter a number: 12312.323
    Result: +1.5029691162109375384*213

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

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

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

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

  3. Объединить предыдущие две задачи в одну программу — реализовать программу-калькулятор, вычисляющую значение арифметического выражения в инфиксной нотации. Выражение вводится с консоли, должны поддерживаться операции {+, -, *, /} и скобки, операнды считать односимвольными.

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

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

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

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

  3. Дан массив размерностью n x n, n — нечетное число. Вывести элементы массива при обходе его по спирали, начиная с центра.

Домашняя работа 3. 30.09.19
Указатели и динамическая память (слайды)
  1. Реализовать алгоритм пирамидальной сортировки.

  2. Написать программу, которая считает количество непустых строк в исходном файле. Строка считается пустой, если состоит только из пробелов и табуляций (символ \t), или в ней нет символов вообще.

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

  4. Пользователи совершают действия, про каждое из них известно, сколько минут назад его сделали. Сколько пользователей совершили k действий за последние t минут?
    На вход подаётся 3 числа: n, k, t -- число пользователей, необходимое число действий и временной промежуток. Затем в 2 * n строках описывается каждый пользователь: для i пользователя указывается m_i -- число действий, которое совершил пользователь, а затем m_i чисел -- сколько минут назад совершалось каждое действие.
    Пример:
    3 2 5
    5
    10 3 5 8 1
    1
    3
    4
    3 2 8 20
    Ответ: 1 (только 3 пользователь совершил 2 действия за последние 5 минут).

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

  2. Напечатать в порядке возрастания все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают n.

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

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

  5. Даны две строки. Определить, можно ли, переставляя символы в первой строке, получить вторую строку. Хочется решение без вложенных циклов.

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

Домашняя работа 1. 10.09.19
Стайлгайд
Сортировки (слайды)
Сортировки (конспект)
  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. Заданы две строки: s1 и s2. Найти количество вхождений s2 в s1 как подстроки.

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

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

  9. Посчитать целую степень числа: an.

  10. Реализовать программу, проверяющую, является ли строка палинромом.

  11. Реализовать быструю сортировку (в рекурсивном варианте).

© 2014-2019 HwProj