/SPBU_Homework_Sem1

Домашнее отечественное на 1-ый семестр.

Primary LanguageC++Apache License 2.0Apache-2.0

  • Домашняя работа 1. 14.09.18

    • Написать программу, считающую значение формулы x4 + x3 + x2 + x + 1 за два умножения.

      Решение 1.1

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

      Решение 1.2

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

      Решение 1.3

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

      Решение 1.4

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

      Решение 1.5

    • Заданы две строки: S и S1. Найти количество вхождений S1 в S как подстроки.

      Решение 1.6

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

      Решение 1.7

    • Написать программу, считающую количество нулевых элементов в массиве.

      Решение 1.8

  • Домашняя работа 2. 21.09.18

    • Реализовать вычисление чисел Фибоначчи рекурсивно (и убедиться, что при n ~ 37 уже заметно медленно), реализовать итеративно, почувствовать разницу.

      Решение 2.1

    • Реализовать возведение в степень --- в лоб (за линейное время) и за О(log n).

      Решение 2.2

    • Написать сортировки пузырьком и подсчётом.

      Решение 2.3

    • Написать программу, которая заполняет массив случайными значениями (с использованием функции rand из stdlib.h), потом преобразует его без использования дополнительных массивов так, что в начале массива будут элементы, меньшие первого, а в конце --- большие либо равные первому. Программа должна работать за линейное время.

      Решение 2.4

  • Домашняя работа 3. 28.09.18

    • Реализовать qsort, который для сортировки кусков массива размером меньше 10 использует сортировку вставкой.

      Решение 3.1

    • Получить с клавиатуры 2 числа, n и k (1 <= n <= 5000, 1 <= k <= 300000), сгенерировать массив из n чисел от 0 до 109, сгенерировать k целых чисел от 0 до 109 , для каждого из них проверить, содержится ли оно в массиве. Надо придумать алгоритм с временной сложностью O(n log n + k log n), или лучший.

      Решение 3.2

    • Найти наиболее часто встречающийся элемент в массиве быстрее, чем за O(n2 ).

      Решение 3.3

  • Домашняя работа 4. 05.10.18

    • Ввести два числа, перевести в двоичное представление в дополнительном коде и напечатать, сложить в столбик в двоичном представлении, вывести сумму, перевести в десятичное, вывести сумму в десятичном виде. Все сообщения писать по-русски (рекомендуется использовать функцию setlocale, чтобы сообщения выводились по-русски и под Windows тоже).

      Решение 4.1

    • Переделать задачу 3 из прошлого задания так, чтобы сортировка была в отдельном модуле и читала входные данные из файла.

      Решение 4.2

    • Написать программу - телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции:

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

      При запуске программа должна читать данные из файла, если файла нет - начинать с пустой базы номеров. Размер базы ограничен сотней записей.

      Решение 4.3

  • Домашняя работа 5. 19.10.18

    • Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:

      • 0 – выйти
      • 1 – добавить значение в сортированный список
      • 2 – удалить значение из списка
      • 3 – распечатать список

      Все операции должны сохранять сортированность. Начинаем с пустого списка.

      Решение 5.1

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

      Решение 5.2

  • Домашняя работа 6. 26.10.18

    • Написать программу для вычисления арифметического выражения в постфиксной форме. С клавиатуры вводится последовательность цифр (для простоты) и операций +, -, *, /, представляющая выражение в постфиксной форме, должен выводиться результат вычисления. Например, на тесте 9 6 - 1 2 + * должно получиться 9.

      Решение 6.1

    • Написать программу проверки баланса скобок в строке, скобки могут быть трёх видов: (), [], {}. Скобочная последовательность вида ({)} считается некорректной, ({}) - корректной.

      Решение 6.2

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

      Решение 6.3

    • Реализовать сортировку слиянием. Во входном файле последовательность записей "имя - номер телефона". Программа должна отсортировать эти записи либо по имени, либо по номеру телефона, в зависимости от выбора пользователя, и вывести результат на экран. Количество записей заранее неизвестно, так что надо реализовывать списками на указателях.

      Решение 6.4

  • Домашняя работа 7. 02.11.18

    • Реализовать АТД "множество" на основе двоичного дерева поиска. Программа должна позволять в интерактивном режиме добавлять значения целого типа в множество, удалять значения, проверять, принадлежит ли значение множеству, печатать текущие элементы множества в возрастающем и убывающем порядках.

      Решение 7.1

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

      Решение 7.2

  • Домашняя работа 8. 09.11.18

    • Реализовать ассоциативный массив с ключами и значениями типа string на основе АВЛ-дерева. Должны поддерживаться следующие операции:

      • Добавить значение по заданному ключу в ассоциативный массив. Если такой ключ уже есть, значение заменяется на новое.
      • Получить значение по заданному ключу из ассоциативного массива. Если такого ключа нет, возвращается пустая строка.
      • Проверить наличие заданного ключа.
      • Удалить заданный ключ и связанное с ним значение из ассоциативного массива. Если такого ключа нет, функция ничего не делает.

      Ассоциативный массив должен быть реализован отдельным модулем.

      Решение 8

  • Домашняя работа 9. 16.11.18

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

      Решение 9.1

    • Написать мейкфайл и собрать какую-либо из задач д/з 6 в консоли с помощью утилиты make (или nmake или mingw32-make), выложить мейкфайл и приложить скриншот успешной сборки.

      Решение 9.2

  • Домашняя работа 10. 23.11.18

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

      Решение 10

  • Домашняя работа 11. 07.12.18

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

      Решение 11.1

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

      Решение 11.2