Домашние задания, осень 2010, 145 группа

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

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

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

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

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

1. 13.09.2010

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. Написать программу, считающую количество нулевых элементов в массиве.
11. Проверить, является ли строка палиндромом.

2. 20.09.2010

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

3. 27.09.2010

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

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

5. 18.10.2010

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

6. 25.10.2010

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

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

7. 01.11.2010

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

8. 08.11.2010

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

9. 15.11.2010

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

• Придумать и реализовать самый бредовый алгоритм сортировки. Вдохновляться можно Bogosort и глупой сортировкой . Авторам достаточно бредовых алгоритмов прощается любая одна задача из первых четырёх д/з.

10. 29.11.2010

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

11. 06.12.2010

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

Условия контрольных:

11.10.2010

1. Проверить, является ли строка палиндромом - то есть, читается ли она одинаково в обоих направлениях. Заглавные и строчные буквы считаются разными, пробелы должны игнорироваться. Пример палиндрома: "я иду с мечем судия". Строку можно задать как константу в коде, можно сделать ввод с клавиатуры. Для определения длины строки можно использовать функцию strlen из string.h.
2. Реализовать сортировку выбором. Сортируемый массив (размером в 10 элементов) вводится с клавиатуры. Сортировка выбором - это та, где в неотсортированной части массива ищется минимальный элемент и добавляется к отсортированной части.
3. В некоторых языках программирования однострочные комментарии задаются не //, как в С++, а символом ";" (комментарий начинается с ; и заканчивается концом строки). Задача - вывести на консоль все комментарии такого вида из входного файла (вместе с символом ";"). До комментария в строке может быть значимый текст, его выводить не надо. Конец строки представляется символом \n, могут быть полезны функции fgetc и feof.

25.10.2010 (переписывание 1 к/р)

1. Удвоить вхождение некоторой буквы во входном тексте и вывести получившийся текст. Текст и буква вводятся с консоли. Чтобы вводить строку с пробелами, используйте в scanf форматный спецификатор %[^\n], например scanf("%[^\n]", str);, или функцию gets
2. Реализовать сортировку вставками.
3. Вывести на консоль все однострочные комментарии С++ (вида // комментарий) из входного файла (вместе с символами "//"). До комментария в строке может быть значимый текст, его выводить не надо, строки без комментариев не выводить. Конец строки представляется символом \n, могут быть полезны функции fgetc и feof.

01.11.2010 (переписывание 1 к/р)

1. Два неотрицательных числа заданы в двоичной форме в массивах. Элементы обоих массивов - булевые. Написать программу, которая определяет, какое число больше.
2. Реализовать сортировку пузырьком.
3. Считать текст из файла и вывести его на консоль, заменяя каждую последовательность повторяющихся символов одним символом. Например. aafgbbba должно выводиться как afgba.

08.11.2010 (переписывание 1 к/р)

1. В массиве целых чисел найти число, сумма цифр которого была бы наибольшей. Если таких чисел несколько, вывести на экран все эти числа.
3. Посчитать, сколько раз встречается каждый символ в файле и вывести на экран. Если символ в файле не встречается, его можно не выводить.

22.11.2010 (2 к/р)

1. Даны числа a и b. За один просмотр файла f, элементами которого являются целые числа, и без использования дополнительных файлов переписать его элементы в файл g так, чтобы первоначально были записаны все числа, меньше заданного a, затем все числа из отрезка [a,b], затем все остальные. Взаимный порядок в каждой из групп должен быть сохранен, предположений о количестве элементов делать нельзя.
2. Во входном файле заданы два отсортированных списка чисел (список представлен в таком виде: сначала идёт число элементов списка, затем - сами элементы). Вывести в выходной файл список чисел - результат их слияния. Предположений о максимальной длине списков делать нельзя.

29.11.2010 (переписывание 2 к/р)

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

06.12.2010 (переписывание 2 к/р)

1. Реализовать односвязный список и операцию, которая его переворачивает. В списке лежат числа, значения считываются из файла. Например, на файле 1 2 3 программа должна выводить 3 2 1.
2. Удалить из списка строк все повторяющиеся элементы. Строки считывать из файла.

15.12.2010 (переписывание 2 к/р)

1. Дан односвязный список целых чисел. Построить по нему список из элементов, образующих возрастающую последовательность наибольшей длины. Например, по списку 1 2 3 2 1 4 должен быть построен список 1 2 3.
2. По бинарному отношению на множестве из n элементов построить его транзитивное замыкание. В файле указано число n и матрица n*n, задающая отношение (в ячейке (i,j) стоит 1, если пара элементов (i, j) принадлежит отношению и 0 в противном случае). Вывести в другой файл матрицу, задающую транзитивное замыкание этого отношения.

17.12.2010 (переписывание 1 к/р)

3. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
   0 – выйти
   1 – заполнить массив чисел случайными значениями
   2 – отсортировать массив
   3 – развернуть массив
   4 – посчитать среднее арифметическое элементов массива

17.12.2010 (переписывание 2 к/р)

1. Дано n – количество запросов. Далее n чисел от -1 до 10^9 – запросы. Если запрос равен -1, следует убрать элемент из начала очереди (если она не пуста). Иначе следует добавить этот элемент в конец очереди. Для каждого запроса -1 вывести убираемый элемент, либо -1, если очередь пуста.
2. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
   0 - выйти
   1 - добавить значение в заданную позицию в двусвязный список
   2 - удалить значение в заданной позиции из списка
   3 - распечатать список
   Позиции задаются целыми числами, 0 соответствует голове списка.

22.12.2010 (переписывание 2 к/р)

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