1 .Понятие рекурсии условия окончания рекурсивного алгоритма

Рекурсивный - способ построения объекта при котором определение объекта включает в себя аналогичный объект ввиду некоторой его части.Решать задачу рекурсивно это значит разложить её на подзадачи , кототорые аналогичным образом (рекурсивно ) разделяются на ещё меньшие подзадачи .На определенном уровне задача становится на столько простой ,что её можно решить тривиально. Исходная задача считается выполненной когда ,будут выполнены все подзадачи её образующие (Стратегия разделяй и властвуй)

1)Задача разбивается на независимые подзадачи меньшей сложности.

2) Каждая подзадача решается отдельно.

3)Из отдельных решений подзадач строится решение исходной задачи.

Рекурсивной называется функция, которая содержит вызов самой себя.

Пример: вычисление (Х)! факториала.

0!=1.

N!=n*(int n)!

Int fakt(int n)

{if (n<=0) return 0;

Else return n*fact(n-1);

Условия окончания рекурсивного алгоритма.

В любом рекурсивном алгоритме обязательно следует предусмотреть его остановку . Например ввести условия его остановки. Например ввести условие при котором рекурсивном обращении к ф-ции прекращается .

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

2. Понятие файла структура текстового и бинарного файла

Понятие Файла

В языке С ++ файл рассматривается как последовательность считываемых или записываемых данных .

Файл –любое устройство передающее данные или работающее с файлами .

В языке С++ есть 2 вида файла :текстовые , двоичные (бинарные).

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

Бинарные - предназначены для хранения только двоичных данных.

Структура файла .

BOF (Begin fo File)

EOF(End of File)

В начале файла записывается инф. О файле : имя файла ,тип файла длина и т.д. , а в конце файла помещается признак конца файла.

Дисковый файл –это файл записанный на диске.

3. Функции для открытия закрытия файлов.

FILE* fopen(const char* имя файла, const char* режим открытия) Функция открывает файл, связывает его с соответственным потоком и возвращает указатель на открытый файл.

Имя файла – указывает на строку символов, в которой указывается режим открытия файла.

Режим открытия - указывает на строку символов, в которой указывается режим открытия файлов.

Допустимые режимы открытия файла.

r - Открывает текстовый файл чтения; w - Создает текстовыЙ файл для записи. Если файл с указанным именем существует, прежняя информация уничтожается; q – Добавить информацию в конец текстового файла; rb – Открыть двоичный файл для чтения; wb – Создать двоичный файл для записи; ab – Добавить информацию в конец двоичного файла; r+ - Открыть текстовый файл для чтения\записи; w+ - Создать текстовый файл для чтения\записи; a+ - Добавить в конец текстового файла или создание текстового файла для чтения\записи; r+b(rb+) – Открыть двоичный файл для чтения\записи; w+b(wb+) – Создать двоичный файл для чтения\записи; a+b(ab+) – Добавит в конец двоичного файла или создать двоичный файл для чтения\записи;

Если при открытии файла возникла ошибка, то функция fopen возвращает NULL. Для создания файла можно использовать FILE *fl; fl – fopen(“lab2.dat”, ''w'') Грамотнее:

FILE *fl; If ((fl=fopen(''lab2.dat'',''w''))==NULL)

{ cout<<’’Ошибка при создании’’<<endl;

return 1; }

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

FILE *fl; If ((fl=fopen(‘’lab2.dat’’,’’r’’))==NULL))

{ fl=fopen(‘’lab2.dat’’,’’w’’); }

int fclose(FILE *указатель на файл); Функция закрывает поток, открытый fopen, и записывает в файл все данныйе, которые находятся в дисковом буфере. После этого доступ к файлу будет запрещен.

int fcloseall(void); Закрывает все открытые файлы.

4.Функции для модификации содержимого файла(puts, gets, feof, fputs)

int putc(int символ, FILE *указатель на файл); Записывается один символ в текущую позицию открытого файла. Символ определяется как тип int.

int gets(FILE *указатель на файл); Читает один символ из текущей позиции указанного файла и после чтения указатель двигается на одну позицию вперед.

int feof(FILE *указатель на файл); Возвращает отличное от нуля значение (true), если конец файла не достигнут, и ноль (false), если достигнут конец файла

Пример:

{ if ((fl=fopen(‘’lab2.dat’’,’’r’’))==NULL)

{cout<<’’Ошибка при открытии’’<<endl;

exit(1); while(!feof(fl))cout<<getc(fl)<<fl<<’’ ‘’;

fclose(fl); }

int fputs(const char *строка, FILE *указатель на файл); Записывает строку символов в текущую позицию указанного файла.

сhar *fgets(char *строка, int lkbyf, FILE *указатель на файл); Читает строку символов, начиная с текущей позиции указанного файла до тех пор пока не будет прочитан символ перехода на новую строку, либо количество прочитанных символов не станет равным длина – 1.

int *fprintf(FILE *указатель на файл, const char *управляющая строка);

int *fscanf(FILE *указатель на файл, const char *управляющая строка);

void rewind(FILE *указатель на файл); - устанавливает указатель текущей позиции в начало файла.

Int terror(FILE *указатель на файл); - определяет произошла ли ошибка при работе с файлом.

Size_t fwrite(const void *записываемое данное, size_t размер элемента, size_t число элементов, FILE *указатель на файл); - Записывает в файл заданное число данных, заданного размера.

Size_t – определяет целое без знака. Ф-ия возвращает число записанных элементов;

int fileno(FILE *указатель на файл); - Возвращает знак дескриптора указ. файла(логический №файла)

long filelength(int дескриптор) – возвращает длину файла с соответственным дескриптором.

int chsize(int дескриптор, long размер); - Устанавливается новый размер файла с соответственным дескриптором.

int fseek(FILE *указатель на файл, long int число байт, int точка отсчета); - Устанавливает указатель в заданную позицию.

5.Функции для модификации содержимого файла(ferror, fwrite, fread)

int ferror(FILE * указатель на файл); определ. Произошла ли ошибка при работе с файлом

size_t fwrite( const void* записываемое данное, size_t размер элемента, size_t число элементов, FILE* указатель на файл), запис. в файл зад. число дан. зад. размера.

Size_t – определяет целое без знака. Ф-ция возращ. число записанных элементов.

Int fileno( File* указатель на файл); - возвр. знач. дескриптера указ. файла(логич. № файла)

Long file length (int дескриптор) – возвр. длину файла с соответ. дескриптором

Int chsize( int дескриптор, long размер) ; - устанавливается новый размер файла соответ. дескриптором

Int fseek( FILE* указатель на файл, long int числа байт, int точка отсчёта) ; - устанавливает указ. в задан. позицию.

6. Сортировка массивов. Методы сартировки.

Поиск и сортиравка ведётся по ключу. Ключом счит. то поле сируктуры, по кот. ведется сортировка и поиск.

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

Цель сортировки – облегчить послед. поиск элементов.

Сортировку массивов наз. внутр. сортировкой, о сортировку файлов внешней.

Существует 3 основных метода сортировки:

1. Обмен (при этом методе меняется местами элементы, располож. не по порядку. Обмен продолж. до тех пор, пока все элементы не будут упорядочены).

2. Выбор (В начале ищется наименьший элемент и ставиться в первую позицию, затем ищется след. по значимости элем. и устанавл. на 2-е место и т.д. В рез. все элементы устанавливаются в необход. позицию.

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

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

Критерий эффективности сортировки:

1. Средняя скорость сортировки (Определяется числом сравнений и обменом).

2. Скорость работы в наилучшем и наихудшем случаях (Имеет знач., если такие случаи встреч. часто. Сущ. такие алгоритм, кот. имеют выс. средн.. скор., однако медленно работают в наихудшем случае).

3. Естественность сортировки (Сортировка наз. естественной, если время сортировки мин. и увелич. по мере возр. степени неупорядоч массива.

4. Алгоритм работы с эл., имеющими одинаковое значение.

7.Сортировка массивов. Простые методы сортировки.

1. Обмен (при этом методе меняется местами элементы, располож. не по порядку. Обмен продолж. до тех пор, пока все элементы не будут упорядочены). По всем критериям пузырёк плох.

2. Выбор (В начале ищется наименьший элемент и ставиться в первую позицию, затем ищется след. по значимости элем. и устанавл. на 2-е место и т.д. В рез. все элементы устанавливаются в необход. позицию.

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

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

Метод пузырька: void s_puz(int a[], int n)

{ int i,j,t; for(i=1; i < n; i++)

for( j=n-1; j >= i; j--) if(a[j-1] > a[j])

{ t = a[j-1]; a[j-1] = a[j]; a[j] = t; }}

8.Метод Шелла .Сортировка Массивов

Метод Шелла основан на сортировке вставками. Сначало сортируются элементы отстоящ. друг от друга на 3 позиции, затем эл-ты отстоящ. друг от друга на 2 позиции и обязательно, посл. на это сортировка эл-ов отстоющ. друг от друга на 1 позицию. Кол-во сдвигов в данной сортировке существенно снижена по сравнению с прост методом сортир. существ. зависит от послед.выбр. шагов. Послед. шагов программист выбирает исходя из конкретн. условиях.

Пример:

void s_shell(int a[], int n)

{ int i, j, t; for(int d=3; d>0; d--)

for(i=d; i<n; i++) { t = a[i];

for(j=i-d; j>=0 && t<a[j]; j-=d) a[j+d]=a[j];

a[j+d] = t; }}

9. Сортировка слиянием. Алгоритм, достоинства и недостатки

Предполагается, что внутри массива из n-элементов имеется 2 смежных отсортированных участка и рекурсивный алгоритм основан на следующей последовательности подзадач:

- Тривиальная задача: Массив из одного элемента отсортирован

- Элементарная задача: Слияние двух отсортированных участков в один отсортированный

- Рекурсивное соотношение: Массив разбивается на 2 смежных массива, каждый из которых сортируется , после чего они сливаются в один массив.

Алгоритм: массив разделен до последовательности длины один ? слияние до упорядоченных пар? слияние до упорядоченных четверок? слияние в один массив.

Один из эффективных методов выполнения, поэтому как правило используется при организации алгоритмов внешней сортировки.