Домашние задания, контрольные работы, осень 2014, 144 группа

Домашние задания:

В табличке:
пусто - задачу не получал
? - задачу получал, но ещё не смотрел
0 - задача не зачтена
0.5 - в целом правильно, но надо кое-что поправить
1 - задача зачтена
- означает дополнительную задачу, которую делать не обязательно, потому что соответствующее ей домашнее задание сдано в срок
зелёным выделены работы, зачтённые полностью (и, соответственно, дающие балл на зачёт)
задачи со звёздочкой - дополнительные, для тех, кто не сдал домашнее задание через две недели после того, как оно было выдано



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

Контрольные работы:

В табличке:
- - задачу не получал
0 - задача не зачтена
1, x - задача зачтена (1 - написана с первого раза, количество x-ов равно количеству переписываний)
На переписывании надо решить только незачтённые задачи, то есть, например, если решены две задачи из трёх, на переписывании надо решить одну, по теме, к которой относится незачтённая задача

Условия задач:

1. 15.09.2014

1. Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x + 1 за два умножения.
4. Написать программу нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения.
5. Дан массив целых чисел x[1]...x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]...x[m] длины m и конца x[m+1]...x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец (обращением двух частей массива, а потом его самого).
6. Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних), подсчётом числа билетов с заданной суммой трёх цифр.
7. Написать программу проверки баланса скобок в исходной строке (т.е. число открывающих скобок равно числу закрывающих и выполняется правило вложенности скобок).
8. Заданы две строки: S и S1. Найти количество вхождений S1 в S как подстроки.
9. Написать программу, печатающую все простые числа, не превосходящие заданного числа.
10. Написать программу, считающую количество нулевых элементов в массиве.

2. 22.09.2014

1. Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.
2. Реализовать возведение в степень - в лоб и придумать, как быстрее, за О(log n)
3. Написать сортировки пузырьком и подсчётом (описание сортировки подсчётом найти самостоятельно)
4. Написать программу, которая заполняет массив случайными значениями (с использованием функции rand из stdlib.h), потом преобразует его без использования дополнительных массивов так, что в начале массива будут элементы, меньшие первого, а в конце - большие первого. Программа должна работать за линейное время.
5. * Дан массив с коэффициентами многочлена от x. Требуется написать программу, "красиво" выводящую этот многочлен на консоль. Например, многочлен, представляемый коэффициентами 1 5 -10, выводится так:

     2
   x + 5x - 10 
   

3. 29.09.2014

Визуализаторы для разных алгоритмов сортировки

1. Реализовать qsort, который для сортировки кусков массива размером меньше 10 использует сортировку вставкой.
2. Решить задачу с одной из лопатинских тренировок: получить с клавиатуры 2 числа, n и k (1 <= n <= 5000, 1 <= k <= 300000), сгенерировать массив из n чисел от 0 до 10^9, сгенерировать k целых чисел от 0 до 10^9 , для каждого из них проверить, содержится ли оно в массиве. Лобовое решение на тренировке не укладывалось во временные ограничения, так что здесь надо придумать алгоритм с временной сложностью O(n log n + k log n), или лучший.
3. Найти наиболее часто встречающийся элемент в массиве быстрее, чем за O(n^2).
4. * Написать программу, которая переставляет цифры натурального числа таким образом, чтобы образовалось наименьшее число, записанное этими же цифрами.

4. 06.10.2014

Штука для перевода десятичных чисел во внутреннее представление
Пример работы с файлами

1. Ввести два числа, перевести в двоичное представление (в каком-либо из кодов) и напечатать, сложить, вывести сумму, перевести в десятичное, вывести результат в десятичном виде. Все сообщения писать по-русски, для этого будет полезна функция setlocale.
2. Переделать задачу 3 из прошлого задания так, чтобы сортировка была в отдельном модуле и читала входные данные из файла.
3. Написать программу, которая считает количество непустых строк в исходном файле. Строка считается пустой, если состоит только из пробелов и табуляций (символ \t), или в ней нет символов вообще.
4. * Найти информацию по сортировке Шелла и реализовать её.

5. 13.10.2014

Презентация с пары

Презентация с дополнительной пары про ООП

6. 20.10.2014

Код с пары

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

7. 27.10.2014

1. Реализовать сортировку слиянием. Во входном файле последовательность записей "имя - номер телефона". Программа должна отсортировать эти записи либо по имени, либо по номеру телефона, в зависимости от выбора пользователя, и вывести результат на экран. Количество записей неизвестно, так что реализовывать списками на указателях.
2. Написать программу для вычисления арифметического выражения в постфиксной форме. С клавиатуры вводится последовательность цифр (для простоты) и операций +, -, *, /, представляющая выражение в постфиксной форме, должен выводиться результат вычисления. Например, на тесте 9 6 - 1 2 + * должно получиться 9.
3. Написать программу проверки баланса скобок в строке, скобки могут быть трёх видов: (), [], {}. Скобочная последовательность вида ({)} считается некорректной, ({}) - корректной.
4. Написать программу, преобразующую выражение из инфиксной формы в постфиксную. В выражении могут быть знаки +, -, *, /, скобки и цифры. Пример: (1 + 1) * 2 должно преобразовываться в 1 1 + 2 *. Алгоритм перевода предлагается найти самостоятельно (алгоритм "сортировочной станции" Э. Дейкстры).
5. * Существуют способы обойти шахматным конем доску 8х8, побывав на каждом поле только один раз. Составить программу подсчета числа способов обхода, с выводом всех путей обхода. В этой задаче доска может быть размера от 1х1 до 10х10, так что путей обхода может и не быть.

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

Презентация с дополнительной пары про ООП на C++

8. 10.11.2014

Код с пары

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

Презентация с дополнительной пары про Qt

9. 17.11.2014

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

10. 27.11.2014

1. Есть множество городов и дороги, связывающие эти города. Для каждой дороги задана её длина. Задача - распределить города между государствами по такому алгоритму: задаются k столиц каждого государства, далее по очереди каждому государству добавляется ближайший незанятый город, непосредственно связанный дорогой с каким-либо городом, уже принадлежащим государству (столицей или каким-либо городом, добавленным на одном из предыдущих шагов). Процесс продолжается до тех пор, пока все города не будут распределены. Граф дорог связный. Во входном файле: n - число городов и m - число дорог. Далее следуют сами дороги в формате: i j len, i и j - номера городов, len - длина дороги. Далее задано число k - число столиц, далее - k чисел - номера столиц. Надо вывести на консоль номера государств и списки городов, принадлежащих государствам.
2. * Реализовать консольную игру "Быки и коровы" (http://goo.gl/J1LKti).

Доклады:

1. Алгоритмы Прима и Краскала --- Владислав Голиков
2. Алгоритм Кнута-Морриса-Пратта --- Дарья Белозерцева
3. Алгоритм Рабина-Карпа --- Григорий Киргизов
4. Алгоритм Бойера-Мура --- Андрей Кудрявцев

11. 01.12.2014

Презентация с пары про парадигмы программирования
Презентация с дополнительной пары про сцену в Qt

12. 08.12.2014

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