Практикум на ЭВМ ("Алгоритмы и структуры данных")
Список задач

Темы


Реализация классов на C++

  1. Реализовать класс "R3Vector", представляющий вектор в трехмерном пространстве. К обычным операциям добавляется векторное произведение. В качестве теста написать с использованием этого класса консольную программу, которая
  2. Реализовать класс "Complex", представляющий комплексное число (с вещественными компонентами типа double). Для комплексных чисел реализовать арифметические действия и преобразование числа в экспоненциальную форму (получения модуля и аргумента) и обратно. Воспользовавшись реализацией класса, написать программу, решающую в комплексных числах
  3. Реализовать класс "Polynomial", представляющий многочлен произвольной степени с операциями сложения, умножения и получения степени.
  4. Реализовать класс "Substitution", представляющий подстановку порядка n, т.е. биективное отображение конечного множества из n элементов в себя. Должны быть реализованы композиция подстановок, действие подстановки на элемент x, 0<=x<=n-1, четность подстановки.
  5. Реализовать класс "Matrix", представляющий прямоугольную матрицу порядка n, где n задается в конструкторе. Должны быть реализованы получение элемента матрицы с заданными индексами (в виде ссылки на элемент типа double), сумма и произведение матриц, единичная матрица, действие матрицы на вектор порядка n, транспозиция, элементарные преобразования, приведение к ступенчатому виду, вычисление определителя, обратной матрицы и т.д.
  6. Реализовать класс "Rotation", представляющий вращение трехмерного пространства, т.е. линейное ортогональное преобразование векторного пространства R3, сохраняющее ориентацию. (Как известно, любое такое преобразование -- это поворот вокруг некоторой оси.) Должны быть реализованы
    • конструктор по умолчанию (тождественное преобразование);
    • copy-конструктор;
    • конструктор, на вход которому подаются 3 координаты направляющего вектора оси вращения и угол поворота в радианах. Поворот происходит против часовой стрелки, если смотреть из конца вектора (т.е. по правилу правого винта);
    • композиция преобразований (operator*);
    • действие преобразования на вектор R3, вектор представляется массивом из трех элементов типа double.
  7. Реализовать класс "AffineTransformation", представляющий собой аффинное преобразование плоскости. Должны быть реализованы композиция (произведение) преобразований, действие преобразования на точку (class R2Point), а также нахождение по заданным двум треугольнокам преобразования, переводящего первый треугольник во второй.

Задачи по теме "Стековый калькулятор" (проект "StackCalc.zip")

  1. Добавить вычисление НОД двух целых чисел с помощью алгоритма Евклида.
  2. Добавить возведение в целую степень с помощью алгоритма быстрого возведения в степень.
  3. Добавить возведение в целую степень в кольце вычетов по модулю m с помощью алгоритма быстрого возведения в степень. Число m является аргументом операции (который извлекается из стека).
  4. Добавить вычисление математических функций exp, sin, cos, tg, arctg, arcsin, arccos.

Задачи по теме "Графика" (проект "Func.zip")

  1. Функция от одного аргумента задается непосредственно в тексте программы. Нарисовать:
  2. Пользователь отмечает кликами мыши 3 точки. После каждого клика программа рисует крестик в соответствующей точке. После третьего нажатия прорамма рисует параболу, проходящую через эти 3 точки.
    Перерисовка окна должна быть корректной.
  3. Такая же задача, только после каждого n-го клика программа рисует график интерполяционного многочлена степени n-1, проходящего через отмеченные точки.
  4. Пользователь отмечает нажатиями левой клавиши мыши произвольные точки, никакие 3 из них не лежат на одной прямой. Программа рисует крестики в отмеченных точках. По нажатию правой клавиши программа должна отметить последнюю точку и нарисовать ломаную без самопересечений с вершинами в отмеченных точках.
  5. Пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник и окружность, описанную вокруг него.
  6. Та же задача для вписанной окружности.
  7. Пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник ABC, а также медиану, биссектрису и высоту, проведенные из вершины A. Треугольник рисуется черным цветом, медиана красным, биссектриса синим, высота зеленым (медиана, биссектриса и высота проводятся до пересечения с прямой BC).
  8. Дан куб с координатами вершин +-1 (центр куба в начале координат). Дан трехмерный вектор V=(vx, vy, vz), где vy отлично от нуля. Нарисовать проекцию куба на плоскость XZ параллельно вектору проектирования V.
  9. Программа вводит с консоли точку, через которую проходит плоскость, и вектор нормали к плоскости. После этого программа должна создать графическое окно, нарисовать в кабинетной проекции черным цветом куб с координатами вершин плюс-минус 1 (без удаления невидимых линй), а также красным цветом сечение куба заданной плоскостью.

Задачи по теме "Инвариант цикла"

Во всех задачах надо реализовать соответствующий алгоритм на основе схемы построения цикла с помощью инварианта. Инварианты перечисленных ниже алгоритмов рассматривались на лекциях. Во всех случаях требуется, чтобы время работы алгоритма было бы полиномиальным, т.е. ограничивалось бы сверху полиномом от длины входа (длина входа — логарифм от максимального входного числа).

  1. Вычислить НОД двух целых чисел с помощью алгоритма Евклида.
  2. Вычислить НОД d двух целых чисел m, n и его представление в виде линейной комбинации исходных чисел
      d = u*m + v*n
    с помощью расширенного алгоритма Евклида. (Даны числа m, n, требуется вычислить числа d, u, v.)
  3. Вычислить обратный элемент y к элементу x в кольце вычетов по модулю m с помощью расширенного алгоритма Евклида, т.е. найти y такой, что yx≡1 (mod m).
  4. С целыми числами разрешается выполнять операции сложения, вычитания, удвоения, деления пополам и проверки четности. Вычислить произведение двух целых чисел.
  5. С целыми числами разрешается выполнять операции сложения, вычитания, удвоения, деления пополам и проверки четности. Вычислить частное и остаток от деления двух целых чисел.
  6. Вычислить с заданной точностью логарифм вещественного числа по заданному основанию, большему единицы, не используя разложение логарифма в ряд (применив рассказанную на лекциях схему построения цикла с помощью инварианта).

Задачи по теме "Текстовый редактор" (проект "TEdit.zip")

  1. Добавить команду "удалить текущее слово и пробелы за ним", которая должна выполняться по нажатию Ctrl+A. Словом считается любая связная последовательность символов, отличных от пробелов. Если курсор стоит на пробеле, то должны быть удалены все пробелы до первого слова правее курсора (само слово при этом не удаляется).
  2. Добавить команды табуляции по словам:
  3. Добавить команду "найти парную скобку", которая должна выполняться по нажатию Ctrl+"[" (квадратная скобка). При этом, если курсор стоит на скобке, он должен перемещаться на парную скобку. Скобка может быть круглой, квадратной или фигурной, открывающей или закрывающей. Если команда не может быть выполнена, курсор должен оставаться на месте.
  4. Реализовать команды
    Команда "добавить строку в буфер" должна очищать буфер, если после предыдущего добавления была хотя бы раз выполнена команда "вставить строки из буфера".
  5. Реализовать команды
    Команда "добавить символ в буфер" должна очищать буфер, если после предыдущего добавления была хотя бы раз выполнена команда "вставить символы из буфера".
  6. Добавить команду откатки на одно действие назад для следующих двух действий: команда выполняется нажатием Ctrl+Z.
  7. Добавить команды
  8. Добавить команду "отформатировать абзац". Курсор стоит на первой строке абзаца и не должен менять положения после выполнения команды. Форматированные строки должны быть по возможности не длиннее 63 символов, отступов слева и красных строк нет, все группы пробелов заменены на один пробел, выравнивать по правому краю не надо. Строки могут разрезаться только по пробелам между словами. Абзац заканчивается пустой строкой.
  9. Добавить команду "заменить символ латинского регистра символом русского регистра, нарисованным на той же клавише", выполняется нажатием Ctrl+R, и обратную команду, выполняется по Ctrl+E. В обоих случаях курсор передвигается на одну позицию вправо. Соответствие между буквами определяется переключением латинского и русского регистров (в дисплейном классе клавишей "CapsLock", или "Alt+клавиша" в Микромире) при одной и той же клавише. Прописные и строчные символы различаются.

Задачи по теме "Красно-черные деревья" (проект "TreeSet.zip")

  1. Напечатать высоту и черную высоту RB-дерева.
  2. Найти путь минимальной длины от корня к некоторому листу и напечатаь его.
  3. Найти путь максимальной длины от корня к некоторому листу и напечатаь его.
  4. Напечатать все поддеревья, содержащие ровно n узлов.
  5. Найти путь от корня к некоторому листу, содержащий максимальное количество красных вершин.
  6. Найти путь от корня к некоторому листу, содержащий минимальное количество красных вершин.
  7. Ввести значения в 2-х вершинах и напечатать простой путь из одной вершины в другую.
  8. Среди всех поддеревьев, содержащих n узлов, найти и напечатать поддерево с максимальной суммой значений вершин.
  9. Среди вершин, отстоящих на расстояние n от корня, найти вершину с максимальным значением.
  10. Найти сумму значений вершин, отстоящих на расстояние n от корня.
  11. Найти и напечатать все максимальные сбалансированные поддеревья.
  12. Найти и напечатать все максимальные почти сбалансированные поддеревья.