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

244 группа

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

Студент TODO №1 №2 №3 Тест 1 №4 №5 №6 №7 №8 №9 Тест 2 №10 №11 Тест 3
116 1 2 3 4 5 1 2 3 4 1 2 1 2 3 4 5 1 2 3 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 1 2 3
Бакирова Анна 35
Дегтярев Иван
Дементьев Александр 17
Зайцев Дмитрий 4
Кидянкин Михаил
Крупина Валерия 29
Кузьмин Юрий
Леонова Анна 31
Полетанский Виктор
Ходько Андрей
Шервашидзе Георгий

Задачи

Тест 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" является корректным номером группы.

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

Домашняя работа 10. 04.12.17
Алгоритмы Прима и Краскала
Алгоритм А*
  1. Реализовать алгоритм A* для поиска пути на двумерной карте. Карта задаётся двумерным массивом в файле, где каждой пустой клетке соответствует 0, а каждой занятой 1. На входе программы координаты точек начала и конца пути. Программа должна нарисовать в консоли заданную карту и проложенный алгоритмом путь. (Вывод отладочной информации на этой карте также приветствуется.)

  2. Реализовать алгоритм Рабина-Карпа поиска подстроки в строке (программа должна выводить индексы всех вхождений).

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

  2. Реализовать кодирование текста с помощью алгоритма Хаффмана (http://habrahabr.ru/post/144200/). На входе программы файл с текстом из латинских букв, пробелов и знаков препинания. На выходе текстовый файл, состоящих из двух строк. Первая строка содержит в себе представление дерева, которое строится в ходе работы алгоритма (например, в отладочном варианте из задачи 7.1), вторая строка — последовательность нулей и единиц, в которую кодируется входной текст. Крайне приветствуется вывод таблицы частоты вхождения символов исходного текста.

  3. Реализовать раскодирование с помощью алгоритма Хаффмана. На входе файл, генерируемый программой из задачи 1, на выходе — исходный закодированный текст.

Домашняя работа 8. 12.11.17
Хеш-таблицы (презентация)
Хеш-таблицы (конспект)
  1. Получив домашнее задание по программированию, группа студентов приступила к решению задач. Три студента с номерами 1, 2 и 3 честно сделали все задание самостоятельно, другие решили списать с кого-нибудь, кто уже имеет готовое решение — либо решенное самостоятельно, либо уже списанное с другого. При проверке выяснилось, что некоторых студентов следует немедленно отчислить, т.к. они не только не написали решение сами, но и поленились списать. Задача: Определить, какой студент какое решение сдавал, и кого надо отчислить. На входе: количество студентов и список пар чисел, где первое число — номер студента, второе — номер того, с кого было списано решение. Требуется вывести список пар чисел, где первое число — номер студента, второе — 1, 2 или 3 — сданный вариант.

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

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

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

  2. Переделать множество из задачи 1 на основе АВЛ-дерева.

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

Домашняя работа 6. 03.11.17
Системы контроля версий (презентация)
Системы контроля версий (конспект)
  1. Зарегистрироваться на github.com и выложить туда все зачтённые домашки.

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

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

Домашняя работа 5. 13.10.17
Представление данных (конспект)
Представление данных (презентация)
  1. По содержимому памяти вывести значение типа double в экспоненциальной форме: sm*qSp, где s — знак мантиссы, m — мантисса, q — основание системы счисления, S — знак порядка, p — порядок числа. Значение 0 должно выводиться как 0. Примеры допустимого вывода:
    Enter a number: -2.5
    Result: -1.25*21
    Enter a number: 12312.323
    Result: +1.5029691162109375384*213

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

  3. Дан массив с коэффициентами многочлена от x. Требуется написать программу, "красиво" выводящую этот многочлен на консоль. Например, многочлен, представляемый коэффициентами -1 12321 0 0 0 -1 -1 -1 1 1 34 -2 0 0, выводится так:
    картинка

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

Домашняя работа 4. 07.10.17
АТД, списки
О разработке ПО (презентация)
О разработке ПО (конспект)
  1. Дан массив размерностью n x n, n — нечетное число. Вывести элементы массива при обходе его по спирали, начиная с центра.

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

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

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

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

Тест 1. 29.09.17
Домашняя работа 3. 24.09.17
Указатели и динамическая память
Структуры данных
  1. Найдите максимальный элемент массива, встречающийся более одного раза (массив неупорядоченный).

  2. Даны две строки. Определить, можно ли, переставляя символы в первой строке, получить вторую строку. Хочется решение быстрее, чем за O( n2 ).

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

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

Домашняя работа 2. 15.09.17
Конспект
  1. Реализовать рекурсивный и итеративный подсчет чисел Фибоначчи.

  2. Реализовать возведение в целую степень (с логарифмической сложностью алгоритма).

  3. Напечатать все представления натурального числа N суммой натуральных слагаемых. Перестановка слагаемых нового способа не дает.

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

  5. Реализовать алгоритм пирамидальной сортировки.

Домашняя работа 1. 08.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. Реализовать подсчет факториала (рекурсивно и итеративно).

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

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

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

© 2014-2018 HwProj