Рекурсия и сложность

Сентябрь 2, 2022

Главная
Алгебра
Рекурсия и сложность

Содержание

2. Рекурсия и ее реализация Рекурсия реализуется на основе подпрограммы, вызывающей саму себя. Первый вызов рекурсивной подпрограммы
3. Этапы разработки рекурсивного алгоритма решения задачи 1) параметризация задачи, т.е. выявление различных элементов, от которых зависит
4. Рекурсивный алгоритм вычисления факториала Формула факториала: n! =n*(n – 1)*(n – 2)*...*1 управляющий параметр -текущее значение
5. Рекурсивная программа вычисления факториала #include "stdafx.h" #include long int fact(int i) { if (i==0) return 1;
6. Работа рекурсивной программы со стеком Стек при первом вызове fact (i=5) Cтек при уровне рекурсии 4
7. Роль стека при вызове подпрограммы В из А 1. В вершину стека помещается фрагмент нужного размера.
8. Рекурсивное вычисление чисел Фибоначчи F(1)=1,F(2)=1,для любого n>2 F(n)=F(n-1)+F(n-2) #include "stdafx.h" #include long int fib(long int i)
9. Задача «Ханойские башни» Существует легенда: «В храме Бендареса находится бронзовая плита с тремя алмазными стержнями. На
10. Алгоритм решения задачи «Ханойские башни» Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит
11. Программа «Ханойские башни»: обозначения Обозначим тот стержень, с которого следует снять диски, через s1, на который
12. #include "stdafx.h" #include enum st {left,middle,right}; void name(st ster) { switch (ster){ case 0: printf(" left
14. Хранение бинарных деревьев
15. Обходы бинарных деревьев Прямой (корень – левое поддерево - правое поддерево); обратный (левое поддерево – правое
16. Прямой обход void pr(struct tree *root) { if(!root) return; if(root->info) printf("%c ", root->info); pr(root->left); pr(root->right); }
17. Обратный обход void obr(struct tree *root) { if(!root) return; obr(root->left); obr(root->right); if(root->info) printf("%c ", root->info); }
18. Симметричный обход void sim(struct tree *root) { if(!root) return; sim(root->left); if(root->info) printf("%c ", root->info); sim(root->right); }
19. Переборные задачи. #include "stdafx.h" #include int a[20]; int k; void write_number() { printf("\n"); for (int j=0;j
20. Пример работы программы для k=3 Если i=k+1, то find(k+1) запускает write_number для вывода и завершает работу,
21. Задача о расстановке n ферзей for i1 := 1 to n do begin ферзь[1] := i1;
22. Отсечения при переборе for i1 := 1 to n do begin ферзь[1] := i1; for i2
23. Простые примеры задач на динамическое программирование Var D : Array [1..50] of LongInt; Function F(X :
24. Жадные алгоритмы Жадный алгоритм (greedy algorithm) – это метод решения оптимизационных задач, основанный на том, что
25. Дискретная и непрерывная задача о рюкзаке Постановка дискретной задачи. В рюкзак загружаются предметы n различных типов
26. Непрерывная задача о рюкзаке Жадный алгоритм: Вычислим цены всех предметов - стоимость предмета разделим на массу
27. Неоптимальность жадного алгоритма для дискретной задачи 10 20 30 60 y.е. в целом, 6 за единицу
28. Размер задачи, временная сложность Алгоритмическая временная сложность — это зависимость времени исполнения алгоритма от длины или
29. Оценка временной сложности операторов программы Tif = Tv+max(Tthen+1,Telse). 1 операция по ветке Then соответствует операции безусловного
30. Класс и порядок сложности Определение. Множество вычислительных проблем, для которых существуют алгоритмы, схожие по сложности, называется
31. Порядок сложности нерекурсивных и рекурсивных функций s=0; for i:=1 to n do for j:=1 to m
32. Грубая оценка временной сложности рекурсивной программы Если верны соотношения T(1)=d; T(n)=a*T(n/c)+b*n, то в зависимости от констант
33. Классы сложности алгоритмов О(1) - количество шагов алгоритма не зависит от количества входных данных. Обычно это
34. Временная сложность рекурсивного алгоритма для задачи «Ханойские башни» Решение задачи для n дисков сводится к решению
35. Зависимость сложности от n. P-задачи Алгоритм, для которого t(n)=O(nx), где x – неотрицательная константа, называют полиномиальными
36. Экспоненциальные и NP-задачи NP-задачи - это класс задач, которые можно решить за полиномиальное время (Р), но
37. NP-полные задачи Основная теорема. Если некоторая NP – полная задача разрешима за полиномиальное время, то Р
39. Скачать презентацию

Слайд 2

Рекурсия и ее реализация
Рекурсия реализуется на основе подпрограммы, вызывающей саму себя.

Первый вызов рекурсивной подпрограммы выполняется из внешней программы.
Типы рекурсии:
прямая (функция содержит вызов самой себя);
косвенная (функция F1 вызывает функцию F2, которая вызывает исходную F1)

Слайд 3

Этапы разработки рекурсивного алгоритма решения задачи
1) параметризация задачи, т.е. выявление различных

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

Слайд 4

Рекурсивный алгоритм вычисления факториала
Формула факториала:
n! =n(n – 1)(n – 2)...1
управляющий

параметр -текущее значение числа n.
Тривиальный случай представляет собой 0! = 1
декомпозиция общего случая
n! = n*(n – 1)!

Слайд 5

Рекурсивная программа вычисления факториала
#include "stdafx.h"
#include
long int fact(int i)
{
if (i==0) return

1;
else return i*fact(i-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
long int f;
int n;
printf("\nInput n");
scanf("%d",&n);
f=fact(n);
printf("%i",f);
getch();
return 0;
}

Слайд 6

Работа рекурсивной программы со стеком
Стек при первом вызове fact (i=5)
Cтек при

уровне рекурсии 4

Слайд 7

Роль стека при вызове подпрограммы В из А
1. В вершину стека помещается

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

Слайд 8

Рекурсивное вычисление чисел Фибоначчи
F(1)=1,F(2)=1,для любого n>2 F(n)=F(n-1)+F(n-2)
#include "stdafx.h"
#include
long int fib(long

int i)
{
if ((i==1)||(i==2)) return 1;
else return fib(i-1)+fib(i-2);
}

int _tmain(int argc, _TCHAR* argv[])
{
int n;
long int ch;
printf("Input number:");
scanf("%d",&n);
ch=fib(n);
printf("\nFibonachi with number
%d is %i\n",n,ch);
getch();
return 0;
}

Слайд 9

Задача «Ханойские башни»
Существует легенда: «В храме Бендареса находится бронзовая плита с

тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота. Наибольший диск лежит на бронзовой плите и с остальными образует пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:
1) диски можно перемещать с одного стержня на другой только по одному;
2) нельзя класть больший диск на меньший;
3)при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски тоже могут находиться тоже только в виде пирамиды.
Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».

Слайд 10

Алгоритм решения задачи «Ханойские башни»
Назовем стержни левым (left), средним (middle) и

правым (right). Задача состоит в переносе m дисков с левого стержня на правый. Задача может быть решена одним перемещением только для одного (m = 1) диска.
Построим рекурсивное решение задачи, состоящее из трех этапов:
a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.

Слайд 11

Программа «Ханойские башни»: обозначения
Обозначим тот стержень, с которого следует снять диски,

через s1, на который надеть – через sk, а вспомогательный стержень через sw.
Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk;
алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.

Слайд 12

#include "stdafx.h"
#include
enum st {left,middle,right};
void name(st ster)
{
switch (ster){
case 0: printf(" left

");break;
case 1: printf(" middle ");break;
case 2: printf(" right ");break;
};
}
void step(st si,st sk)
{
printf("\ntake disk from");
name(si);
printf(",put to");
name(sk);
}

void move(int n,st si,st sw,st sk)
{
if (n==1) step(si,sk);
else
{
move(n-1,si,sk,sw);
step(si,sk);
move(n-1,sw,si,sk);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
printf("\nInput n:");
scanf("%d",&n);
move(n,left,middle,right);
getch();
return 0;
}

Слайд 13

Слайд 14

Хранение бинарных деревьев

Слайд 15

Обходы бинарных деревьев
Прямой (корень – левое поддерево - правое поддерево);
обратный

(левое поддерево – правое поддерево – корень) ;
симметричный (левое – корень – правое)

struct tree {
char info;
struct tree *left;
struct tree *right;
};

Слайд 16

Прямой обход
void pr(struct tree *root)
{
if(!root) return;
if(root->info) printf("%c ",
root->info);
pr(root->left);

pr(root->right);
}

Слайд 17

Обратный обход
void obr(struct tree *root)
{
if(!root) return;
obr(root->left);
obr(root->right);
if(root->info) printf("%c ",

root->info);
}

Слайд 18

Симметричный обход
void sim(struct tree *root)
{
if(!root) return;
sim(root->left);
if(root->info) printf("%c ", root->info);

sim(root->right);
}

Слайд 19

Переборные задачи.
#include "stdafx.h"
#include
int a[20];
int k;
void write_number()
{
printf("\n");
for (int j=0;j}
void

find(int i)
{
if (i==k) write_number();
else
{
a[i]=0;
find(i+1);
a[i]=1;
find(i+1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("\nk=");
scanf("%d",&k);
find(0);
getch();
return 0;
}

Рассмотрим программу, осуществляющую вывод всех k-значных двоичных чисел (их всего, очевидно, 2k)

Слайд 20

Пример работы программы для k=3
Если i=k+1, то find(k+1) запускает write_number для

вывода и завершает работу, так как вызов find(k+1) обозначает, что первые k элементов массива уже заполнены.

Слайд 21

Задача о расстановке n ферзей
for i1 := 1 to n do

begin
ферзь[1] := i1;
for i2 := 1 to n do begin
ферзь[2] := i2;
for i3 := 1 to n do begin
ферзь[3] := i3;
...
<проверка построенной позиции>
end;
end;
end;

Слайд 22

Отсечения при переборе
for i1 := 1 to n do begin
ферзь[1]

:= i1;
for i2 := 1 to n do begin
ферзь[2] := i2;
{ проверка частично построенной позиции }
if <ферзь[2] не бьёт ферзь[1]> then
for i3 := 1 to n do begin
ферзь[3] := i3;
{ проверка частично построенной позиции }
if <ферзь[3] не бьёт предыдущих> then
for i4 := 1 to n do begin
...
if <ферзь[n] не бьёт предыдущих> then
<решение найдено>
end;
end;
end;
end;

Слайд 23

Простые примеры задач на динамическое программирование
Var D : Array [1..50] of

LongInt;
Function F(X : integer) : LongInt;
Begin
if D[X] = 0
then
if (X = 1) or (X = 2)
then D[X] := 1
else D[X] := F(x - 1) + F(x - 2);
F := D[X]
end;
Без рекурсии:
D[1] := 1; D[2] := 1;
For i := 3 to X do D[i] := D[i-1] + D[i-2];

Слайд 24

Жадные алгоритмы
Жадный алгоритм (greedy algorithm) – это метод решения оптимизационных задач,

основанный на том, что процесс решения задачи можно разбить на шаги, на каждом из которых принимается решение.
Решение, принимаемое на каждом шаге, должно быть оптимальным только на текущем шаге, и должно приниматься вне зависимости от решений на других шагах.
На каждом шаге «жадный» алгоритм выбирает локально оптимальное в том или ином смысле решение.

Слайд 25

Дискретная и непрерывная задача о рюкзаке
Постановка дискретной задачи.
В рюкзак загружаются

предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес wi и стоимость vi (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W.
Обозначим количество предметов типа i через ki, тогда требуется максимизировать v1*k1+v2*k2+...+vn*kn при ограничениях w1*k1+w2*k2+...+wn*kn≤W, где ki - целые (0≤ki≤[W/wi]), квадратные скобки означают целую часть числа.

Слайд 26

Непрерывная задача о рюкзаке
Жадный алгоритм:
Вычислим цены всех предметов - стоимость предмета

разделим на массу (Price[i]/Weight[i]).
Сначала берем самый дорогой предмет и наполняем им рюкзак, если предмет закончился, а рюкзак не заполнен, берем следующий по цене, и так далее, пока не наберем максимально возможную суммарную массу предметов.
Для сортировки понадобится O(N·log(N)) операций.
В цикле по i от 1 до N и попробовать взять предмет i —
займет еще O(n) операций. Итого, общая сложность —
O(N·log(N) + N), что в общем случае эквивалентно
O(N·log(N)).

Слайд 27

Неоптимальность жадного алгоритма для дискретной задачи
10
20
30
60 y.е. в целом, 6 за

единицу веса

100 у.е. в целом, 5 за единицу веса

120 у.е. в целом, 4 за единицу веса

Результат «жадного выбора» в дискретной задаче – 2 предмета – 10 и 20 кг, сумма – 160 у.е.

На самом деле оптимум – 2 и 3 предметы! Сумма – 220 у.е.

Объем рюкзака= 50

Слайд 28

Размер задачи, временная сложность
Алгоритмическая временная сложность — это зависимость времени исполнения

алгоритма от длины или количества входных данных, называемых размером задачи.
Измеряется время числом элементарных шагов. Каждый элементарный шаг связан с операцией, выполняемой в алгоритме.

Слайд 29

Оценка временной сложности операторов программы
Tif = Tv+max(Tthen+1,Telse).
1 операция по ветке Then

соответствует операции безусловного перехода.
Tfor = Tv1 + Tv2+1 + k(Tтело +4),
где k – количество итераций цикла, 1 до цикла соответствует начальному присваиванию, 4 операции в цикле – сравнение параметра цикла с выражением V2, условный переход на тело цикла, увеличение счетчика цикла и безусловный переход на начало цикла.
ПРИМЕР:
for i:=1 to 100 do
for j:=1 to 3 do s:=s+a[i,j];
Его временная сложность равна 1+100(4+1+3*(4+2))=2301 операций.

Слайд 30

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

схожие по сложности, называется классом сложности.
При оценке эффективности алгоритма вычисление точного значения функции временной сложности f(n) может быть трудно, поэтому используются методы аппроксимации для определения верхней границы функции.
Пусть имеется функция g(n) и константа К такая, что K*g(n) превышает f(n) по мере того, как n значительно возрастает.
Определение. Функция f(n) имеет порядок O(g(n)), если имеется константа К и счетчик n0, такие, что
f(n) < K*g(n), для n > n0.

Слайд 31

Порядок сложности нерекурсивных и рекурсивных функций
s=0;
for i:=1 to n do

for j:=1 to m do s=s+1;
Временная сложность O(n*m)
Временная сложность для рекурсивных программ также является рекурсивной функцией:
T(n0)=const - нет рекурсивного хода
T(n)=f(T(g(n)) – при рекурсивном вызове.

Слайд 32

Грубая оценка временной сложности рекурсивной программы
Если верны соотношения
T(1)=d;
T(n)=aT(n/c)+bn,
то в

зависимости от констант а и с выражение для сложности имеет вид:
0(n) при aT(n)= 0(n log2n) при a=c
0(nlog c a) при a>c

Слайд 33

Классы сложности алгоритмов
О(1) - количество шагов алгоритма не зависит от количества

входных данных. Обычно это алгоритмы, использующие определённую часть данных и игнорирующие все остальные данные. Например, анализ одного элемента массива вне зависимости от количества элементов;
О(log2 n) – алгоритм двоичного поиска;
О(n) - алгоритм линейной сложности, когда для каждого входного объекта выполняется только одно действие;
О(n log2 n) - такую сложность имеет алгоритм быстрой сортировки;
O(n2) - квадратичные алгоритмы. В основном, все простейшие алгоритмы сортировки.
O(nx) - полиномиальные алгоритмы.
O(xn) - экспоненциальные алгоритмы.
О(n!) - факториальные алгоритмы.

Слайд 34

Временная сложность рекурсивного алгоритма для задачи «Ханойские башни»
Решение задачи для n

дисков сводится к решению двух подзадач и одному ходу. Обе подзадачи имеют не половинный размер, а размер, лишь на единицу меньший исходного. Подсчитаем требуемое число ходов T(n). С учетом структуры решения:
T(n) = 2T(n-1) +Tход
а=2, с=n/(n-1), следовательно a>c, и задача имеет экспоненциальный порядок сложности. По индукции можно доказать, что
T(n)=2n-1+2n-2+…2+1=2n-1.

Слайд 35

Зависимость сложности от n. P-задачи
Алгоритм, для которого t(n)=O(nx), где x –

неотрицательная константа, называют полиномиальными

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

Слайд 36

Экспоненциальные и NP-задачи
NP-задачи - это класс задач, которые можно решить за

полиномиальное время (Р), но на машине, более мощной, чем обычная однопроцессорная машина — на недетерминированном (N) вычислителе.

Генератор варианта решения

Проверка варианта - решение?

да

нет

P ⊆ NP. Верно ли обратное (и тогда Р = NP) или существуют задачи, решаемые за полиномиальное время на недетерминированной машине, но требующие экспоненциального времени на однопроцессорной машине (тогда Р ⊂ NP, NP \ Р≠∅) ?

Слайд 37

NP-полные задачи
Основная теорема. Если некоторая NP – полная задача разрешима за

полиномиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не разрешимая за полиномиальное время, то все NP – полные задачи таковы.

NP-полные

Рекурсия и сложность

Содержание

Рекурсия и ее реализацияРекурсия реализуется на основе подпрограммы, вызывающей саму себя.

Этапы разработки рекурсивного алгоритма решения задачи1) параметризация задачи, т.е. выявление различных

Рекурсивный алгоритм вычисления факториалаФормула факториала:n! =n*(n – 1)*(n – 2)*...*1 управляющий

Рекурсивная программа вычисления факториала#include "stdafx.h"#include long int fact(int i){ if (i==0) return

Работа рекурсивной программы со стекомСтек при первом вызове fact (i=5)Cтек при

Роль стека при вызове подпрограммы В из А 1. В вершину стека помещается

Рекурсивное вычисление чисел ФибоначчиF(1)=1,F(2)=1,для любого n>2 F(n)=F(n-1)+F(n-2)#include "stdafx.h"#include long int fib(long

Задача «Ханойские башни»Существует легенда: «В храме Бендареса находится бронзовая плита с

Алгоритм решения задачи «Ханойские башни»Назовем стержни левым (left), средним (middle) и

Программа «Ханойские башни»: обозначенияОбозначим тот стержень, с которого следует снять диски,

#include "stdafx.h"#include enum st {left,middle,right};void name(st ster){ switch (ster){ case 0: printf(" left

Хранение бинарных деревьев

Обходы бинарных деревьевПрямой (корень – левое поддерево - правое поддерево); обратный

Прямой обходvoid pr(struct tree *root){ if(!root) return;if(root->info) printf("%c ", root->info); pr(root->left);

Обратный обходvoid obr(struct tree *root){ if(!root) return;obr(root->left); obr(root->right); if(root->info) printf("%c ",

Симметричный обходvoid sim(struct tree *root){ if(!root) return;sim(root->left); if(root->info) printf("%c ", root->info);

Переборные задачи. #include "stdafx.h"#include int a[20];int k;void write_number(){ printf("\n"); for (int j=0;j}void

Пример работы программы для k=3Если i=k+1, то find(k+1) запускает write_number для

Задача о расстановке n ферзейfor i1 := 1 to n do

Отсечения при перебореfor i1 := 1 to n do begin ферзь[1]

Простые примеры задач на динамическое программированиеVar D : Array [1..50] of

Жадные алгоритмыЖадный алгоритм (greedy algorithm) – это метод решения оптимизационных задач,

Дискретная и непрерывная задача о рюкзакеПостановка дискретной задачи. В рюкзак загружаются

Непрерывная задача о рюкзакеЖадный алгоритм:Вычислим цены всех предметов - стоимость предмета

Неоптимальность жадного алгоритма для дискретной задачи10203060 y.е. в целом, 6 за

Размер задачи, временная сложностьАлгоритмическая временная сложность — это зависимость времени исполнения

Оценка временной сложности операторов программыTif = Tv+max(Tthen+1,Telse).1 операция по ветке Then

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

Порядок сложности нерекурсивных и рекурсивных функцийs=0;for i:=1 to n do

Грубая оценка временной сложности рекурсивной программы Если верны соотношения T(1)=d; T(n)=a*T(n/c)+b*n, то в

Классы сложности алгоритмовО(1) - количество шагов алгоритма не зависит от количества

Временная сложность рекурсивного алгоритма для задачи «Ханойские башни»Решение задачи для n

Зависимость сложности от n. P-задачиАлгоритм, для которого t(n)=O(nx), где x –

Экспоненциальные и NP-задачиNP-задачи - это класс задач, которые можно решить за

NP-полные задачиОсновная теорема. Если некоторая NP – полная задача разрешима за

Похожие презентации