Рекурсия в ПРОЛОГе


The Presentation inside:

Slide 0

Рекурсия в ПРОЛОГе Понятие рекурсии Примеры рекурсивных объектов Рекурсивные правила в ПРОЛОГе Примеры рекурсивных правил Вычисление факториала Последовательность Фибоначчи Задача о Ханойских башнях


Slide 1

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


Slide 2

Рекурсия  в художественных образах клип Гравюра голландского художника Мориса Эшера "Рисующие руки"


Slide 3

ПРИМЕРЫ РЕКУРСИИ У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …


Slide 4

Рекурсия в природе


Slide 5

Рекурсия в математике: Треугольник Серпиньского фрактал, один из двумерных аналогов множества Кантора предложенный польским математиком В. Серпиньским в 1915 году. Также известен как «решётка» или «салфетка» Серпиньского.


Slide 6

Рекурсия в математике: Снежинка Коха


Slide 7

Рекурсия в математике: Алгебраические фракталы Множество Мандельброта . Алгоритм построения основан на простом итеративном выражении: Z[i+1] = Z[i] * Z[i] + C, где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости.


Slide 8

Примеры рекурсивных определений 1. Сумма первых N натуральных чисел S(N)=1+2+3+…+(N-1)+N S(N)= 2. Степень с натуральным показателем Xn = Xn-1*X Xn =


Slide 9

Рекурсивные правила в ПРОЛОГе Рекурсивное правило Рекурсивная часть (обращение к себе) нерекурсивная часть (остановка рекурсии)


Slide 10

Примеры рекурсивных правил: Вычисление факториала n!=1*2*3*...*(n-1)*n. Граничное условие: n=0 % нерекурсивная часть правила : 0! = 1 fact (0, 1):- !. % рекурсивная часть правила: n! = (n-1)!*n fact (N, FN):- M=N–1, fact (M, FM), FN=FM*N. n!=


Slide 11

fact (0, 1):- !. fact (N, FN):- M=N–1, fact (M, FM), FN=FM*N. fact (3, FN) ----------------------- N=3 FN= M=N-1 -------------- 2=3 -1 fact (2, FM) ----------------------- M=2 FM= FN=FM*N ----------------- M’=M-1 -------------- 1=2 -1 fact (1, FM’) ----------------------- M’ = 1 FM’= FM=FM’*M ------------------- M’’=M’-1 -------------- 0=1 -1 fact (0, FM’’) ----------------------- M’’=0 FM’’= 1 FM’=FM’’*M’ -------------------- FM’=1*1=1 6 FN=2*3=6 FM=1*2=2 1 2


Slide 12

Примеры рекурсивных правил: Числа Фибоначчи F(1)=1, Ff(2)=1, F(n)=F(n-1)+F(n-2). 1, 1, 2, 3, 5, 8, 13, 21,... F(n) =


Slide 13

Правило для вычисления n-го числа Фибоначчи fib(N,F), N-порядковый номер, F- значение N-го числа Фибоначчи fib(1,1):-!. %F(1) =1 fib(2,1):-!. %F(2) =1 fib(N,F):- %F(N)=F(N-1)+F(N-2) N1=N-1,fib(N1,F1), N2=N-2,fib(N2,F2), F=F1+F2.


Slide 14

Задача о Ханойских башнях (1)А > В: Разложение исходной задачи на подзадачи: (1) Переложить 1,2-й диски с А на В (А>В) (2) Переложить 3-й диск с А на С (А>С) (3) Переложить 1,2-й диски с В на С (В>С) (3)B > C: C>В А>С А>В B>A B>C А>C A A A B B B C C C Решение подзадач: 1,2 1,2 Решение при N=3


Slide 15

Рекурсивное правило для N дисков move(1,A,B,C):- write("Перенести диск с ", A, " на  ",C),nl,!. move(N,A,B,C):- M=N-1,move(M,A,C,B), write("Перенести диск с ", A ," на  ",C),nl, move(M,B,A,C).


Slide 16

Задача о Ханойских башнях А В С Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Перенести диск с A на B Перенести диск с C на A Перенести диск с C на B Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Перенести диск с B на A Перенести диск с C на A Перенести диск с B на C Перенести диск с A на B Перенести диск с A на C Перенести диск с B на C Количество перемещений 2n -1


×

HTML:





Ссылка: