Рекурсивные алгоритмы (C++). Лекция 8 по основам программирования

Август 6, 2022

Главная
Информатика
Рекурсивные алгоритмы (C++). Лекция 8 по основам программирования

Содержание

3. РЕКУРСИВНЫМ называется способ построения объекта, в котором определение объекта включает аналогичные объекты в виде составных частей.
4. РЕКУРСИЯ Рекурсия – метод определения функции через её предыдущие и ранее определенные значения, а так же
5. РЕКУРСИЯ Глубина рекурсии – количество вложенных вызовов функции.
6. АЛГОРИТМЫ СОРТИРОВКИ
7. АЛГОРИТМЫ СОРТИРОВКИ РЕКУРСИВНЫЕ АЛГОРИТМЫ
8. БЫСТРАЯ СОРТИРОВКА Стратегия – «разделяй и властвуй». Описание алгоритма: Выбираем в массиве некоторый элемент, который будем
9. БЫСТРАЯ СОРТИРОВКА
10. БЫСТРАЯ СОРТИРОВКА void sort(int in[], int a, int b){ int i,j,mode; if (a>=b) return; for (i=a,
11. СОРТИРОВКА СЛИЯНИЕМ Стратегия – «разделяй и властвуй». Описание алгоритма: Сортируемый массив разбивается на две части примерно
12. СОРТИРОВКА СЛИЯНИЕМ
13. ОПЕРАЦИЯ СЛИЯНИЯ Отделяем элемент, наименьший из двух имеющихся в началах исходных массивов, и присоединяем его к
14. ОПЕРАЦИЯ СЛИЯНИЯ
15. ЗАДАЧИ 1. Реализовать алгоритм сортировки рекурсивным разделением списка. 2. Реализовать алгоритм сортировки рекурсивным слиянием списка.
17. Скачать презентацию

Слайд 2

Слайд 3

РЕКУРСИВНЫМ называется способ построения объекта, в котором определение объекта включает аналогичные объекты

в виде составных частей.

Слайд 4

РЕКУРСИЯ
Рекурсия – метод определения функции через её предыдущие и ранее определенные

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

Слайд 5

РЕКУРСИЯ
Глубина рекурсии – количество вложенных вызовов функции.

Слайд 6

АЛГОРИТМЫ СОРТИРОВКИ

Слайд 7

АЛГОРИТМЫ СОРТИРОВКИ
РЕКУРСИВНЫЕ АЛГОРИТМЫ

Слайд 8

БЫСТРАЯ СОРТИРОВКА
Стратегия – «разделяй и властвуй».
Описание алгоритма:
Выбираем в массиве некоторый

элемент, который будем называть опорным элементом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
Рекурсивно упорядочиваем подмассивы.

Слайд 9

БЫСТРАЯ СОРТИРОВКА

Слайд 10

БЫСТРАЯ СОРТИРОВКА
void sort(int in[], int a, int b){
int i,j,mode;
if (a>=b) return;

for (i=a, j=b, mode=1; i < j; mode >0 ? j-- : i++)
if (in[i] > in[j]) {
int c = in[i]; in[i] = in[j]; in[j]=c;
mode = -mode;
}
sort(in,a,i-1);
sort(in,i+1,b);
}

Слайд 11

СОРТИРОВКА СЛИЯНИЕМ
Стратегия – «разделяй и властвуй».
Описание алгоритма:
Сортируемый массив разбивается на

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

Слайд 12

СОРТИРОВКА СЛИЯНИЕМ

Слайд 13

ОПЕРАЦИЯ СЛИЯНИЯ
Отделяем элемент, наименьший из двух имеющихся в началах исходных массивов, и

присоединяем его к концу результирующего массива.
Элементы переносим до тех пор, пока один из исходных массивов не закончится.
После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива.

Слайд 14

ОПЕРАЦИЯ СЛИЯНИЯ

Слайд 15

ЗАДАЧИ
1. Реализовать алгоритм сортировки рекурсивным разделением списка.
2. Реализовать алгоритм сортировки

рекурсивным слиянием списка.

Рекурсивные алгоритмы (C++). Лекция 8 по основам программирования

Содержание

РЕКУРСИВНЫМ называется способ построения объекта, в котором определение объекта включает аналогичные объекты

РЕКУРСИЯРекурсия – метод определения функции через её предыдущие и ранее определенные

РЕКУРСИЯГлубина рекурсии – количество вложенных вызовов функции.

АЛГОРИТМЫ СОРТИРОВКИ

АЛГОРИТМЫ СОРТИРОВКИРЕКУРСИВНЫЕ АЛГОРИТМЫ

БЫСТРАЯ СОРТИРОВКАСтратегия – «разделяй и властвуй». Описание алгоритма:Выбираем в массиве некоторый

БЫСТРАЯ СОРТИРОВКА

БЫСТРАЯ СОРТИРОВКАvoid sort(int in[], int a, int b){int i,j,mode;if (a>=b) return;

СОР­ТИ­РОВ­КА СЛИЯ­НИ­ЕМСтратегия – «разделяй и властвуй». Описание алгоритма:Сортируемый массив разбивается на

СОР­ТИ­РОВ­КА СЛИЯ­НИ­ЕМ

ОПЕРАЦИЯ СЛИЯНИЯОтделяем эле­мен­т, наименьший из двух имеющих­ся в на­ча­лах ис­ход­ных мас­си­вов, и