Филиал МГУ в г. Душанбе-2025
Алгоритмы и структуры данных

Реализация на языке С++

Лекции и практические занятия

Самостоятельная работа состоит в решении задач по темам, которые обсуждаются в лекциях. По каждой теме нужно решить одну задачу из предлагаемого списка. Номер задачи равен номеру студента в журнале по модулю n, где n — число задач по данной теме. Решения задач присылайте мне на электронную почту в виде одного или нескольких файлов, присоединенных к письму (если файлов много, то лучше присылать zip-архив с файлами в поддиректории). Адрес моей электронной почты:
vladibor266 (собака) gmail.com
Тема письма должна начинаться со слов "Душанбе 2025".

Журнал руппы ПМИиИ-4, весенний семестр 2025 г.

Записи лекций на виртуальной доске

Тема 1. Классы для поддержки двумерной графики и геометрии

Мы используем классы R2Vector (вектор на плоскости) и R2Point (точка). Библиотека классов представленя двумя файлами:
R2Graph.h
R2Graph.cpp

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

Пример программы, вычисляющей окружность, вписанную в треугольник:
"incircle.cpp"

Список задач на тему "Геометрия на плоскости"

  1. Вычислить окружность, описанную вокруг треугольника.
  2. Вычислить точку Жергона треугольника.
  3. Вычислить точку Нагеля треугольника.
  4. Вычислить точку Лемуана треугольника.

Тема 2. Классы в C++

Примеры классов

Рассмотренные ниже классы специально не реализованы до конца, чтобы можно было решать задачи.

  1. Класс прямоугольных матриц: описание класса — файл "Matrix.h", реализация неинлайновых методов — файл "Matrix.cpp", тестовая программа — файл "matrixTest.cpp".
  2. Библиотека классов для 2-мерной графики на плоскости: файлы "R2Graph.h", "R2Graph.cpp",
  3. Класс "Многочлены на полем вещественых чисел": файлы "Polynomial.h", "Polynomial.cpp", тестовая программа — файл "PolynomialTest.cpp". Архив всех файлов: "Polynomial,zip".
  4. Класс "Контур на плоскости". Контур представляет собой замкнутую ломаную без самопересечений, т.е. многоугольник на плоскости, не обязательно выпуклый. Направление обхода контура определяет его ориентацию: положительную, если обход против часовой стрелки (CCW — Counter Clockwise), отрицательную, если по часовой (CW). Вершины многоугольника хранятся как объекты типа R2Point в динамическом массиве типа std::vector<R2Point>.

    Помимо класса R2Contour, реализован также класс R2Polyline, представляющий незамкнутую ломаную на плоскости. Класс R2Contour наследуется из класса R2Polyline, а класс R2Polyline в свою очередь наследуется из класса std::vector<R2Point>.

    Файлы проекта: "R2Contour.h", "R2Contour.cpp", тестовая программа — файл "R2ContourTest.cpp", классы для поддержки 2-мерной геометрии — "R2Graph.h", "R2Graph.cpp", Архив всех файлов: "R2Contour,zip".

Список задач на тему "Классы в C++"

Студент должен решить ту задачу, номер которой совпадает по модулю 4 с его номером в журнале.

  1. Реализовать до конца класс Матрицы. Должны быть реализованы операции над матрицами (сложение, вычитание, умножение), вычисление ранга и определителя матрицы, вычисление обратной матрицы. Для квадратной невырожденной матрицы A и вектора B должно быть реализовано решение линейной системы уравнений A·X = B.
  2. Реализовать до конца класс многочленов над полем вещественных чисел. Должны быть реализованы операции над многочленами, включая сложение, вычитание и умножение двух многочленов, умножение многочлена на число, деление с остатком двух многочленов, а также вычисление производной многочлена, значения многочлена в заданной точке и наибольшего общего делителя двух многочленов.
  3. Реализовать до конца класс "Контур на плоскости". Вершины ломаной, определяющей контур, надо хранить как объекты типа R2Point. Должно быть реализовано определение ориентации контура, ориентирование контура (при необходимости изменение направления его обхода), вычисление площади и площади со знаком контура, его периметра, центра тяжести вершин и центра тяжести как плоской фигуры, определение, лежит ли заданная точка внутри контура, вычисление угла, под которым контур виден из заданной точки, и другие естественные для этого класса методы.
  4. Реализовать класс "Треугольник на плоскости". Вершины треугольника надо хранить как объекты типа R2Point. Должно быть реализовано определение ориентации треугольника, ориентирование треугольника (при необходимости изменение направления его обхода), вычисление площади и площади со знаком треугольника, его периметра, центра тяжести, а также вычисление описанной и вписанной окружностей. Для произвольной точки нужно уметь определять, лежит ли точка внутри или вне треугольника. Также нужно уметь вычислять пересечение треугольника и прямой, а также угол, под которым треугольник виден из заданной точки.

Для реализованного класса надо написать тестовую консольную программу, которая вводит объект или несколько объектов класса с клавиатуры, вызывает тестируемые методы и печатает результаты.