Рекурсия - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсия. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Глава 9. Рекурсия МГТУ им. Н.Э. Баумана Факультет Информатика и системы управления Кафедра Компьютерные системы и сети Лектор: к.т.н., доцент Ничушкина Татьяна Николаевна

Слайд 2

Описание слайда:

9.1 Основные понятия Существует допустимая математическая форма определений, при построении которой определяемое понятие используется и как заголовок, и как ее элемент. Эта форма называется рекурсивной или индуктивной. Любое рекурсивное утверждение строится с помощью двух утверждений, символизирующих собой две независимые части рекурсивного определения. Первое утверждение носит названия базисного. Именно оно служит признаком завершения рекурсивной процедуры и является не рекурсивным. Второе утверждение носит название рекурсивного. Рекурсивное утверждение записывается так, чтобы при цепочке повторных применений оно редуцировалось к базовому. Например: определить понятие нечетное число Базисное утверждение: 1 нечетное число. Рекурсивное утверждение: Если I является нечетным, то нечетными являются числа, определяемые выражениями I-2, I+2 .

Слайд 3

Описание слайда:

Основные понятия (2) Используя это определение, докажем. Что 7 – нечетное число. 7-2 ->5 5-2 -> 3 3-2-> 1 1 -> нечетное -> 3 -> 5 -> 7 – нечетное. База указывает один или более случаев, удовлетворяющих определению. Рекурсивная часть показывает, как надо применить определение, что бы проверить, удовлетворяют ли ему другие случаи. Но есть еще и неявная часть рекурсии, которая, по умолчанию, утверждает, что никакие другие объекты не удовлетворяют определению. Пример: Написать рекурсивное определение возведения числа x в степень n: Базисное утверждение x0=1; Рекурсивное утверждение xn=x*xn-1; Определим 35 35= 34*3 34= 33*3 …….

Слайд 4

Описание слайда:

Основные понятия (3) Приведенное рекурсивное определение называется линейным, так как в формировании результата принимает участие одна величина, требующая дополнительного вычисления. Еще одним примером линейной рекурсии является вычисление факториала числа: База 1!=1; 0!=1; Рекурсивное: N!=N*(N-1)! Однако, есть рекурсивные определения, при вычислении по которым, на каждом уровне необходимо вычисление двух выражений, требующих дополнительного вычисления. Пример: числа Фибоначчи 1 1 2 3 5 8 13 21 34 55 89 …. Базисное утверждение: F1=1 и F2=1 Рекурсивное Fn=Fn-1+Fn-2 Найдем значение 5 числа Фибоначчи: F5=F4 + F3; F4=F3+F2 F3=F2+F1; F3=F2+F1 F2=1; F1=1; F2=1, F1=1.

Слайд 5

Описание слайда:

Основные понятия(4) Рекурсивная подпрограмма – организация вычислений, при которой процедура или функция обращается к самой себе. Различают: явную и косвенную рекурсии. При явной – в теле подпрограммы существует вызов самой себя, при косвенной – вызов осуществляется в подпрограммах, вызываемых из рассматриваемой. Косвенная рекурсия требует предопределения: void B(int j); void A(int k); { ...B(i);... } void B(int j); {... A(j);... }

Слайд 6

$Вычисление целой степени целого числа // Ex9_1.cpp #include "stdafx.h" #include long int funstep(int x,int n) { if (n==0) return 1; else...$

Описание слайда:

Вычисление целой степени целого числа // Ex9_1.cpp #include "stdafx.h" #include long int funstep(int x,int n) { if (n==0) return 1; else {return x*funstep(x,n-1);} } int main(int argc, char* argv[]) {int x,n; puts("input x,n for x^n"); scanf("%d %d",&x,&n); printf("\n %7d ^ %3d =",x,n); printf("%10d\n",funstep(x,n)); return 0; }

Слайд 7

$Вычисление n - го числа Фибоначчи // Ex9_2.cpp #include "stdafx.h" #include int fib(int n) {if((n==1)||(n==2)) return 1; else { return...$

Описание слайда:

Вычисление n - го числа Фибоначчи // Ex9_2.cpp #include "stdafx.h" #include int fib(int n) {if((n==1)||(n==2)) return 1; else { return fib(n-1)+ fib(n-2);} } int main(int argc, char* argv[]) {int n; puts("input n value Fibonnachi"); scanf("%d",&n); printf("\n %7d Fibonachi =",n); printf("%10d\n",fib(n)); return 0; }

Слайд 8

Описание слайда:

Вычисление наибольшего общего делителя

Слайд 9

$Вычисление наибольшего общего делителя (4)‏ // Ex9_3.cpp . #include "stdafx.h" #include int nod(int a,int b) {if(a==b) return a; else { if...$

Описание слайда:

Вычисление наибольшего общего делителя (4)‏ // Ex9_3.cpp . #include "stdafx.h" #include int nod(int a,int b) {if(a==b) return a; else { if (a>b) return nod(a-b,b); else return nod(a,b-a); } } int main(int argc, char* argv[]) {int a,b; puts("input two integer value "); scanf("%d %d",&a,&b); printf("\n nod %7d %7d = %7d\n",a,b,nod(a,b)); return 0; }

Слайд 10

Описание слайда:

Вычисление наибольшего общего делителя(3)

Слайд 11

$Вычисление наибольшего общего делителя (2)‏ // Ex9_4.cpp #include "stdafx.h" #include void nod(int a,int b,int &r) {if(a==b) r=a; else { if...$

Описание слайда:

Вычисление наибольшего общего делителя (2)‏ // Ex9_4.cpp #include "stdafx.h" #include void nod(int a,int b,int &r) {if(a==b) r=a; else { if (a>b)nod(a-b,b,r); else nod(a,b-a,r); } } int main(int argc, char* argv[]) {int a,b,r; puts("input two integer value "); scanf("%d %d",&a,&b); nod(a,b,r); printf("\n nod %7d %7d = %7d\n",a,b,r); return 0; }

Слайд 12

Описание слайда:

9.2 Фрейм активации. Структура рекурсивной подпрограммы Каждое обращение к рекурсивной подпрограмме вызывает независимую активацию этой подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом активации. Фрейм активации включает локальные переменные подпрограммы; копии параметров-значений; адреса параметров-переменных и параметров-констант (4 байта); копию строки результата (для функций типа string); служебную информацию (12 байт, точный размер этой области зависит от способа передачи параметров).

Слайд 13

Описание слайда:

Переворот строки 1) последовательное отсечение начального элемента и добавление его в конец результирующей строки: (Ex9_5) char * reverse (char * s) { char s1[2],* ptr=s; if (strlen(s)==0){s[0]='\0';return s;} else {s1[0]=s[0];s1[1]='\0'; return strcat(reverse(strcpy(s,ptr+1)),s1);} } Фрейм активации: V=4 + 2+4+256 + 278.

Слайд 14

$Переворот строки 2) последовательная перестановка элементов(Ex9_6), например ABCDE  EBCDA  EDCBA void reverse (char * s,int n) {char temp; if (n$

Описание слайда:

Переворот строки 2) последовательная перестановка элементов(Ex9_6), например ABCDE  EBCDA  EDCBA void reverse (char * s,int n) {char temp; if (n

Слайд 15

Описание слайда:

Определение корней уравнения на заданном отрезке Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения погрешности, то координата середины отрезка и есть корень. Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

Слайд 16

Описание слайда:

Определение корней уравнения на заданном отрезке (2)‏ // Ex9_7.cpp #include "stdafx.h" #include #include void root(float a,float b,float eps,float &r) {float x,f; x=(a+b)/2; f=x*x-1; if (fabs(f)>=eps) if ((a*a-1)*f>0) root(x,b,eps,r); else root(a,x,eps,r); else r=x; }

Слайд 17

Описание слайда:

Определение корней уравнения на заданном отрезке (2)‏ // Основная программа int main(int argc, char* argv[]) { float a,b,eps,r; puts("Input a,b,eps"); scanf("%f %f %f",&a,&b,&eps); if ((a*a-1)*(b*b-1)

Слайд 18

Описание слайда:

Структура рекурсивной подпрограммы «Операторы после вызова», выполняются после возврата управления из рекурсивно вызванной подпрограммы. Пример. Распечатать положительные элементы массива в порядке следования, а отрицательные элементы – в обратном порядке. Признак конца массива – 0.

Слайд 19

Описание слайда:

Просмотр массива

Слайд 20

$Просмотр массива // Ex9_8.cpp #include "stdafx.h" #include // рекурсивная подпрограмма void print(int x[],int i) {if (x[i]==0)...$

Описание слайда:

Просмотр массива // Ex9_8.cpp #include "stdafx.h" #include // рекурсивная подпрограмма void print(int x[],int i) {if (x[i]==0) puts("***********"); else {if (x[i]>0)printf("%4d\n",x[i]); print(x,i+1); if (x[i]

Слайд 21

Описание слайда:

Просмотр массива (2)‏ // основная программа int main(int argc, char* argv[]) {int i,x[40]; puts("input massiv v konce 0"); i=-1; do {i=i+1; scanf("%d",&x[i]); }while (x[i]!=0); puts(" RESULT "); print(x,0); return 0; }

Слайд 22

Описание слайда:

9.3 Древовидная рекурсия. Перестановки 1,2,3  123,132, 213, 231, 312, 321. Схема формирования перестановок:

Слайд 23

$Перестановки (2)‏ // Ex9_9.cpp #include "stdafx.h" #include void perest(int n,int m,const int r[],int pole[]) {int r1[3],k,i,j; if (n==m){...$

Описание слайда:

Перестановки (2)‏ // Ex9_9.cpp #include "stdafx.h" #include void perest(int n,int m,const int r[],int pole[]) {int r1[3],k,i,j; if (n==m){ for(i=0;i

Слайд 24

Описание слайда:

Перестановки (3)‏ for(j=0;j

Слайд 25

Описание слайда:

9.4 Полный и ограниченный перебор Пример. Расставить N ферзей на доске N*N так, чтобы они не били друг друга.

Слайд 26

Описание слайда:

Дерево формирования вариантов

Слайд 27

Описание слайда:

Схема алгоритма расстановки ферзей

Слайд 28

Описание слайда:

Программа расстановки ферзей // Ex9_10.cpp #include "stdafx.h" #include #include // Функция проверки корректности варианта int new_r(int n,int pole[]) {int r=1; for(int j=0;j