GirZ0n/SPBU-Homework-1

Programming homework for the first semester

SPBU-Homework-1

Here you can find conditions and solutions to problems for the first semester.

Navigation menu

• Semester №1 ⬅️ You are here
• Semester №2
• Semester №3
• Semester №4

Homework

Homework №1

1. Написать программу, считающую значение формулы x^4 + x^3 + x^2 + x + 1 за два умножения. [Solution]

2. Реализовать алгоритм нахождения неполного частного от деления a на b (целые числа), используя только операции сложения, вычитания и умножения. [Solution]

3. Дан массив целых чисел x[1]...x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]...x[m] длины m и конца x[m+1]...x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец. [Solution]

4. Посчитать число "счастливых билетов" (билет считается "счастливым", если сумма первых трёх цифр его номера равна сумме трёх последних). [Solution]

5. Написать программу проверки баланса скобок в исходной строке (т.е. число открывающих скобок равно числу закрывающих и выполняется правило вложенности скобок). [Solution]

6. Заданы две строки: s1 и s2. Найти количество вхождений s2 в s1 как подстроки. [Solution]

7. Написать программу, печатающую все простые числа, не превосходящие заданного числа. [Solution]

8. Реализовать подсчет факториала (рекурсивно и итеративно). [Solution]

9. Посчитать целую степень числа: a^n. [Solution]

10. Реализовать программу, проверяющую, является ли строка палинромом. [Solution]

11. Реализовать быструю сортировку (в рекурсивном варианте). [Solution]

Homework №2

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

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

3. Реализовать консольную игру "Быки и коровы". [Solution]

4. Найдите максимальный элемент массива, встречающийся более одного раза (массив неупорядоченный). [Solution]

5. Даны две строки. Определить, можно ли, переставляя символы в первой строке, получить вторую строку. Хочется решение без вложенных циклов. [Solution]

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

Homework №3

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

2. Написать программу, которая считает количество непустых строк в исходном файле. Строка считается пустой, если состоит только из пробелов и табуляций (символ \t), или в ней нет символов вообще. [Solution]

3. Дан массив размером n, в нём есть нули, надо их все переместить в конец, при этом не создавая новый массив. [Solution]

4. Пользователи совершают действия, про каждое из них известно, сколько минут назад его сделали. Сколько пользователей совершили k действий за последние t минут? На вход подаётся 3 числа: n, k, t — число пользователей, необходимое число действий и временной промежуток. Затем в 2*n строках описывается каждый пользователь: для i пользователя указывается m_i — число действий, которое совершил пользователь, а затем m_i чисел — сколько минут назад совершалось каждое действие. [Solution]

Пример:
3 2 5
5
10 3 5 8 1
1
3
4
3 2 8 20
Ответ: 1 (только 3 пользователь совершил 2 действия за последние 5 минут).

Homework №4

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

2. Написать программу-телефонный справочник. При запуске программа должна читать данные из файла, если файла нет — начинать с пустой базы номеров. Формат представления данных в файле придумать самостоятельно. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции: [Solution]

0 - выйти
1 - добавить запись (имя и телефон)
2 - найти телефон по имени
3 - найти имя по телефону
4 - сохранить текущие данные в файл.

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

Homework №5

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

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

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

Homework №6

1. По содержимому памяти вывести значение типа double в экспоненциальной форме: sm*q{Sp}, где s — знак мантиссы, m — мантисса, q — основание системы счисления, S — знак порядка, p — порядок числа. Примеры допустимого вывода: [Solution]

Enter a number: -2.5
Result: -1.25*2^1
Enter a number: 12312.323
Result: +1.5029691162109375384*2^13

2. Ввести два числа, перевести в двоичное представление (в каком-либо из кодов) и в этом двоичном виде напечатать, сложить, вывести сумму в двоичном и десятичном виде (суммировать двоичные числа). [Solution]

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

Homework №7

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

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

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

Homework №8

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

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

Homework №9

1. Реализовать лексический анализатор, проверяющий, является ли введённая последовательность символов вещественным числом (вещественное число задаётся регулярным выражением (+ | -)? digit+ (. digit+)? (E(+ | -)? digit+)?, где digit – [0..9]). Реализовывать можно как больше нравится: либо через switch, либо таблицей переходов. [Solution]

Test №1

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

2. Отсортировать чётные позиции в массиве с помощью сортировки вставками. Массив произвольной длины. Реализовать два варианта ввода значений массива — с консоли и автоматическая генерация случайных чисел от 11 до 42. В случае ввода с консоли пользователь вводит числа массива, завершая их 0 (сам 0 служит только как символ завершения массива и сам в массив не входит). В случае генерации случайных чисел пользователь вводит размер массива. [Solution]

Test №2

1. Реализовать функцию нахождения i-го числа Фибоначчи (линейную по скорости и константную по памяти). [Solution]

2. Реализовать сортировку вставками односвязного линейного списка. [Solution]

3. 1953 год. В связи с усилением влияния Запада и необходимостью предпринять ответные меры, Иосиф Сталин разрабатывает новый эффективный алгоритм внутрипартийной чистки: сначала расстреливаются n самых опасных членов, а затем оставшиеся упорядочиваются в алфавитном порядке и первые m отправляются в Сибирь. Л.П. Берия уже успел провести предварительные работы: определил степень лояльности к СССР среди членов партии и предоставил списки генеральному секретарю. На входе файл формата "фамилия - степень лояльности". n и m вводятся с клавиатуры. Задача: определить, кто будет расстрелян, кого отправят в Сибирь, кто останется невредим. Пока невредим. [Solution]

Test №3

1. Написать программу, которая вводит с клавиатуры набор целых чисел (в любом порядке, конец — число 0), и выводящую числа из этого набора в порядке возрастания и без повторений, с указанием того, сколько каждое число раз встретилось в этом наборе. [Solution]

2. Написать программу поиска седловых точек двумерного массива. Седловая точка — это элемент, наименьший в своей строке и наибольший в своем столбце. [Solution]

3. Реализовать конечный автомат, проверяющий, является ли строка корректным номером группы на матмехе. Номер группы начинается с последних двух цифр года поступления, Дальше B (бакалавры), M (магистры) или S (специалисты), дальше номер группы (число от 1 до 10), дальше строка -mm. Например, 17B10-mm является корректным номером группы. [Solution]