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

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

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

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

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

Зачёт:

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



Сдаваемые задачи должны соответствовать требованиям Стайлгайда, сопровождаться тестами и комментариями

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

1. 12.09.2012

1. Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x за два умножения.
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. Написать программу, считающую количество нулевых элементов в массиве.
11. * Проверить, является ли строка палиндромом.

2. 19.09.2012

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

3. 26.09.2012

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. 03.10.2012

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

5. 17.10.2012

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

6. 24.10.2012

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

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

7. 31.10.2012

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

8. 07.11.2012

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

9. 14.11.2012

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

Доклады:

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

10. 28.11.2012

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

11. 05.12.2012

1. Реализовать с помощью switch по состоянию лексический анализатор, проверяющий, является ли введённая последовательность символов вещественным числом (вещественное число задаётся регулярным выражением digit+ (. digit+)? (E(+ | -)? digit+)?, где digit - [0..9]).
2. С помощью ДКА с явной таблицей состояний вывести на консоль все комментарии С++ вида /* комментарий */ из входного файла (вместе с символами "/* */").

Презентация про лексический анализ