Programing homeworks
Первый семестр:
Домашняя работа 1. 10.09.15
1.1 Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x + 1 за два умножения. 1.2 Реализовать алгоритм нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения. 1.3 Дан массив целых чисел x[1]...x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]...x[m] длины m и конца x[m+1]...x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец. 1.4 Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних). 1.5 Написать программу проверки баланса скобок в исходной строке (т.е. число открывающих скобок равно числу закрывающих и выполняется правило вложенности скобок). 1.6 Заданы две строки: s и s1. Найти количество вхождений s1 в s как подстроки. 1.7 Написать программу, печатающую все простые числа, не превосходящие заданного числа. 1.8 Реализовать подсчет факториала (рекурсивно и итеративно). 1.9 Посчитать целую степень числа: a^n. 1.10 Реализовать программу, проверяющую, является ли строка палинромом. 1.11 Реализовать быструю сортировку (в рекурсивном варианте).
Домашняя работа 2. 17.09.15
2.1 Реализовать рекурсивный и итеративный подсчет чисел Фибоначчи. 2.2 Реализовать возведение в целую степень (с логарифмической сложностью алгоритма). 2.3 Напечатать все представления натурального числа N суммой натуральных слагаемых. Перестановка слагаемых нового способа не дает. 2.4 Напечатать в порядке возрастания все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают n. 2.5 Реализовать алгоритм пирамидальной сортировки. 2.6 Реализовать консольную игру "Быки и коровы" (http://goo.gl/J1LKti).
Домашняя работа 3. 26.09.15
3.1 Найдите максимальный элемент массива, встречающийся более одного раза (массив неупорядоченный). 3.2 Написать программу преобразования инфиксной формы выражения в постфиксную. Известно, что каждый операнд занимает один символ. В выражении могут быть знаки +, -, *, /, скобки и цифры. Пример: (1 + 1) * 2 должно преобразовываться в 1 1 + 2 *. Алгоритм перевода предлагается найти самостоятельно (алгоритм "сортировочной станции" Э. Дейкстры). 3.3 Реализовать программу, вычисляющую значение выражения в постфиксной записи с помощью стека. 3.4 Объединить предыдущие две задачи в одну программу — реализовать программу-калькулятор, вычисляющую значение арифметического выражения в инфиксной нотации. Выражение вводится с консоли, должны поддерживаться операции {+, -, *, /} и скобки, операнды считать односимвольными.
Домашняя работа 4. 02.10.15
4.1 Даны две строки. Определить, можно ли, переставляя символы в первой строке, получить вторую строку. Хочется решение быстрее, чем за O(n^2). 4.2 Дан массив размерностью N x N, N — нечетное число. Вывести элементы массива при обходе его по спирали, начиная с центра. 4.3 Написать программу, которая переставляет цифры натурального числа таким образом, чтобы образовалось наименьшее число, записанное этими же цифрами. 4.4 Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции: 0 - exit; 1 - add a value to sorted list; 2 - remove a value from sorted list; 3 - print list. Все операции должны сохранять сортированность. Начинаем с пустого списка. Список должен быть оформлен отдельным модулем. 4.5 "Считалочка" — отряд из 41-го сикария, защищавший галилейскую крепость Массада, не пожелал сдаваться в плен блокировавшим его превосходящим силам римлян. Сикарии стали в круг и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. Самоубийство — тяжкий грех, но тот, кто в конце концов останется последним, должен будет его совершить. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам. В нашем случае участвует n воинов и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который должен будет остаться последним. Считать с помощью циклического списка, который должен быть оформлен отдельным модулем.
Домашняя работа 5. 10.10.15
5.1 Дан файл с текстом. Вывести все слова этого текста, предварительно оставив в каждом слове только первые вхождения каждой буквы. 5.2 По содержимому памяти вывести значение типа double в экспоненциальной форме: smq^(Sp), где s — знак мантиссы, m — мантисса, q — основание системы счисления, S — знак порядка, p — порядок числа. Примеры допустимого вывода: Enter a number: -2.5 Result: -1.252^(1) Enter a number: 12312.323 Result: +1.50296911621093753842^(13) 5.3 Вывести на консоль все однострочные комментарии С++ (вида // комментарий) из входного файла (вместе с символами "//"). До комментария в строке может быть значимый текст, его выводить не надо, строки без комментариев не выводить. Конец строки представляется символом '\n', могут быть полезны функции fgetc и feof. Программа должна учитывать случаи, когда последовательность "//" находится внутри текстовой строки или многострочного комментария (/ */). В таких случаях ничего выводить не нужно. 5.4 Написать программу-телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции: 0 - выйти 1 - добавить запись (имя и телефон) 2 - найти телефон по имени 3 - найти имя по телефону 4 - сохранить текущие данные в файл. При запуске программа должна читать данные из файла, если файла нет — начинать с пустой базы номеров. Формат представления данных в файле придумать самостоятельно.
Домашняя работа 6. 21.10.15
6.1 Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках, а также в формате (a b c), где a — значение в узле, а b и c — аналогичные представления поддеревьев правого и левого потомка. Пример: "(5 (2 null null) (10 null (12 null null)))". Такой вывод бывает крайне полезен при отладке операций над деревом. 6.2 По дереву разбора арифметического выражения вычислить его значение. Дерево разбора хранится в файле в виде (<операция> <операнд1> <операнд2>), где <операнд1> и <операнд2> сами могут быть деревьями, либо числами. Например, выражение (1 + 1) * 2 представляется в виде (* (+ 1 1) 2). Должны поддерживаться операции +, -, , / и целые числа в качестве аргументов. Требуется построить дерево в явном виде, распечатать его (не обязательно так же, как в файле), и посчитать значение выражения обходом дерева. Может быть полезна функция ungetc. Можно считать, что входной файл корректен. Пример: по входному файлу ( (+ 1 1) 2) может печататься ((1 + 1) * 2) и выводиться 4. 6.3 Переделать множество из задачи 1 на основе АВЛ-дерева.
Домашняя работа 7. 22.10.15
7.1 Получив домашнее задание по программированию, группа студентов приступила к решению задач. Три студента с номерами 1, 2 и 3 честно сделали все задание самостоятельно, другие решили списать с кого-нибудь, кто уже имеет готовое решение — либо решенное самостоятельно, либо уже списанное с другого. При проверке выяснилось, что некоторых студентов следует немедленно отчислить, т.к. они не только не написали решение сами, но и поленились списать. Задача: Определить, какой студент какое решение сдавал, и кого надо отчислить. На входе: количество студентов и список пар чисел, где первое число — номер студента, второе — номер того, с кого было списано решение. Требуется вывести список пар чисел, где первое число — номер студента, второе — 1, 2 или 3 — сданный вариант. 7.2 Описать модуль для работы с АТД "Строка" со следующими операциями: создание, удаление, копирование (функцию clone(), возвращающую полную копию строки), конкатенация (дописывание строки-аргумента к текущей), сравнение на равенство, вычисление длины, проверка на пустоту, выделение подстроки, преобразование к char*. Строка должна быть потенциально расширяемой в неограниченных пределах. 7.3 Реализовать алгоритмы для работы с хэш-таблицей (разрешение коллизий методом цепочек). По данному тексту (читается из файла, не ограничен по размеру) посчитать число использований каждого слова. Вывести load factor, среднюю длину цепочки, максимальную длину цепочки и значения, которые в нее попали, общее число добавленных слов, число пустых ячеек таблицы. Для работы со строками использовать модуль "Строка" из задачи 2.
Домашняя работа 8. 30.10.15
8.1 Пронумеровать вершины ориентированного графа в произвольном порядке латинскими буквами. На входе имя файла с заданием графа и начальная вершина, от которой будет осуществляться нумерация. Предполагается, что в графе одна компонента связности. 8.2 В некоторой стране n городов, соединенных между собой дорогами различной длины. По каждой дороге можно проехать в обе стороны. 1 сентября 1939г силы вермахта подло вторглись в эту страну и захватили город с номером 1. Далее, каждый день они захватывали по одному городу, используя следующий алгоритм: среди всех еще не захваченных городов выбирается ближайший к городу 1 и захватывается. Во входном файле заданы n - число городов и m - число дорог. Далее следуют сами дороги в формате: "i j len", i и j - номера городов, len - длина дороги. Задача: вывести номера городов в порядке захвата, а также и расстояние и путь от каждого захваченного города до города 1. Города нумеруются с 1. 8.3 Вывести компоненты связности заданного неориентированного графа.
Домашняя работа 9. 06.11.15
9.1 Даны 2 текстовых файла. Записать в третий файл только те строки, которые встречаются и в первом, и во втором файлах. 9.2 Реализовать алгоритм Рабина-Карпа поиска подстроки в строке. 9.3 По данному неориентированному графу построить минимальное остовное дерево с помощью алгоритма Прима.
Домашняя работа 10. 28.11.15
10.1 Реализовать кодирование текста с помощью алгоритма Хаффмана (http://habrahabr.ru/post/144200/). На входе программы файл с текстом из латинских букв, пробелов и знаков препинания. На выходе текстовый файл, состоящих из двух строк. Первая строка содержит в себе представление дерева, которое строится в ходе работы алгоритма (например, в отладочном варианте из задачи 6.1), вторая строка — последовательность нулей и единиц, в которую кодируется входной текст 10.2 Реализовать раскодирование с помощью алгоритма Хаффмана. На входе файл, генерируемый программой из задачи 1, на выходе — исходный закодированный текст.
Домашняя работа 11. 28.11.15
11.1 Реализовать автомат по разбору чисел с плавающей точкой
Домашняя работа 12. 08.12.15
12.1 Реализовать синтаксический анализатор, разбирающий арифметические выражения методом рекурсивного спуска. Входной поток составляют числа, разбираемые лексическим анализатором из прошлого задания, и знаки операций {+, -, /, *}
Домашняя работа 13. 11.12.15
13.1 Зарегистрироваться на github.com, выложить имя логина. Создать себе репозиторий для домашних задач с адекватным именем. 13.2 Придумать подходящую структуру папок и выложить в гит все имеющиеся исходники решений задач с прошлого семестра. Каждая ДЗ должна быть оформлена отдельным коммитом.