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

244-2014 группа

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

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №7 №8 Тест 2 №9 №10 Тест 3
66 1 2 3 4 5 6 1 2 3 4 1 2 1 2 3 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3
Бабкин Иван 28
Батоев Константин
Боровков Данила
Ершов Иван
Иванов Илья 23
Корнилова Анастасия
Маслов Алексей 14
Рюмин Артём
Смоляков Никита 1
Соловьев Александр
Танков Владислав

Задачи

Тест 3. 15.12.14
  1. 1

  2. 2

  3. 3

Домашняя работа 10. 10.12.14
Лексический анализ (конспект)
Лексический анализ (презентация)
Синтаксический анализ (конспект)
Синтаксический анализ (презентация)
  1. Реализовать автомат по разбору чисел с плавающей точкой

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

Домашняя работа 9. 01.12.14
  1. Даны 2 текстовых файла. Записать в третий файл только те строки, которые встречаются и в первом, и во втором файлах.

  2. Реализовать алгоритм Рабина-Карпа поиска подстроки в строке.

  3. По данному неориентированному графу построить минимальное остовное дерево с помощью алгоритма Прима.

Тест 2. 01.12.14
Домашняя работа 8. 24.11.14
Конспект
  1. Пронумеровать вершины ориентированного графа в произвольном порядке латинскими буквами. На входе имя файла с заданием графа и начальная вершина, от которой будет осуществляться нумерация. Предполагается, что в графе одна компонента связности.

  2. В некоторой стране n городов, соединенных между собой дорогами различной длины. По каждой дороге можно проехать в обе стороны. 1 сентября 1939г силы вермахта подло вторглись в эту страну и захватили город с номером 1. Далее, каждый день они захватывали по одному городу, используя следующий алгоритм: среди всех еще не захваченных городов выбирается ближайший к городу 1 и захватывается. Во входном файле заданы n - число городов и m - число дорог. Далее следуют сами дороги в формате: "i j len", i и j - номера городов, len - длина дороги. Задача: вывести номера городов в порядке захвата, а также и расстояние и путь от каждого захваченного города до города 1. Города нумеруются с 1.

  3. Вывести компоненты связности заданного неориентированного графа.

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

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

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

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

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

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

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

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

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

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

Тест 1. 13.10.14
Домашняя работа 4. 06.10.14
Двусвязный список (код с пары)
Стек (код с пары)
Конспект пары о разработке ПО
Презентация с пары о разработке ПО
  1. Найдите максимальный элемент массива, встречающийся более одного раза (массив неупорядоченный). Задачу хочется решить быстрее, чем за O(n2).

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

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

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

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

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

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

  4. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции: 0 - exit; 1 - add a value to sorted list; 2 - remove a value from sorted list; 3 - print list. Все операции должны сохранять сортированность. Начинаем с пустого списка. Список должен быть оформлен отдельным модулем.

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

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

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

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

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

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

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

Домашняя работа 1. 15.09.14
Конспект пары
  1. Написать программу, считающую значение формулы x4 + x3 + x2 + x за два умножения.

  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