Темы

• Реализация классов на C++ (проект "R2Graph.zip")
• Задачи по теме "Стековый калькулятор" (проект "StackCalc.zip")
• Задачи по теме "Графика" (проект "Func.zip")
• Задачи по теме "Инвариант цикла".
• Задачи по теме "Текстовый редактор" (проект "TEdit.zip")
• Задачи по теме "Красно-черные деревья" (проект "Tree.zip")

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. Добавить команды табуляции по словам:
   • Shift+Вправо перемещает курсор в начало следующего слова;
   • Shift+Влево перемещает курсор на пробел, непосредственно следующий за концом предыдущего слова.
3. Добавить команду "найти парную скобку", которая должна выполняться по нажатию Ctrl+"[" (квадратная скобка). При этом, если курсор стоит на скобке, он должен перемещаться на парную скобку. Скобка может быть круглой, квадратной или фигурной, открывающей или закрывающей. Если команда не может быть выполнена, курсор должен оставаться на месте.
4. Реализовать команды
   
   • добавить строку в буфер, выполняется нажатием F3. При этом курсор перемещается на одну строку вниз;
   • вставить все строки из буфера в текущее место в тексте, выполняется нажатием F4. Курсор при этом остается на месте.
   Команда "добавить строку в буфер" должна очищать буфер, если после предыдущего добавления была хотя бы раз выполнена команда "вставить строки из буфера".
5. Реализовать команды
   
   • добавить символ в буфер, выполняется нажатием F1. Курсор при этом перемещается на одну позицию право;
   • вставить все символы из буфера в текущее место в тексте, выполняется нажатием F2. Курсор при этом смещается вправо на количество позиций, равное количеству вставленные символов.
   Команда "добавить символ в буфер" должна очищать буфер, если после предыдущего добавления была хотя бы раз выполнена команда "вставить символы из буфера".
6. Добавить команду откатки на одно действие назад для следующих двух действий:
   • удаление строки (по Shft+Delete или Ctrl+K);
   • разрезание строки по нажатию Enter;
   команда выполняется нажатием Ctrl+Z.
7. Добавить команды
   • удаления начала текущей строки до курсора, не включая символ в позиции курсора. Команда должна выполняться по Ctrl+U;
   • удаления конца текущей строки, начиная с символа в позиции курсора. Команда должна выполняться по Ctrl+D;
   • склеивания двух строк: к текущей строке надо приклеить следующую строку, при этом следующая строка удаляется (т.е. из двух строк делается одна). Команда должна выполняться по Ctrl+Delete.
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. Найти и напечатать все максимальные почти сбалансированные поддеревья.