шпоры2 (1079645)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

1. Типы защищённости членов класса

По умолчанию члены класса являются закрытыми(private). Чтобы сделать части класса открытыми(т.е. доступными для других частей программы), необходимо объявить их после ключевого слова public.

class inf

{int a;

double b;

public:

void num();

int sum();};

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

(см. 8 вопрос)Спецификатор доступа protected объявляет защищенные члены или обеспечивает наследование защищенного класса. Доступ к защищенному члену идентичен доступу к закрытому члену, то есть к нему могут обращаться только другие члены ого же класса. Единственное исключение из этого правила проявляется при наследовании защищенного члена. В этом случае защищенный член существенно отличается от закрытого.

Если базовый класс наследуется как public класс, защищенные члены базового класса становятся защищенными членами производного класса, то есть доступными для производного класса. Следовательно, используя спецификатор protected, можно создать члены класса, которые закрыты в рамках своего класса, но которые может унаследовать производный класс, причем с получением доступа к ним.

33. Многофазная сортировка файлов

Идея многофазной сортировки состоит в том, что из имеющихся m вспомогательных файлов (m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода образуемых серий. Как только один из файлов ввода становится пустым, его начинают использовать для вывода серий, получаемых при слиянии серий нового набора (m-1) файлов. Таким образом, имеется первый шаг, при котором серии исходного файла распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое слияние серий из (m-1) файла, пока в одном из них не образуется одна серия.

Очевидно, что при произвольном начальном распределении серий по вспомогательным файлам алгоритм может не сойтись, поскольку в единственном непустом файле будет существовать более, чем одна серия. Предположим, например, что используется три файла B1, B2 и B3, и при начальном распределении в файл B1 помещены 10 серий, а в файл B2 - 6. При слиянии B1 и B2 к моменту, когда мы дойдем до конца B2, в B1 останутся 4 серии, а в B3 попадут 6 серий. Продолжится слияние B1 и B3, и при завершении просмотра B1 в B2 будут содержаться 4 серии, а в B3 останутся 2 серии. После слияния B2 и B3 в каждом из файлов B1 и B2 будет содержаться по 2 серии, которые будут слиты и образуют 2 серии в B3 при том, что B1 и B2 - пусты. Тем самым, алгоритм не сошелся (таблица 3.2).

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

Число серий в файле B1	Число серий в файле B2	Число серий в файле B3
10	6	0
4	0	6
0	4	2
2	2	0
0	0	2

Попробуем понять, каким должно быть начальное распределение серий, чтобы алгоритм трехфазной сортировки благополучно завершал работу и выполнялся максимально эффективно. Для этого рассмотрим работу алгоритма в обратном порядке, начиная от желательного конечного состояния вспомогательных файлов. Нас устраивает любая комбинация конечного числа серий в файлах B1, B2 и B3 из (1,0,0), (0,1,0) и (0,0,1). Для определенности выберем первую комбинацию. Для того, чтобы она сложилась, необходимо, чтобы на непосредственно предыдущем этапе слияний существовало распределение серий (0,1,1). Чтобы получить такое распределение, необходимо, чтобы на непосредственно предыдущем этапе слияний распределение выглядело как (1,2,0) или (1,0,2). Опять для определенности остановимся на первом варианте. Чтобы его получить, на предыдущем этапе годились бы следующие распределения: (3,0,2) и (0,3,1). Но второй вариант хуже, поскольку он приводится к слиянию только одной серии из файлов B2 и B3, в то время как при наличии первого варианта распределения будут слиты две серии из файлов B1 и B3. Пожеланием к предыдущему этапу было бы наличие распределения (0,3,5), еще раньше - (5,0,8), еще раньше - (13,8,0) и т.д.

Это рассмотрение показывает, что метод трехфазной внешней сортировки дает желаемый результат и работает максимально эффективно (на каждом этапе сливается максимальное число серий), если начальное распределение серий между вспомогательными файлами описывается соседними числами Фибоначчи. Напомним, что последовательность чисел Фибоначчи начинается с 0, 1, а каждое следующее число образуется как сумма двух предыдущих:

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....)

Понятно, что если распределение основано на числе Фибоначчи fi, то минимальное число серий во вспомогательных файлах будет равно fi, а максимальное - f(i+1). Поэтому после выполнения слияния мы получим максимальное число серий - fi, а минимальное - f(i-1). На каждом этапе будет выполняться максимально возможное число слияний, и процесс сойдется к наличию всего одной серии.

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

1. Обеспечение доступа к защищённым членам класса (начало – 7 вопрос)

class inf

{int a;

double b;

public:

void num();

int sum();

protected:

int asdf;};

class qwer : public inf

{int p;

public:

void func();};

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

class inf class qwer : public inf

{int a; {int p;

double b; public:

public: void func();};

void num(); class qwer1 : public qwer

int sum(); {int p1;

protected: public:

int asdf;}; void func1();};

Если базовый класс наследуется закрытым способом, защищенные члены этого базового класса становятся закрытыми (private) членами производного класса. То есть при повторном наследовании(наследовании первого производного класса вторым производным в качестве базового) второму производному классу защищенные члены становятся недоступны.

class inf

{int a;

double b;

public:

void num();

int sum();

protected:

int asdf;};

class qwer : private inf

{int p;

public:

void func();};

1. Оценка сложности алгоритмов сортировки файлов

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

Рассмотрим сложность имеющихся методов сортировки файлов.

Метод слияний.

Всего слияний log по основанию 2 длины.

Количество чтений и записей в файл n+n+log2(n/k)

k-элементы в подфайлах

k log2 k *(n/k)= log2k*n-сложность в оперативной памяти

Сложность данного вида сортировки линейная.

Метод осциллирующей сортировки.

Для расчета сложности берется логарифм по основанию 3, но сложность при этом остается такой же, как сложность при методе слияния, потому что логарифм по любому основанию особой роли не играет. Работает немного быстрее метода слияний.

1. Подсчет вершин в дереве рекурсивных вызовов

Алгоритм, получая на входе массив из n элементов, делит его пополам при первом вызове, поэтому рассмотрим случай, когда n=2^k, k =log ₂n В этом случае мы имеем полное дерево рекурсивных вызовов глубиной k, содержащее n листьев, фрагмент дерева показан на рис 10.1.

Рис 10.1 Фрагмент рекурсивного дерева при сортировке слиянием

Обозначим количество вершин дерева через V:
V = n + n/2+n/4+n/8+...+1 = n*(1+1/2+1/4+1/8+...+1)=2n - 1= 2^k+1- 1 Из них все внутренние вершины порождают рекурсию, количество таких вершин – Vr = n-1, остальные n вершин – это вершины в которых рассматривается только один элемент массива, что приводит к останову рекурсии.

1. Анализ трудоемкости алгоритма сортировка слиянием

Таким образом, для n листьев дерева выполняется вызов процедуры MS c вычислением r+1, проверка условия p=q и возврат в вызывающую процедуру для слияния, что в сумме с учетом трудоемкости вызова даёт:
F1(n) = n*2*(5+4+1) + n*2(If p=q и r+1) = 22*n;

Для n-1 рекурсивных вершин выполняется проверка длины переданного массива, вычисление середины массива, рекурсивный вызов процедур MS, и возврат, поскольку трудоемкость вызова считается при входе в процедуру, то мы получаем:
Fr(n) = (n-1)*2*(5+4+1) + (n-1)*(1+3+1) = 24*n - 24;

Процедура слияния отсортированных массивов будет вызвана n-1 раз, при этом трудоемкость складывается из трудоемкости вызова и собственной трудоемкости процедуры Merge:
Трудоемкость вызова составит (для 6 параметров и 4-х регистров):
Fm<вызов>(n) = (n-1)*2*(6+4+1) = 22*n - 22;

Поскольку трудоемкость процедуры слияния для массива длиной m составляет 18*m + 23 (10.1), и процедура вызывается n-1 раз с длинами массива равными n, n/2, n/4, …, причем 2 раза с длиной n/2, 4 раза с длиной n/4, то со-вокупно имеем:
Fm<слияние>(n) = (n-1)*23 + 18*n + 2*18*(n/2) + 4*18*(n/4) + … + = {учитывая, что таким образом обрабатывается k-1 уровней}
= 18*n *( log₂n – 1) + 23*(n-1) = 18*n* log₂n + 5*n - 23;

Учитывая все компоненты функции трудоемкости, получаем окончательную оценку:
Fa(n) = F1(n) + Fr(n) + Fm<вызов>(n) + Fm<слияние>(n) =
= 22*n + 24*n - 24 + 22*n - 22 +18*n* log₂n + 5*n - 23 =
= 18*n* log₂n + 73*n - 69 (10.2)

Если количество чисел на входе алгоритма не равно степени двойки, то необходимо проводить более глубокий анализ, основанный на изучении поведения рекурсивного дерева, однако при любых ситуациях с данными оценка главного порядка Q( n* log₂n) не измениться.

1. Деструкторы классов

Деструктор-это функция, которая вызывается при разрушении объекта.

Локальные объект создаются при входе в блок, в котором они определены, и разрушаются при выходе из него. Глобальные объекты разрушаются при завершении программы. В C++ именно деструктору поручается обработка процесса дезактивации объекта. Имя деструктора совпадает с именем конструктора (и соответственно с именем класса), он предваряется символом тильда “~”. Подобно конструкторам деструкторы не возвращают значений, а следовательно, в их объявлениях отсутствует тип возвращаемого значения.

Определение класса.

class inf

{int a;

double b;

public:

~inf(); деструктор

void num();

int sum();};

Определение деструктора.

inf::~inf()

{ cout<<”!!!”; }

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы