Алгоритмы и структуры данных
http://mech.math.msu.su/~vvb/
Что требуется:
1) С++ компилятор,
2) make,
3) для оконных приложений и графики
нужно установить QT (кьют) + QtCreator
free-вариант над MinGW-64
Я советую под MS Windows установить
систему CygWin (для неграфических, консольных
приложений). В cygwin надо установить следующие пакеты:
1) gcc-g++
2) make
3) gdb
4) unzip, zip
5) wget,
6) ssh, ...
7) python3
В MS Windows есть оболочка PowerShell или
древняя CMD, но они очень неудобные.
В cygwin оболочка bash полностью такая же, как в Unix
(Linux) и в OS-X (Apple -- это тоже вариант Unix).
Под MS Windows можно установить Linux как вторую
систему, лучше всего WSL2 (Windows System for Linux),
которая эмулирует Linux Ubuntu.
Пришлите мне список студентов
на адрес vladibor2016@yandex.ru
Используем С++ со стандартной библиотекой STL
Структура данных, или ADT (Abstract Data Type) --
классы, которые организуют хранение данных и работу
с ними (поиск, добавление, удаление, циклы "для каждого"
и т.д.). Структура данных в STL С++ обычно называется
контейнером, контейнеры зависят от параметров
(тип элементов в структуре, размер, специальные функции
и т.п.), которые задаются с помощью механима template
(шаблоны).
Библиотека STL содержится в пространстве имен
namespace std;
#include <iostream>
#include <vector>
#include <string>
#include <map>
std::vector<double> a(100);
std::map<std::string, int> notebook;
1. Вспомним еще раз классы
Используя классы, мы
1) пользуемся готовыми библиотеками классов,
написанными другими людьми, для решения
наших задач;
2) создаем свои собственные классы.
Как пример, рассмотрим геометрию на плоскости R2
и классы для решения геометрических задач.
У нас есть небольшая библиотека R2Graph,
реализующая геометрию на плоскости. В ней
есть классы R2Vector и R2Point
R2Vector u, v, w;
R2Point p, q, t;
v = q - p; // вектор из точки p в точку q
t = p + w; // точка t получается из точки p
// сдвигом на вектор w
Задача 1: найти расстояние от точки t
до прямой (p, v)
(прямая задается точкой p и
направляющим вектором v).
R2Point t;
R2Point p; R2Vector v;
. . .
R2Vector n = v.normal();
n.normalize();
double d = (t - p)*n;
double dist = fabs(d);
Задача 2: найти точку пересечения двух прямых.
Дано: две прямые (p1, v1) и (p2, v2).
Вычислить точку q пересечения этих двух
прямых.
Поскольку q лежит на первой прямой, то
q = p1 + v1*t, где t <- R
Пусть n -- нормаль ко второй прямой
R2Vector n = v2.normal()
Тогда, т.к. q лежит на второй прямой, то
вектор q - p2 перпендикулярен нормали n:
(q - p2)*n = 0
Подставим q из первого уравнения
(p1 + v1*t - p2)*n = 0
(p1 - p2)*n + t*(v1*n) = 0
t*(v1*n) = (p2 - p1)*n
t = ((p2 - p1)*n) / (v1*n)
R2Point intersectLines(
const R2Point& p1, const RVector& v1,
const R2Point& p2, const R2Vector& v2
) {
R2Vector n = v2.normal();
double t = ((p2 - p1)*n) / (v1*n);
return p1 + v1*t;
}
Задача:
дан треугольник, заданный тремя точками a, b, c.
Найти вписанную окружность (центр и радиус).
Вот программа, решающая эту задачу -- файл "incircle.cpp".
Обратите внимание, что мы используем только методы
классов вектор и точка и не используем вычислений
с координатами.
#include <iostream>
#include "R2Graph.h"
void inCircle(
const R2Point& a,
const R2Point& b,
const R2Point& c,
R2Point& center,
double& radius
);
int main() {
std::cout << "Enter 3 vertices of triangle:"
<< std::endl;
R2Point a, b, c;
std::cin >> a >> b >> c;
R2Point center;
double radius;
inCircle(a, b, c, center, radius);
std::cout << "Inscribed circle:" << std::endl;
std::cout << "center = " << center
<< ", radius = " << radius << std::endl;
return 0;
}
void inCircle(
const R2Point& a,
const R2Point& b,
const R2Point& c,
R2Point& center,
double& radius
) {
R2Vector ab = b - a;
ab.normalize();
R2Vector ac = c - a;
ac.normalize();
R2Vector bisa = ab + ac;
R2Vector ba = a - b;
ba.normalize();
R2Vector bc = c - b;
bc.normalize();
R2Vector bisb = ba + bc;
intersectStraightLines(
a, bisa,
b, bisb,
center
);
radius = center.distanceToLine(a, b - a);
}
При компиляции этой программ мы подключаем также
библиотеку R2Graph (файлы "R2Graph.h" и "R2Graph.cpp"),
определяющую классы R2Vector и R2Point и некоторые функции
для решения элементарных геометрических задач на плоскости
R2 (например, вычисление точки пересечения двух прямых
или нахождение расстояния от точки до прямой).
Команда компиляции в Linux или в CygWin следующая:
g++ -o incircle incircle.cpp R2Graph.cpp
Вот пример работы этой программы:
/home/vvb/Dush2025>./incircle
Enter 3 vertices of triangle:
0 0
4 0
4 3
Inscribed circle:
center = (3, 1), radius = 1
------------------------------------
26 Feb 2025
Замечательные точки треугольника
Мы знаем по школьному курсу следующие точки тругольника:
1) центр вписанной окружности (пересечение биссектрис);
2) центр описанной окружности (circumcenter =
точка пересечения серединных перпендикуляров);
3) точка пересечения медиан треугольника (центр тяжести);
4) точка пересечения высот треугольника (ортоцентр).
Теорема Чевы (Ceva)
Три отрезка из вершин треугольника к противоположным
сторонам пересекаются в одной точке тогда и только тогда,
когда выполняется равенство:
x/y * z/t * u/w = 1
где x, y, z, t, u, w -- длины отрезков, на которое
делятся стороны треугольника, в порядке обхода против
часовой стрелки.
Другие популярные популярные точки (пересечения чевиан):
5) точка Жергона;
6) точка Нагеля;
7) точка Лемауна.
Изогональное сопряжение
Пусть x -- точка внутри треугольника.
Проведем через нее 3 чевианы.
Потом каждую из чевиан отразим симметрично относительно
биссектрисы, проведенной из той же вершины.
Три симметричных отрезка, полученные из чевиан, тоже
будут пересекалься в одной точке y. Точка y изогонально
симметрична исходной точке x.
Точка Жергона -- это пересечение чевиан, проведенных
к точкам касания вписанной окружности сторон треугольника.
Точка Нагеля -- это пересечение чевиан, проведенных
к точкам касания трех внешне-вписанных окружностей.
Точка Лемуана -- это точка, изогонально симметричная
центру тяжести треугольника, т.е. пересечение трех
симмедиан. Симмедиана -- это линия, зеркально симметричная
медиане относительно биссектрисы, выходящей из той же
вершины треугольника.
Замечательные свойства центра тяжести и точки Лемуана:
1) центр тяжести минимизирует сумму квадратов расстояний
от точки до вершин треугольника;
2) точка Лемуана минимизирует сумму квадратов расстояний
от точки до сторон треугольника.
Для примера решим задачу 2:
вычислить точку Жергона треугольника.
Функция, вычисляющая точку Жергона, использует
функцию inCircle, вычисляющую окружность, вписанную
в треугольник (ее центр и радиус), которую мы
уже реализовали ранее.
R2Point gergonne(
const R2Point& a,
const R2Point& b,
const R2Point& c
) {
R2Point inCenter;
double radius;
inCircle(a, b, c, inCenter, radius);
// std::cout << "Incircle center: " << inCenter << std::endl;
R2Point cev_a;
intersectStraightLines(
inCenter, (c - b).normal(),
b, c - b,
cev_a
);
// std::cout << "cev_a: " << cev_a << std::endl;
R2Point cev_b;
intersectStraightLines(
inCenter, (a - c).normal(),
c, a - c,
cev_b
);
// std::cout << "cev_b: " << cev_b << std::endl;
R2Point g;
intersectStraightLines(
a, cev_a - a,
b, cev_b - b,
g
);
return g;
}
Вот пример работы этой программы:
/home/vvb/Dush2025>g++ -o gergonne gergonne.cpp R2Graph.cpp
/home/vvb/Dush2025>./gergonne
Enter 3 vertices of triangle:
0 0
5 1
3 5
Gergonne point: (3.11423, 1.99903)
--------------------------------------
12 Mar 2025
Классы в C++
Прошлы раз мы рассмотрели реализацию класса Complex,
представляющего комплексные числа.
Внутреннее прелставление комплексного числа
возможно в двух вариантах:
1) объект хранит вещественную и мнимую части
комплексного числа
class Complex {
private:
double re;
double im;
. . .
};
2) объект хранит абс. величину (модуль) и аргумент
(угол вектора с осью абсцисс) комплексного числа,
такое представление называется экспоненциальным
z = r*e^{i phi}
или полярным.
class Complex {
private:
double r;
double phi;
. . .
};
Каждое из этих представлений имеет свои плюсы и минусы.
В декартовом представлении удобно реализуются операции
+ и -, в экспоненциальном -- операции * и /.
Например, в полярном представлении оператор +=
реализуется следующим образом:
class Complex {
private:
double r;
double phi;
public:
double real() const {
return r*cos(phi);
}
double imag() const {
return r*sin(phi);
}
Complex& operator+=(const Complex& z) {
double re = real() + z.real();
double im = imag() + z.imag();
r = sqrt(r*r + im*im);
phi = atan2(im, re);
return *this;
}
Complex& operator*=(const Complex& z) {
r *= z.r;
phi += z.phi;
phi = fmod(phi, 2.*M_PI);
if (phi < -M_PI)
phi += 2.*M_PI;
else if (phi > M_PI)
phi -= 2.*M_PI;
return *this;
}
. . .
};
Добавим в класс Complex несколько статических методов.
Обычные методы применяются к объектам класса, например
Complex z;
double = z.real();
Статические методы не применяются к объектам, это просто
как бы функции, лишь номинально причисленные к классу.
В классе Complex есть конструктор, который по двум
вещественным числам создает объект, у которого комплексная
и мнимая части равны двуи переданным числам.
double a, b;
. . .
Complex z = Complex(a, b);
double r, phi;
// Как создать комплексное число тоже по двум
// вещественным числам, но которые определяют не
// декартовы координаты числа, а модуль и аргумент?
// Используем статический метод polar
Complex z2 = Complex::polar(r, phi);
Реализация этого статического метода внутри класса:
class Complex {
private:
double re;
double im;
public:
. . .
static Complex polar(double r, double phi) {
return Complex(r*cos(phi), r*sin(phi));
}
};
Для примера применения класса Complex
решим кубическое уравнение:
a*x^3 + b*x^2 + c*x + d = 0
Можно считать, что a = 1, иначе просто разделим
уравнение на a.
x^3 + a*x^2 + b*x + c = 0
Можно свести уравнение к виду, когда коэффициент
при x^2 равен нулю. Иначе делаем замену типа сдвига:
x = x' + s
Получим
(x' + s)^3 + a*(x' + s)^2 + b(x' + s) + c = 0
x'^3 + 3*sx'^2 + ... + a*x'^2 + ... = 0
x'^3 + (3*s + a)*x'^2 + ... = 0
откуда получаем
s = -a/3
То есть при замене
x = x' - a/3
член при х'^2 сокращается.
Окончательно уравнение примет вид
x^3 + a*x + b = 0
Мы свели исходную задачу к уравнению такого вида.
Единственное, что нужно помнить для вывода формулы Кардано --
это замена
x = u + v
где u, v -- две независимые переменные.
(Свели простое уравнение от одной переменной к
более сложному уравнению от двух переменных.)
Подставим и раскроем скобки:
(u + v)^3 + a*(u + v) + b = 0
Считаем, что b != 0.
u^3 + 3*u^2*v + 3*u*v^2 + v^3 + a*(u + v) + b = 0
u^3 + v^3 + b + 3*u*v*(u + v) + a*(u + v) = 0
u^3 + v^3 + b + (u + v)*(3*u*v + a) = 0
============= --------------------
Приравняем отмеченные части к нулю и решим систему
из двух уравнений с двумя неизвестными:
{ u^3 + v^3 + b = 0
{ (u + v)*(3*u*v + a) = 0
Поскольку b != 0 и x = 0 не является решением, x = u + v,
то можем сократить второе уравнение на (u + v):
{ u^3 + v^3 + b = 0
{ 3*u*v + a = 0
Из второго уравнения выражаем v:
v = -a/(3*u)
и подставляем в первое уравнение:
u^3 - a^3/(27*u^3) + b = 0
Сделаем замену
u^3 = y
Получим
y - a^3/(27*y) + b = 0
Сведем к квадратному, домножив на y:
y^2 + b*y - a^3/27 = 0
Дискриминант уравнения:
d = b*b + 4*a^3/27
Достаточно получить 1 корень:
y = (-b + sqrt(d))/2
Переходя обратно, получим 3 корня исходного
уравнения, поскольку уравнение
u^3 = y
имеет ровно 3 комплексных решения (3 кубических корня
из y).
Московское время 13:45.
Перерыв до 13:55
-----------------------------------
Мы реализовали вычисление трех корней кубического уравнения
в файле cubicEq.cpp
Тест:
рассмотрим уравнение
(x - 2)*(x - 3)*(x + 5) = 0
раскроем скобки:
(x^2 - 5*x + 6)*(x + 5) = 0
x^3 - 5*x^2 + 6*x + 5*x^2 - 25*x + 30 = 0
======= =====
x^3 - 19*x + 30 = 0
Корни уравнения: 2, 3, -5.
Работа нашей программы:
Solve a cubic equation of form
x^3 + a*x + b == 0
with complex coefficients
Enter complex a, b:
-19 0
30 0
Solutions of the cubic equation:
3 + 4.44089e-16*i
-5 + 0*i
2 + 0*i
Ответ правильный!
Еще пример: решим уравнение
x^3 - x - 1 = 0
Solve a cubic equation of form
x^3 + a*x + b == 0
with complex coefficients
Enter complex a, b:
-1 0
-1 0
Solutions of the cubic equation:
1.32472 + 0*i
-0.662359 + 0.56228*i
-0.662359 + -0.56228*i
Ответ также правильный.
Проверим с помощью SageMath:
sage: res = solve(x^3 - x - 1, x)
sage: res
[x == -1/2*(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)*(I*sqrt(3) + 1)
- 1/6*(-I*sqrt(3) + 1)/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3),
x == -1/2*(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)*(-I*sqrt(3) + 1)
- 1/6*(I*sqrt(3) + 1)/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3),
x == (1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3) +
1/3/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)]
sage: res[0].rhs()
-1/2*(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)*(I*sqrt(3) + 1) - 1/6*(-I*sqrt(3) + 1)/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)
sage: res[0].rhs().n()
-0.662358978622373 - 0.562279512062301*I
sage: res[1].rhs().n()
-0.662358978622373 + 0.562279512062301*I
sage: res[2].rhs().n()
1.32471795724475
Ответы совпали.
В следующий раз мы рассмотрим еще несколько классов:
матрицы, треугольник на плоскости, прямоугольник на
плоскости, многоугольник (или контур) на плоскости.
Также рассмотрим, как надо использовать контейнеры
из стандартной библиотеки классов STL языка C++
и почему не надо использовать базовые конструкции
языка C/C++, а использовать именно контейнеры.
Также будут даны задачи на классы.
------------------------------------------------
Zoom-сессия в воскресенье 16 марта в 11:00
московского времени.
------------------------------------------------
19 Mar 2025
Классы в C++
Класс Матрица
Неправильное решение:
матрица размера m*n (m строк, n столбцов)
хранится как массив строк.
Каждая строка захватывается по-отдельности
в динамической памяти и представляет собой массив длины n.
Кроме того, хранится массив указателей на начала строк
длины m.
double **a = new double*[m];
for (int i = 0; i < m; ++i) {
a[i] = new double[n];
}
// После этого элемент матрицы с индексами i, j
// записывается как a[i][j]
// Удаление матрицы (освобождение памяти):
for (int i = 0; i < m; ++i) {
delete[] a[i];
}
delete[] a;
Это дурацкий способ работы с матрицами.
Почему он плохой?
1. Чтение/запись требует двух обращений к памяти:
a[i][j]
сначала читаем p = a[i] -- указатель на начало
i-й строки;
затем читаем сам элемент p[j].
2. Плохо используется кэш-память процессора.
Выгоднее располагать элементы матрицы в непрерывном
сегменте памяти.
Если вы будете использовать эту реализацию, то я не
буду засчитывать подобные решения.
--------------------------------------------------
Правильный способ реализации матрицы:
храним элементы матрицы в непрерывном линейном массиве
по строкам (в Фортране по столбцам, в Python
в модуле numpy возможны оба варианта, по умолчанию
используется вариант по строкам).
Пример: матрица размера 3*4 (m = 3, n = 4)
a00 a01 a02 a03
a10 a11 a12 a13
a20 a21 a22 a23
хранится в линейном массиве в следующем порядке:
a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23
--------------- =============== ---------------
строка 0 строка 1 строка 2
Соответственно элемент матрицы с индексами i, j
записывается как a[i*n + j].
Так хранятся, к примеру, изображения в видео-памяти
компьютера.
Напишем 2 варианта реализации матрицы.
Первый вариант соттветствует версии языка C++
1985-го года, до того, как была введена стандартная
библиотека STL языка C++ в 1998 г.
===============================================
26 Mar 2025
Если мы явно захватываем какие-то ресурсы при создании
объекта, то обязательно надо
1) определить copy-конструктор;
2) определить оператор копирования
Matrix& operator=(const Matrix& matr);
3) определить move-конструктор
Matrix& operator=(Matrix&& matr);
4) определить оператор перемещения (move)
Matrix& operator=(Matrix&& matr); // r-value
5) определить деструктор
~Matrix();
Это так называемое "правило 5-ти" (раньше оно называлось
"правиле трех", когда в C++ не было move-семантики).
Еще есть в C++ правило RAII --
Resouce Allocation Is Initialization:
захват ресурсов удбно выполнять в конструкторе,
освобождение в деструкторе.
Большинтсво современных не слишком квалифицированных
программистов на C++ этих правил не знают, потому что
они вместо базовых массивов языка C/C++ используют
конетейнерные классы из стандартной библиотеки.
Для этого, например, мы используем вместо базовых
и указателей на их начала мы используем класс
"динамический массов" из стандартной библиотеки STL.
Например, наш класс Матрица вместо старой реализации:
class Matrix {
private:
int m; // Number of rows
int n; // Number of columns
double *a;
. . .
};
используем правильную" реализацию с современной точки
зрения (читайте книгу Б.Страуструпа
"Язык программирования C++"). Вместо массива, который
задается указателем на его начальный элемент
double *a;
мы используем класс std::vector<double> из стандартной
библиотеки.
#include <vector>
class Matrix {
private:
int m; // Number of rows
int n; // Number of columns
// double *a;
std::vector<double> a;
. . .
};
Что нам это дает?
!!! Не нужно определять эти 5 методов, поскольку
компилятор сгенерирует их автоматически и они будут
работать правильно, поскольку для всех контейнерных
классов эти операции уже определены и работают
правильно (в отличие от копирования указателей, что
всегда приводит к катастрофе).
Рассмотрим самый важный класс из стандартной библиотеки:
динамический массив.
std::vector<double> a;
+--------------------------+-----------------+
| size() |x *** мусор **** |
+--------------------------+-----------------+
capacity()
Добавление элемента в конец динамического массива:
a.push_back(x);
Мнемоника:
начало структуры данных называется front()
конец структуры данных называется back()
Добавить в конец контейнера a:
a.push_back(x);
Удалить из конца контейнера a:
a.pop_back();
Удалить из начала контейнера a:
a.pop_front();
Методы begin() и end() возвращают вовсе не
элементы в начале и в конце контейнера!!!
Они возвращают ИТЕРАТОРЫ, указывающие на начало
контейнера и на воображаемый элемент, который следует
за последним элементом контейнера (я обычно
называею этот элемент ЗАКОНЕЦ). Таким образом,
итераторы a.begin() и a.end() задают как бы
полуинтервал, в котором находятся все элементы
контейнера.
Продолжим реализацию класса Matrix, используя
современный подход: вместо базовых массивов
языка C/C++ используем контейнерные классы из
стандартной библиотеки STL. (Есть также
библиотека Boost.)
. . .
В методе Гаусса мы на очередном шаге обрабатываем
минор матрицы, начинающийся со строки i и столбца j.
В чистой математике мы ищем ненулевой элемент в
столбце j, начиная с i-й строки. Если такого нет, то
столбец нулевой, и мы просто увеличиваем j на 1.
Если есть ненулевой элемент в строке k, то мы меняем
строки i, k так, чтобы ненулевой элемент стоял бы в
начале минора в i-й строке.
НО!!! ТАК ДЕЛАТЬ НЕЛЬЗЯ при реальных вычислениях.
ПОЧЕМУ ТАК???
Когда потом зануляем столбец, мы вычитаем из
строки k, где k > i, строку i, умноженную на коэффициент
a[k][j]/a[i][j],
так, чтобы первый элемент в строке k обнулился.
Векторная запись:
a[k] = a[k] - a[i] * (a[k][j]/a[i][j])
Если элемент a[i][j] не является максимальным по модулю
в j-м столбце, то коэффициент,
на который умножаем,
| a[k][j]/a[i][j] | > 1
и ошибки экспоненциально растут.
Следовательно, надо искать не просто ненулевой элемент,
а максимальный по модулю элемент в столбце необработанного
минора.
---------------------
9 Apr 2025
Продолжение: классы в C++. Некоторые алгоритмы
1. Мы рассмотрели класс матриц над полем R
и реализовали алгоритм Гаусса приведения матрицы
к ступенчатому виду (Row Echelon Form).
Рассмотрим более подробно
1) алгоритм решения системы линейных уравнений
в частном случае, когда матрица системы невырождена;
2) алгоритм вычисления обратной матрицы.
Основаны оба этих алгоритма на приведении произвольной
матрицы к редуцированному ступенатому виду
(Reduced Row Echelon Form):
Обычный ступенчатый вид:
0 0 ... 0 x * * * * *
0 0 ... 0 0 0 x * * *
0 0 ... 0 0 0 0 x * *
0 0 ... 0 0 0 0 0 0 x
0 0 ... 0 0 0 0 0 0 0
. . .
0 0 ... 0 0 0 0 0 0 0
где x != 0, * -- любое число.
Редуцированный ступенчатый вид:
0 0 ... 0 1 * 0 0 * 0
0 0 ... 0 0 0 1 0 * 0
0 0 ... 0 0 0 0 1 * 0
0 0 ... 0 0 0 0 0 0 1
0 0 ... 0 0 0 0 0 0 0
. . .
0 0 ... 0 0 0 0 0 0 0
Редуцированный ступенчатый вид получается
из обычного обратным проходом.
Идем снизу вверх, находим первую ненулевую
строку i, домножаем ее на элемент, обратный
к первому ненулевому элементу в строке a_ij,
после чего a_ij = 1.
Далее из всех строк с индексом k > i выше нее
вычитаем i-ю строку, умноженную на элемент a_kj
так, чтобы a_kj стал равен нулю.
Напишем это на C++ (добавим метод в классе матриц).
================================
16 Apr 2025
================================
23 Apr 2025
Реализация класса "Полином над полем R"
class Polynomial;
Возможны разные реализации:
1) "разреженный" (sparce) полмином -- храним только
коэффициенты, отличные от нуля;
2) если храним все коэффициенты, в том числе и нулевые,
в массиве коэффициентов, то можем их хранить
(2.1) в порядке возрастания степеней, т.е.
coeff[i] -- это коэффициент при x^i;
(2.2) в порядке убывания степеней (мне этот способ
не нравится)
coeff[i] -- это коэффициент при x^(deg - i);
3) степень многочлена-константы равна нулю. А чему равна
степень нулевого многочлена? Варианты
(3.1) нулю;
(3.2) минус бесконечность;
(3.3) минус единица.
Мы используем вариант (3.1).
Коэффициенты храним в массиве в порядке возрастания степеней.
То есть коэффициенты многочлена
x^3 - x - 1
Храним в массиве
{ -1, -1, 0, 1 }
т.е. многочлен выражается как
p(x) = (-1) + (-1)*x + 0*x^2 + 1*x^3
Но!!!
При вводе-выводе многочлена мы будем печатать многочлен
в привычном для человека виде по убыванию степеней:
p(x) = x^3 - x - 1 (вывод).
Ввод (в тестовой программе):
==============================================
/home/vvb/Dush2025/Polynomial>./PolynomialTest
Enter a degree of the first polynomial: deg(f) = 3
Enter coefficients of the first polynomial f in descending order:
1 0 -1 -1
Enter a degree of the second polynomial: deg(g) = 2
Enter coefficients of the second polynomial g in descending order:
5 0 -7
f = x^3 - x - 1
g = 5*x^2 - 7
==============================================
Важно!!!
Вместо базовых массивов языка C/C++ надо, следуя Б.Страуструпу,
испльзовать конейнерные классы из стандартной библиотеки.
В случае многочлена мы храним его коэффициенты в динамическом
массиве типа std::vector<double>
Коэффициент при i-й степени переменной x хранится в
i-й ячейке динамического массиве.
Еще один важный момент:
мы не храним массив коэффициентов внури объекта
класса Polynomial, а -- ВНИМАНИЕ!!!
НАСЛЕДУЕМ класс Polynomial из класса std::vector<double>:
class Polynomial: public std::vector<double> {
// Наследуем ВСЕ методы динамичческого массива,
// которые теперь могут применяться к классу
// Polynomial
public:
// Создаем многочлен заданной степени, у которого
// все коэффиценты нулевые
Polynomial(int deg = 0):
std::vector<double>(deg + 1)
{
}
// Создаем многочлен нулевой степени по числу,
// которое будет его свободным членом
Polynomial(double freeTerm = 0.):
std::vector<double>(1, freeTerm)
{
}
// Создаем многочлен по динамическому массиву
// его коэффициентов
Polynomial(const std::vector<double>& coeffs):
std::vector<double>(coeffs)
{
}
// Создаем многочлен по динамическому массиву
// его коэффициентов -- то же самое, но с
// move-семантикой.
Polynomial(std::vector<double>&& coeffs):
std::vector<double>(coeffs)
{
}
// Coefficients in this constructor are given
// in ascending order
Polynomial(int deg, const double* coeffs):
std::vector<double>(coeffs, coeffs + deg + 1)
{
trim();
}
// Удаляем из динамического массива
// старшие коэффициенты многочлена, равные нулю
// Remove upper zero coefficients
void trim() {
int i = degree();
while (i > 0) {
if (fabs((*this)[i]) > POLYNOMIAL_EPS)
break;
--i;
}
assert(i >= 0);
resize(i + 1);
}
int degree() const {
return int(size() - 1);
}
Polynomial& operator+=(const Polynomial& f) {
int d0 = degree();
int d1 = f.degree();
int d = d0;
if (d1 > d)
d = d1;
resize(d + 1);
for (int i = 0; i <= d; ++i) {
if (i <= d0) {
if (i <= d1)
(*this)[i] += f[i];
} else {
assert(i <= d1);
(*this)[i] = f[i];
}
}
trim();
return *this;
}
// Подчеркнем, что метод operator+ можно, но НЕ НУЖНО
// реализовывать внутри класса!
// (Читайте книгу Б.Страуструпа
// "The C++ Programming Language", его совет --
// внутри класса лучше реализовывать только операторы
// типа operator+=, которые меняют объект класса,
// бинарные операторы типа operator+ лучше реализовывать
// как глобальные функции вне класса.
. . .
};
inline Polynomial operator+(
const Polynomial& p0,
const Polynomial& p1
) {
Polynomial sum = p0;
sum += p1;
return sum;
}
Особенность печати:
вместо
f(x) = -1*x^0 + -1*x^1 + 0*x^2 + 1*x^3
печатаем красиво:
f(x) = x^3 - x - 1
====================================
30 Apr 2025
Классы: итераторы
Сначала итераторы были лишь объектами в стандартной библиотеке
варианта 1998 г. Итаретор -- это обобщение понятия
указателя в C
double x = 123;
double *p;
p = &x;
*p === x * dereference (разыменование)
Связь между указателями и массивами.
Имя массива -- это указатель на его начальный элемент.
double a[100];
a === &(a[0])
Арифметика указателей -- это то преимущество, за
счет которого язык C выиграл у всех остальных языков.
Масштабирование
p = &(a[0]);
p + 1 == &(a[1]);
p + k -- адрес k-го элемента массива a
Соответственно,
a[k] == *(p + k)
Разность указателей -- это целое число,
равное количеству элементов того типа, на который ссылается
указатель, которые помещаются между двумя адресами.
Два способа суммирования массива в традиционном стиле
и с помощью указателей:
double a[100];
. . .
double sum = 0.;
for (int i = 0; i < 100; ++i) {
sum += a[i];
}
"Настоящий программист" на языке C напишет то же
самое с использованием указателей:
double a[100];
. . .
double sum = 0.;
double *p = a;
double *q = a + 100; // Указатель на воображаемый элемент
// ЗА последним элементом массива a
while (p < q) {
sum += *p;
++p;
}
В стандартной библиотеке языка C++ все контейнерные классы
содержат внутренний класс iterator (а также const_iterator),
который обобщает указатели языка C. Метод begin()
возвращает итератор, указывающий на начальный элемент
контейнера, метод end() -- итератор, указывающий на
воображаемый элемент за запоследним элементом контейнера.
Пример: суммирование элементов динамического массива.
std::vector<double> a(100);
. . .
double sum = 0.;
std::vector<double>::iterator p = a.begin();
while (p < a.end()) {
sum += *p;
++p;
}
В C++ 2011 появилось слово auto, которое означает тип
выражения в правой части оператора присваивания.
std::vector<double> a(100);
. . .
double sum = 0.;
auto p = a.begin();
while (p < a.end()) {
sum += *p;
++p;
}
Начиная с 2011 года в языке C++ (уже не в стандартной
библиотеке!) появилась конструкция range-based for
(цикл "для каждого"), которая является синтаксическим
сахаром для цикла while, использующего итераторы.
Тот фрагмент суммирования массива теперь можно записать
так:
std::vector<double> a(100);
. . .
double sum = 0.;
for (auto x: a) {
sum += x;
}
На самом деле, так не напишет ни один нормальный человек.
Первое: на самом деле, когда мы просто читаем элементы
массива и гарантировано их не меняем (не портим), то
надо использовать const_iterator:
std::vector<double> a(100);
. . .
double sum = 0.;
// std::vector<double>::const_iterator p = a.cbegin();
auto p = a.cbegin();
while (p < a.cend()) {
sum += *p;
++p;
}
Если использовать range-based for, то надо писать так:
std::vector<double> a(100);
. . .
double sum = 0.;
for (const auto& x: a) {
sum += x;
}
===================================================
Задача сортировки:
дан массив размера n
a0, a1, a2, ..., a_n-1
Надо упорядочть его элементы по возрастанию:
a0 <= a1 <= a2 <= ... <= a_n-1
Оценка минимального числа сравнений в произвольном
алгоритме сортировки.
Допустим, что нет никакой информации об элементах массива,
мы можем их только сравнивать между собой:
a_i < a_j? true/false
Тогда время работы алгоритма можно оценить по числу
сравнений, необходимых для самого плохого входа.
Теорема: в произвольном алгоритме сортировки число
сравнений на самом плохом для него входе не меньше чем
t >= log_2 (n!)
Напримеp, чтобы упорядочит массив длины 4, нужно сделать
в общем случае не меньше чем 5 сравнений.
t >= log_2(4!) = log_2(24) > log_2(16) = 4
t > 4 => t >= 5
И можно предьявить алгоритм, который упорядочиват массив за
не более чем 5 сравнений.
Следствие:
t >= log_2 (n!) ~ n*log_2(n) по формуле Стирлинга
n! ~ n^n * e^(-n) sqrt(2*pi*n)
log_2 (n!) ~ n*log_2(n) +
+ (-n) + 1/2*(log_2(n) log_2(2*pi)) =
n*log_2(n) + o(n*log_2(n) ~
~ n*log_2(n)
Для доказательства рассмотрим дерево работы алгоритма
сортировки.
Считаем, что порядок обладает свойством транзитивности:
a < b и b < c => a < c
Алгритм сортировка == расписание турнира команд ==
== бинарное дерево.
Вершина -- пара играющих команд (i, j)
В соотвествии с исходом матча турнир дальше идет
по одной из двух ветвей. Тернимальным вершинам
турнирного дерева соответствуют финальные расстановки
команд, т.е. отсортированный массив.
Рассмотрим пример трех команд: 1, 2, 3
(1, 2)
1<2 / \ 2<1
(2, 3) ...
2<3/ \ 3<2
(1, 2, 3) (1, 3)
1<2 / \ 3<1
(1, 3, 2) (3, 1, 2)
Макс. число матчей = высоте турнирного дерева - 1
Терминальные вершины турнирного дерева
соответствуют различным расстановкам команд =>
число терм. вершин >= n!
Предложение 1. У полного дерева высоты h всего
2^(h-1) терминальных вершин.
Доказательство
При переходе на уровень ниже, начиная с корня дерева,
число вершин данного уровня удваивается.
Предложение 2. У произвольного дерева высоты h
число терминальных вершин <= 2^(h-1)
Доказательство
Достроим данное дерево до полного той же высоты,
число терминальных вершин при этом может только увеличиться.
Итак, для числа k терминальных вершин справедливо неравенство:
k <= 2^(h-1)
Следовательно,
log_2(k) <= h - 1
k >= n!
log_2(n!) <= log2(k) <= h - 1 = t
t >= log_2(n!) ~ n*log2(n)
Теорема доказана.
Перерыв до 13:51 по московскому времени
15:51
Продолжение
Напишем на C++ программу для тестирования различных
алгоритмов сортировки testSort.cpp
. . .
Наивные алгоритмы сортировки работают за время
O(n^2). Оптимальный алгоритмы работают за время
O(n*log(n)). Это
1) сортировка кучей HeapSort (или по-русски
говорят "Сортировка пирамидой");
2) сортировка слиянием MergeSort, у которой есть
много вариантов, наиболее продвинутый вариант
называется TimSort (не "команда" Team, а Тим --
это имя автора).
HeapSort не требует дополнительной памяти, но,
увы, не является стабильной сортировкой, т.е.
может менять взаимный порядок одинаковых элементов.
MergeSort стабильна, но требует дополнительной памяти
размера O(n).
Куча (Heap, priority_queue)
Массив наделяется структурой бинарного дерева:
у узла a[i] сыновья a[2*i + 1], a[2*i + 2]
Дерево называется пирамидой, или (максимальной) кучей,
если отец больше или равен своим сыновьям:
a[i] >= a[2*i + 1]
a[i] >= a[2*i + 2]