В. В. Борисенко, 2003-04 учебный год

Оглавление

• Реализация классов на C++.
• Задачи по теме "Стековый калькулятор" (проект "StackCalc.zip")
• Задачи по теме "Графика" (проект "GWindow.zip")
• Задачи по теме "Выпуклая оболочка" (проект "R2Conv.zip")
• Задачи по теме "Текстовый редактор" (проект "TextEdit.zip")
• Задачи по теме "Хэш-реализация множества" (проект "HashSet.zip")
• Задачи по теме "Красно-черные деревья" (проект "TreeSet.zip")
• Задачи по теме "Синтаксический разбор" (проект "YaccCalc.zip")

Все проекты в одном архиве: AllProj.tgz.

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

   • конструктор по умолчанию (тождественное преобразование);
   • copy-конструктор;
   • конструктор, на вход которому подаются 3 координаты направляющего вектора оси вращения и угол поворота в радианах. Поворот происходит против часовой стрелки, если смотреть из конца вектора (т.е. по правилу правого винта);
   • композиция преобразований (operator*);
   • действие преобразования на вектор R3, вектор представляется массивом из трех элементов типа double.

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

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

Задачи по теме "Графика" (проект "GWindow.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 (без удаления невидимых линй), а также красным цветом сечение куба заданной плоскостью.

Задачи по теме "Выпуклая оболочка" (проект "R2Conv.zip")

Во всех задачах надо

• первое: добавить соответствующее предписание к системе предписаний исполнителя "Выпуклая оболочка", т.е. модифицировать файлы "R2Conv.h" и "R2Conv.cpp", содержащие интерфейс и реализацию класса R2Convex. Например, в задаче
  Добавить предписание "Точка <вх:t> внутри выпуклой оболочки?: да/нет"
  надо к классу R2Convex добавить метод
  bool contains(const R2Point& p) const;
• второе: модифицировать программу "convmain.cpp", позволяющую работать с исполнителем "Выпуклая оболочка" в графическом окне, добавив вызов дополнительного предписания и отображение его результата. Например, в упомянутой выше задаче надо по нажатию правой клавиши мышки нарисовать крестик в точке нажатия и в левом верхнем углу окна напечатать текст "Точка внутри" или "Точка вне". Обязательным требование является корректная перерисовка окна, т.е. крестик и напечатанная фраза не должны пропадать при перерисовке окна.

Список задач:

1. Добавить предписание "Диаметр выпуклой оболочки: вещественное".
2. Добавить предписание "Центр тяжести вершин: точка".
3. Добавить предписание "Центр тяжести многоугольника: точка".
4. Добавить предписание "Центр тяжести многоугольника: точка".
5. Добавить предписание "Точка <вх:t> внутри выпуклой оболочки?: да/нет".
6. Добавить предписание "Угол, под которым выпуклая оболочка видна из точки <вх:t>: вещественное".
7. Добавить предписание "расстояние от данной точки до выпуклой оболочки" (если точка внутри, то расстояние 0).

Задачи по теме "Текстовый редактор" (проект "TextEdit.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+клавиша" в Микромире) при одной и той же клавише. Прописные и строчные символы различаются.

Задачи по теме "Хэш-реализация множества" (проект "HashSet.zip")

В задачах нужно воспользоваться классом "HashSet", не изменяя ни его интерфейса, ни реализации.

Список задач:

1. Найти 20 самых часто встречающихся слов в тексте и напечатать их, упорядочив по количеству вхождений в текст. Текст должен читаться либо из файла, либо из входного потока, в зависимости от командной строки (если есть аргумент, то из файла, нет -- из входного потока).
2. Реализовать исполнитель "Записная книжка" со следующими тремя предписаниями:
   • Добавить или модифицировать запись (вход: имя человека: строка, вход: телефон: строка).
     Если имя не содержится в записной книжке, то запись добавляется; если содержится, то модифицируется телефон,
   • Прочесть телефон человека с именем (вход: имя: строка): строка.
     Если имя не содержится в записной книжке, то выдается пустая строка (или сообщение о том, что имя не найдено).
   • Закончить работу.

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

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

Задачи по теме "Синтаксический разбор" (проект "YaccCalc.zip")

1. Запись формулы включает имена переменных, знаки арифметических операций и скобки (нет констант). Напечатать обратную польскую запись формулы.
2. Запись формулы включает вещественные константы, знаки +, -, * (нет деления), скобки и переменную "x". Надо напечатать выражение этой формулы в виде многочлена, т.е. раскрыть скобки и привести подобные члены. Например, на вход подается строка "(x+1)*(x-2)", на выходе печатается

       1.000*x^2 + 1.000*x - 2.000
   

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