• Домашняя работа 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