Самостоятельная работа состоит в решении задач по темам, которые обсуждаются в лекциях. По каждой теме нужно решить одну задачу из предлагаемого списка. Номер задачи равен номеру студента в журнале по модулю 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. Должно быть реализовано определение ориентации треугольника, ориентирование треугольника (при необходимости изменение направления его обхода), вычисление площади и площади со знаком треугольника, его периметра, центра тяжести, а также вычисление описанной и вписанной окружностей. Для произвольной точки нужно уметь определять, лежит ли точка внутри или вне треугольника. Также нужно уметь вычислять пересечение треугольника и прямой, а также угол, под которым треугольник виден из заданной точки.

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

Сортировка

Лекция Алгоритмы сортировки (презентация)

Генерация случайных чисел

Скорость работы алгоритмов сортировки интересно оценивать на больших массивах, содержащих миллионы элементов. Для заполнения таких массивов мы используем генераторы случайных чисел. Древняя функция rand() из ANSI-библиотеки языка C недостаточно хороша (например, при генерации случайных точек в многомерном пространстве большая часть из них содержится в некоторой гиперплоскости). Для того, чтобы программа не работала детерминированно при разных запусках, раньше использовалась функция srand для установки начального элемента псевдослучайной последовательности, в качестве случайного значения функции srand обычно передавалось время в секундах с начала эпохи 1 января 1970 г., что также недостаточно для современных программ. В современной стандартной библиотеке языка C++ содержатся намного более качественные функции для генерации случайных чисел. Типичная схема генерации случайных целых и вещественных чисел в заданных диапазонах иллюстрируется следующей программой "randDevice.cpp":

#include <iostream>
#include <random>

int main() {
    std::random_device seed;
    std::mt19937 gen(seed());
    std::uniform_int_distribution<int> intRange(1, 100);
    std::uniform_real_distribution<double> realRange(-10., 10.);

    std::cout << "Random integer numbers:" << std::endl;
    for (int i = 0; i < 20; ++i) {
        int randNumber = intRange(gen);
        if (i > 0) {
            // Delimiter
            if (i%5 == 0)       // 5 numbers in a line
                std::cout << std::endl;
            else
                std::cout << ' ';
        }
        std::cout << randNumber;
    }
    std::cout << std::endl;

    std::cout << "Random real numbers:" << std::endl;
    for (int i = 0; i < 20; ++i) {
        double randNumber = realRange(gen);
        if (i > 0) {
            // Delimiter
            if (i%5 == 0)       // 5 numbers in a line
                std::cout << std::endl;
            else
                std::cout << ' ';
        }
        std::cout << randNumber;
    }
    std::cout << std::endl;

    return 0;
}

Описания функций для генерации случайных чисел содержатся в заголовочном файле random:

    #include <random>

    std::random_device seed;

    std::mt19937 gen(seed());

Однако обычно нам нужны числа в заданном диапазоне. Для этого можно применять объекты типа std::uniform_int_distribution<int> для генерации целых чисел или std::uniform_real_distribution<int> для генерации вещественных чисел:

    std::uniform_int_distribution<int> intRange(1, 100);
    std::uniform_real_distribution<double> realRange(-10., 10.);

        int randNumber = intRange(gen);

        double randNumber = realRange(gen);

Вот результат работы приведенной выше программы "randDevice.cpp":

    >g++ -o randDevice randDevice.cpp
    >./randDevice
    Random integer numbers:
    100 39 73 89 81
    78 58 91 10 61
    84 16 44 55 48
    93 15 67 54 30
    Random real numbers:
    -5.75583 -6.79703 9.89776 0.351352 -5.17714
    -3.1965 -5.16208 6.71477 2.46811 7.78662
    4.96462 8.28746 -1.036 -0.750713 5.14964
    -2.7142 8.38426 4.50047 3.19789 -6.55677

Задачи по теме "Сортировка"

Нужно решить одну задачу, номер которой совпадает по модулю 3 с номером студента в журнале. В качестве заготовки следует использовать файл "tstSort.cpp", содержащий функции генерации случайных массивов и их печати, а также прототипы функций сортировки разными методами. Реализация дана только для функции сортировки insertionSort и нескольких вспомогательных функций, таких как bubbleDown и merge, реализации остальных алгоритмов сортировки оставлена в качестве задач.

1. Написать функцию сортировки массива методом пирамиды HeapSort. Прототип функции:

   void heapSort(
       std::vector::iterator i0,
       std::vector::iterator i1
   );
   

2. Написать функцию сортировки массива методом слияния MergeSort, используя нисходящую (рекурсивную) схему реализации. Прототип функции:

   void mergeSortTopBottom(
       std::vector::iterator i0,
       std::vector::iterator i1,
       std::vector::iterator* tmpMemory = nullptr
   );
   

3. Написать функцию сортировки массива методом слияния MergeSort, используя восходящую (итеративную) схему реализации. Прототип функции:

   void mergeSortBottomTop(
       std::vector::iterator i0,
       std::vector::iterator i1,
       std::vector::iterator* tmpMemory = nullptr
   );