Итоговый экзамен (семестр)
1. Итоговый экзамен по информатике состоит в разработке программы на Си++.
2. Тематика задач, выносимых на экзамен, соответствует разделам курса Информатика:
- 4.4 - данные произвольного формата;
- 4.5 - функции с переменным количеством параметров;
- 4.8 - машинно-ориентированные операции (целые произвольной размерности в различных формах представления);
- 5.4 - рекурсия;
- 5.2, 5.3, 5.5, 5.7 - структуры данных;
- 5.8, 5.9 - текстовые и двоичные файлы произвольного доступа.
Кроме того, возможны варианты заданий, связанные с представлением разли чных типов данных - обычных и разреженных матриц, степенных полиномов и т.п..
При подготовке к экзамену можно использовать соответствующие варианты лабораторных работ 2,3,4 семестров.
3. Задача должна быть выполнена с использованием технологии ООП, то есть оформлена в виде класса или системы классов. Если программа работает с данными произвольных типов, то класс должен быть оформлен в виде шаблона. В классах необходимо описание только тех методов, которые используются в поставленной задаче ("воды" не надо). Если в варианте задания четко определен вид структуры данных, формы представления данных, то отклонения от условий считается грубым нарушением (например, статический или динамический массив, фиксированная или переменная размерность, внешняя или внутренняя форма представления числа и т.п..). При отсутствии такой информации необходимо явно оговорить выбранный Вами способ представления данных.
4. К тексту программы должно быть приложено описание структур данных, принципов построения алгоритма и перечня особых ситуаций, с которыми может сталкиваться программа (как реализованных в программе, так и не реализованных - "пустая" структура данных, поведение программы при несоответствии формата файла и т.п..). Объем - в пределах 1 стр.. Стилистика описания, логичность, связность также учитываются при выставлении оценки.
5. Пример задачи. Класс разреженных матриц. Матрица представлена динамическим массивом ненулевых коэффициентов (строка, столбец - int, значение - double).
Переопределить операцию сложения матриц, результат - объект-значение, операнды не меняются.
Комментарии : объект разреженная матрица представлен динамическим массивом структурированных переменных elem. Elem содержит " координаты" коэффициента и его значение. Кроме того объект содержит текущую размерность массива количество ненулевых коэффициентов. Частная проблема при сложении матриц определение размерности выходного массива коэффициентов. Сложение происходит в два этапа сначала определяется размерность выходных данных, а затем происходит само формирование выходного массива коэффициентов. Алгоритм сложения : создается массив коэффициентов в промежуточном (выходном) объекте. Затем в него переносятся коэффициенты первого объекта. Для каждого из коэффициентов второго объекта проверяется, есть ли соответствующий ему в первом объекте. Если есть, то коэффициент суммируется с коэффициентом первого объекта, иначе добавляется в выходной объект. Поскольку операция возвращает копию (значение) объекта-результата и объект имеет динамические данные, обязателен конструктор копирования. Используется также служебный метод (приватный), производящий поиск заданного коэффициента и возвращающий его индекс в динамическом массиве. Сложение корректно выполняется для всех случаев, в том числе и для полностью нулевых матриц. Отсутствует реакция объектов на отсутствие динамической памяти в операторе new.
struct elem{
int x,y; // координаты коэффициента
double k; // значение коэффициента
};
class matrix{
elem *pd; // Динамический массив коэффициентов
int sz; // Размерность массива
int find(int,int); // Поиск позиции коэффициента
public:
matrix(matrix&); // Конструктор копирования
matrix(); // Конструктор нулевой матрицы
~matrix();
matrix operator+(matrix&); // Переопределенная операция сложения
};
matrix::matrix(){
sz=0; pd=new elem; // Для единообразия объектов выделяем память
}
matrix::~matrix(){ // Деструктор
delete pd;
}
matrix::matrix(matrix &two){ // Конструктор копирования
pd = new elem[two.sz];
sz=two.sz;
for (int i=0; i<sz; i++) pd[i]=two.pd[i];
}
// Личный метод поиска " места расположения" коэффициента
int matrix::find(int xx, int yy){
for (int i=0; i<sz; i++)
if (pd[i].x==xx && pd[i].y==yy) return i;
return 1;
}
matrix matrix::operator+(matrix &two){
int newsz=sz; // Размерность выходного массива
for (int i=0; i<two.sz; i++) // Если коэффициент из второго отсутствует
if (find(two.pd[i].x, two.pd[i].y)==-1)
newsz++; // в первом - увеличить размерность на 1
matrix out(); // Выходной объект
delete out.pd; // При создании не пустой
out.pd = new elem[newsz];
for (i=0; i<sz; i++) // Копировать первый в выходной
out.pd[i]=pd[i];
out.sz=sz;
for (i=0; i<two.sz; i++) // Если коэффициент из второго присутствует
{ // в выходном сложить, иначе добавить.
int nn=out.find(two.pd[i].x, two.pd[i].y);
if (nn!=-1)
out.pd[nn]+= two.pd[i];
else
out.pd[out.sz++] = two.pd[i];
}
return out;
}
// Вариант 2. Можно использовать в качестве временного
// объекта второй операнд, если передавать его по значению
matrix matrix::operator+(matrix two){
int newsz=sz; // Размерность выходного массива
for (int i=0; i<two.sz; i++) // Если коэффициент из второго отсутствует
if (find(two.pd[i].x, two.pd[i].y)==-1)
newsz++; // в первом - увеличить размерность на 1
// Перераспределить память во втором объекте
two.pd=realloc(two.pd, sizeof(elem)*newsz;
for (i=0; i<sz; i++) // Если коэффициент из второго присутствует
{ // в выходном сложить, иначе добавить.
int nn=two.find(pd[i].x, pd[i].y);
if (nn!=-1)
two.pd[nn]+= pd[i];
else
two.pd[two.sz++] = pd[i];
}
return two;
}
