Задания по выч. практике. 2 семестр 2 курс.

                      ТРЕБОВАНИЯ К ПРОГРАММАМ

1. Необходимо точно выполнять условия задач, при сомнениях --
   консультироваться с преподавателем. Программы представляются в
   исходных текстах.

2. Текст программы должен быть откомментирован. В заголовке указать
   имя автора, группу, краткую формулировку задания. Переменные
   должны иметь осмысленные имена. Желательно объявление переменной
   снабжать комментарием о ее назначении.

3. Следует структурировать программу, разбивая ее на (относительно)
   независимые части. Осуждается порочная практика размещения многих
   операторов в одной строке.

4. Длинные программы (свыше 200 строк) следует разбивать на несколько
   файлов и создавать проект. Это обязательное требование, так как
   умение работать с проектами квалифицированному программисту
   необходимо.

5. Интерфейс программы должен быть достаточно удобен
   для пользователя.

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

7. Исходные данные в любом из заданий, если это не оговорено особо,
   должны вводиться с клавиатуры или из файла, а именно: если при
   запуске программы в командной строке указано имя файла, то
   исходные данные читаются из него, в противном случае - вводятся с
   клавиатуры.

8. В программе не должно быть глобальных переменных.

=========================================================================
1. Реализовать класс "Стек символов" (на базе списка). Класс должен
включать в себя методы:
   добавить / взять элемент в вершине стека;
   стек пуст / непуст.

   Реализовать класс "Массив стеков". Длина массива определяется во
время инициализации и в дальнейшем не меняется. Методы класса:
   добавить стек в качестве n-й компоненты;
   вывод содержимого n-го стека на экран.

2. Реализовать класс "Очередь символов" (на базе списка). Класс
должен включать в себя методы:
   добавить элемент в очередь;
   взять элемент из очереди;
   очередь пуста / непуста.

   Реализовать класс "Массив очередей". Длина массива определяется во
время инициализации и в дальнейшем не меняется. Методы класса:
   добавить очередь в качестве n-й компоненты;
   вывод содержимого n-й очереди на экран.


3. Реализовать класс "Дек символов" (на базе списка). Класс должен
включать в себя методы:
   добавить / взять элемент в начале / конце дека;
   дек пуст / непуст.

   Реализовать класс "Массив деков". Длина массива определяется во
время инициализации и в дальнейшем не меняется. Методы класса:
   добавить дек в качестве n-й компоненты;
   вывод содержимого n-го дека на экран.


4. Реализовать класс "Матрица целых" размера m x n. Класс должен
включать в себя методы:
   получить размеры матрицы;
   получить элемент с заданными координатами;
   изменить элемент с заданными координатами;
   прибавить заданную матрицу;
   умножить на заданную матрицу;
   умножить на константу.


5. Реализовать класс "Защищенный массив символов". Массив должен быть
одномерным и индексироваться целыми числами. Границы изменения
индекса задаются при инициализации и в дальнейшем не изменяются.
Методы: получить границы массива, прочитать / изменить значение
компоненты, вывести массив в поток. При этом должна производиться
проверка на нарушение границ, в случае нарушения выводиться на экран
сообщение об ошибке. Обращение к элементам массива должно быть таким же,
как и для обычных массивов.

   Реализовать класс "Текст". Текст хранить в виде массива защищенных
массивов. Его размеры задаются во время инициализации и в дальнейшем
не меняются. Методы:
   добавить строку в конец текста;
   вывести текст в поток.


6. Реализовать класс "Текст". Текст хранить в виде массива строк.
Размеры текста могут динамически изменяться.
Методы:
   добавить строку после n-й строки;
   получить n-ю строку;
   удалить n-ю строку;
   получить количество строк в тексте;
   получть количество символов в тексте;
   удалить весь текст.
Дополнительные функции:
   прочитать текст из потока (текст читается до конца потока);
   вывести текст в поток.

   Реализовать функцию, которая сравнивает два текста на равенство
(посимвольно).

7. Реализовать класс "Однонаправленный список символов".
Класс должен включать в себя методы:
   длина списка
   вставить символ после i-го
   удалить i-й символ
   удалить первое вхождение заданного символа
   поиск символа в списке
   вывод списка в поток

   Реализовать класс "Массив списков". Длина массива определяется во
время инициализации и в дальнейшем не меняется. Методы класса:
   добавить список в качестве n-й компоненты;
   получить n-й список

8. Реализовать класс "Двунаправленный список символов".
Класс должен включать в себя методы:
   длина списка
   вставить символ после i-го
   удалить i-й символ
   удалить первое вхождение заданного символа
   поиск символа в списке
   вывод списка в поток

   Реализовать класс "Массив списков". Длина массива определяется во
время инициализации и в дальнейшем не меняется. Методы класса:
   добавить список в качестве n-й компоненты;
   получить n-й список

========================================================================

11. Реализовать класс "Многочлен от переменных x,y,z с вещественными
коэффициентами" с методами:
   вычисление значения многочлена на заданных числах;
   вычисление степени многочлена по каждой переменной.

Объект инициализируется символьной строкой, не содержащей скобок.

На базе этого класса реализовать производные классы:

   1) "Многочлены 2-й степени от одной переменной". Методы:
       нахождение корней многочлена;
       разложение многочлена на множители;
       вычисление производной многочлена;

       Инициализация символьной строкой и тройкой чисел.

   2) "Линейные формы от переменных x,y,z". Методы:
       форма диагональна или нет;
       форма невырождена или нет.

       Инициализация только символьной строкой.


12. Реализовать класс "Текст". Текст хранится в виде массива строк,
длина текста не фиксирована. Методы:
   добавить строку в конец текста;
   удалить последнюю строку;
   текст пуст / непуст.

   Реализовать также следующие классы (подумав, какой на базе
   какого):

   1) "Объявление". Объявление представляет собой текст, имеет строку
   для хранения адреса и массив строк с телефонами. Методы:
     изменить адрес;
     добавить / удалить телефон;
     подсчитать количество символов в объявлении;
     распечатать объявление (в поток).

   2) "Объявления с вознаграждением". Представляет собой объявление с
информацией о сумме вознаграждения и методе, позволяющем ее
получить.

   3) "Доска объявлений". Содержит массив объявлений. Размер массива
определяtтся при инициализации и в дальнейшем не увеличивается.
   Методы:

     добавление / чтение / удаление объявления;

13. Реализовать класс "Человек", включающий в себя имя, фамилию,
отчество, год рождения и методы, позволяющие изменять / получать
значения этих полей.

   Реализовать производные классы:

   1) "Преподаватель университета" с полями: должность, ученая
   степень, специальность, список научных трудов (массив строк).

   2) "Член партии" с полями: название партии, год вступления в
   партию, номер партбилета, автобиография (массив строк).

   3) "Преподаватели - члены партии" (производный от 2 и 3).
   Дополнительное поле -- список трудов в поддержку партии.

   Классы должны содержать методы доступа и изменения всех полей.
Предельные размеры динамических массивов задаются при инициализации и
не увеличиваются в дальнейшем.

14. Реализовать класс "Человек", включающий в себя имя, фамилию,
отчество, год рождения и методы, позволяющие изменять / получать
значения этих полей.

   Реализовать производные классы:

   1) "Предприниматель" -- содержит номер лицензии, адрес
   регистрации, ИНН, данные о налоговых платежах (массив пар вида
   <дата, сумма>).

   2) "Турист" -- содержит данные паспорта (строка), данные о
   пересечении границы в виде массива пар <дата, страна>.

   3) "Челнок" (производный от 2 и 3) -- добавляется массив строк -
   список адресов, по которым покупается товар.

   Классы должны содержать методы доступа и изменения всех полей.
Предельные размеры динамических массивов задаются при инициализации и
не увеличиваются в дальнейшем.

15. Описать класс "Функционал на функциях на отрезке [a,b]" с
методом, по функции выдающим число. Производные классы должны
реализовать следующие функционалы:

(1) интегрирование методом прямоугольников (5-10 промежуточных
значений);

(2) то же, методом трапеций;

(3) то же, квадрата функции;

(4) максимум модулей значений функции на концах отрезка и в середине.

Оболочка должна инициализировать обьекты -- функции и функционалы и
распечатать значения заданного функционала на заданной функции.

16. Описать класс "Функция на отрезке [a,b]" (шаблон с
параметрами double, double), единственным методом которого был бы
метод, выдающий значение функции в заданной точке.

Реализовать производные классы

(1) полиномы 2-й степени одной переменной
(2) линейная комбинация тригонометрических функций sin и cos
(3) экспонента от полинома 1-й степени одной переменной
(4) константную функцию


17. "Матрицы"

Разработать базовый класс "квадратная матрица вещественных чисел".
Поля:
        Размер;
        Указатель на область памяти, где хранятся элементы
        матрицы;

Виртуальные абстрактные методы:
        Записать элемент в i-й столбец, j-ю строку;
        Прочитать элемент из i-го столбца, j-й строки;

Невиртуальный метод:
        Вывести матрицу в поток.

От базового класса наследуются следующие классы:

(1) "Полная матрица вещественных чисел", хранящая n^2 чисел.

(2) "Диагональные матрица вещественных чисел".

(3) "Верхнетреугольная матрица вещественных чисел".

От (3) наследуется:

(4) "Симметрическая матрица вещественных чисел".

Придумать оптимальный способ хранения каждого из четырех производных типов
матриц (так, для диагональных матриц требуется n*sizeof(float) байт).
Переопределить те методы, включая конструкторы, работа которых зависит
от типа матрицы. Так, при попытке записать ненулевое число в позицию (3,1)
треугольной матрицы должна диагностироваться ошибка, при записи числа
в позицию (i,j) симметричной матрицы то же значение должно возникать
в позиции (j,i) и т.п.







18. Реализовать класс "Статья" с полями "название статьи" и "имя автора"
и методами, позволяющим посмотреть эти поля.

Реализовать класс "Библиотечная карточка" хранящая автора, название,
авторский знак, инвентарный номер, код по тематическому каталогу.
Класс должен иметь методы возвращающие эти поля и иметь метод
для алфавитного поиска, возвращающий объединенное значение полей
"автор" и "название".

Реализовать производные от него классы:

(1) "Карточка для самостоятельного издания" с методами, возвращающими
издательство, год издания, тираж, количество страниц и производные от
него классы

а) "Карточка для сборника статей" с методом, возвращающим карточки,
описывающие статьи (см. ниже).

б) "Карточка для книги" (книга состоит из одной статьи),
дополнительный метод должен возвращать статью.

(2) "Карточка для статьи" с методами, возвращающими кроме имени
автора, статью и ссылку на карточку для издания, в котором статья
опубликована.

Реализовать класс "Каталог", с производными "Тематический каталог",
"Алфавитный каталог" с методами, реализующими поиск по шифру или
автору (названию).

=======================================================================

21. МНОГОМЕРНЫЕ МАССИВЫ

Разработать класс, объектами которого являются многомерные массивы
(размерностью до MAX_DIM) с элементами типа NUMBER.

Конструктор класса выглядит примерно так:

    Array::Array(int dim, ...);  // первый параметр -- размерность,
    // остальные параметры -- границы по соответствующей размерности.

    Array M(3, 3,4,2);       // пример создания массива размерности 3
    // по 1-й размерности -- 3 (0..2),
    // по 2-й размерности -- 4 (0..3),
    // по 3-й размерности -- 2 (0..1).

Необходимы методы для определения размерности массива,
величины массива по данной размерности, сравнения двух многомерных
массивов, базовые арифметические операции:
 - сложение, вычитание двух массивов
 - умножение элементов массива на скаляр

Доступ к элементам массива осуществляется обычным образом:

   M[2][0][1] = M[i][j][1] ;

При индексации проверяется выход за границы массива.

Результатом индексирования массива числом индексов K, где K матрица (свертка по строкам/столбцам);
 - выделение строки/столбца/диагонали матрицы в независимый вектор;
 - преобразование матрицы(вектора) одного типа в матрицу(вектор)
   другого типа

Обращение к элементам матрицы (вектора) должно происходить по правилам C/C++:

   FloatMatrix M(10,10);
   IntVector   V(15);
   ......
   M[0][5] = 0.5;
   V[13] = 666 + M[1][3];
   M[1] = R;


23. КЛАСС "МАТЕМАТИЧЕСКИЕ ФУНКЦИИ"

1. Реализовать класс "База функций", который содержит имена и
   определения базовых функций от одной переменной. Методы класса:

  -- добавить определение функции в виде
        addFunction("sec", "1/sin(x)");
  -- получить определение функции;
  -- удалить определение функции.

Данный класс должен хранить кроме того некоторый набор элементарных
функций (exp, sin, cos, sqrt и т.п.)


2. Реализовать класс "Функция", объектами которого являются вещественные
   функции от одного аргумента, вида

     double func(double);

Объекты можно конструировать, задавая выражение в виде строки, например:

    Function func1( "exp(x) + (x^2 - 4.4x^3) / cos(x)" );

Внутреннее представление функции -- в виде двоичного дерева.

Кроме того, функцию можно задавать как комбинацию функций, например:

    Function MyFunc = func1 + 2 * func2 * (func3/func4) - func5(func6);

Реализовать вычисление значения по заданному аргументу. Предусмотреть
ситуации, когда аргумент лежит вне области определения. Естественно,
если при вычислении MyFunc(100) значение func2(100) не определено, то
и значение MyFunc не определено.

Реализовать ввод-вывод функции в виде суперпозиции элементарных функций.
При выводе не должны печататься лишние скобки. Пример: (x+1+(2+x^2)).


Реализовать вычисление производной функции (результат -- функция).


24. КЛАСС "ПОЛИНОМЫ"

Разработать класс, объектами которого являются полиномы с вещественными
коэффициентами.

Объекты можно конструировать, задавая выражение в виде строки, например:

    Polynom poly( "1.1x^3 + 4x - 1" );

Кроме того, полином можно задавать как комбинацию полиномов, например:

    Polynom POL = p1 + 2 * p2 * p3^n - p4(p5);  // n -- целое

Внутреннее представление -- списком.
При задании полинома комбинацией полиномов требуется приводить подобные,
раскрывать скобки, возводить в степень и т.п.

Действия над полиномами:

1. Вычисление значения по заданному аргументу.
2. Ввод и вывод полинома.
3. Вычисление производного полинома.
4. Вычисление первообразной (с нулевой константой).
5. Деление полиномов, вычисление остатка от деления.
6. Нахождение наибольшего общего делителя, наименьшего общего кратного.

25. КЛАСС "ДЛИННЫЕ ЧИСЛА"

1. Длинные целые числа.

Реализуйте класс, объектами которого являются целые числа с неограниченным
числом цифр. Число хранится в двоичном виде, память под массив данных
должна выделяться динамически.

Действия над длинными числами:

 - сложение, вычитание, умножение, деление нацело, взятие остатка,
   деление с остатком, возведение в целую степень;
 - операции сравнения двух длинных чисел;
 - ввод-вывод чисел (через потоки);
 - операции сдвига (на один/несколько бит);
 - взятие абсолютной величины числа.

Предусмотрите инициализацию числа строкой:
  LongNumber N("123456789012345678901234567890");
  N = "100000000000000000000000";
и преобразование числа в строку.

2. Рациональные числа.

Используя класс целых длинных чисел реализовать арифметику рациональных чисел.
Рациональное число хранить в приведенном виде.

Действия над рациональными числами:

 - сложение, вычитание, умножение, деление нацело, взятие остатка,
   деление с остатком, возведение в целую степень;
 - операции сравнения двух длинных чисел;
 - ввод-вывод чисел (через потоки);
 - взятие абсолютной величины числа.

Предусмотрите инициализацию числа строкой:
  Rational R("123456789012345678901234567890");
  R = "100000000000000000000000.0000200001";
  R = "1/7";

Оператор ввода из потока должен уметь читать число как в десятичном представлении
(123456789.0987654321), так и в виде дроби (123456789/987654321).

Оператор вывода печатает число в виде дроби.

Дополнительно предусмотреть преобразование числа в строку
а) в виде обычной дроби;
б) в виде десятичной дроби с заданным числом цифр в дробной части:
     Rational r("2/3");
     convertToDecimal( R, 4 ) == "0.6667"


26. МОДЕЛИРОВАНИЕ. "Волчий остров"

Остров (прямоугольник фиксированного размера) заселен дикими кроликами,
волками и волчицами. Имеется по несколько представителей каждого вида.
Кролики с вероятностью 1/9 передвигаются в один из восьми соседних
квадратов или остаются на прежнем месте. Каждый кролик с вероятностью 1/5
превращается в двух кроликов. Каждая волчица передвигается случайным образом,
пока в одном из восьми соседних квадратов не окажется кролик, за которым она
охотится. Если волчица и кролик оказываются в одном квадрате, волчица съедает
кролика и получает одно "очко". В противном случае она теряет 0.1 "очка".
Волки и волчицы c нулевым количеством "очков" умирают. Волк ведет себя подобно
волчице до тех пор, пока поблизости не исчезнут все кролики; тогда если
волчица находится в одном из восьми близлежащих квадратов, волк гонится
за ней. Если волк и волчица окажутся в одном квадрате и там нет кролика,
которого нужно съесть, они производят потомство случайного пола.

Для создания более устойчивой экологической системы острова введите
на острове запретные зоны для хищников.

Разработать набор классов, реализующих данную программу.

Программа должна работать в графическом режиме, весь остров помещается на
экране (размеры не меньше чем 50х50 клеток). Предусмотреть редактирование,
сохранение на диске и восстановление с диска популяции, гибкое изменение
параметров системы, пошаговую демонстрацию и режим быстрого просчета.


27. МНОЖЕСТВО С ХЭШ-ТАБЛИЦЕЙ

Реализовать класс-шаблон, объектами которого являются множества элементов
с элементами типа T (int, float, myObject, и т.д.)

Для внутреннего представления множества использовать динамическую
хэш-таблицу.

Операции над множеством:

- узнать мощность множества
- добавить/удалить элемент
- проверить есть ли элемент в множестве
- сделать множество пустым
- вывести множество в поток

Отношения между двумя множествами:
- равны ли два множества
- содержит ли одно множество другое
- пересечение двух множеств
- об'единение двух множеств
- разность двух множеств
- симметрическая разность двух множеств

Реализовать класс "итератор над множеством", который позволяет
перебирать элементы заданного множества. Порядок перебора элементов
не фиксирован. Набор методов итератора:
  - установить итератор в начальное состояние,
  - проверить: итератор перебрал все элементы множества,
  - выдать текущий элемент,
  - перейти к следующему элементу.

Пример:

   myObject e(..);
   SetOf S;
   S.adjoinElement( e ); // добавить элемент e в S.

   SetIterator Iter( S );
   for( Iter.reset(); !Iter.done(); Iter.next() ) {
     myObject tmp = I.value();
     ...
   }

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

28. МНОЖЕСТВО С ДВОИЧНЫМ ДЕРЕВОМ

Реализовать класс-шаблон, объектами которого являются множества элементов
с элементами типа T (int, float, myObject, и т.д.)

Для внутреннего представления множества использовать двоичное дерево.

Операции над множеством:

- узнать мощность множества
- добавить/удалить элемент
- проверить есть ли элемент в множестве
- сделать множество пустым
- вывести множество в поток

Отношения между двумя множествами:
- равны ли два множества
- содержит ли одно множество другое
- пересечение двух множеств
- об'единение двух множеств
- разность двух множеств
- симметрическая разность двух множеств

Реализовать класс "итератор над множеством", который позволяет
перебирать элементы заданного множества. Порядок перебора элементов
не фиксирован. Набор методов итератора:
  - установить итератор в начальное состояние,
  - проверить: итератор перебрал все элементы множества,
  - выдать текущий элемент,
  - перейти к следующему элементу.

Пример:

   myObject e(..);
   SetOf S;
   S.adjoinElement( e ); // добавить элемент e в S.

   SetIterator Iter( S );
   for( Iter.reset(); !Iter.done(); Iter.next() ) {
     myObject tmp = I.value();
     ...
   }

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