правил
Вычисление факториала
Последовательность Фибоначчи
Задача о Ханойских башнях
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Рекурсия в ПРОЛОГе презентация
Содержание
- 1. Рекурсия в ПРОЛОГе
- 2. Понятие рекурсии Рекурсия — способ организации действий, при
- 3. Рекурсия в художественных образах клип Гравюра голландского художника Мориса Эшера "Рисующие руки"
- 4. ПРИМЕРЫ РЕКУРСИИ У попа была собака,
- 5. Рекурсия в природе
- 6. Рекурсия в математике: Треугольник Серпиньского
- 7. Рекурсия в математике: Снежинка Коха
- 8. Рекурсия в математике: Алгебраические фракталы
- 9. Примеры рекурсивных определений 1. Сумма первых N
- 10. Рекурсивные правила в ПРОЛОГе Рекурсивное правило
- 11. Примеры рекурсивных правил: Вычисление факториала n!=1*2*3*...*(n-1)*n.
- 12. fact (0, 1):- !. fact (N,
- 13. Примеры рекурсивных правил: Числа Фибоначчи F(1)=1,
- 14. Правило для вычисления n-го числа Фибоначчи fib(N,F),
- 15. Задача о Ханойских башнях (1)А
- 16. Рекурсивное правило для N дисков
- 17. Задача о Ханойских башнях А В С
Понятие рекурсии Рекурсия — способ организации действий, при котором процесс обращается сам к себе. Рекурсивным называется любой объект, который частично определяется через себя.
Слайд 1 Рекурсия в ПРОЛОГе
Понятие рекурсии
Примеры рекурсивных объектов
Рекурсивные правила в ПРОЛОГе
Примеры рекурсивных
Слайд 2Понятие рекурсии
Рекурсия — способ организации действий, при котором процесс обращается сам к
себе.
Рекурсивным называется любой объект, который частично определяется через себя.
Рекурсивным называется любой объект, который частично определяется через себя.
Слайд 3Рекурсия в художественных образах
клип
Гравюра голландского художника Мориса Эшера "Рисующие руки"
Слайд 4ПРИМЕРЫ РЕКУРСИИ
У попа была собака, он её любил,
Она съела кусок мяса,
он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…
Слайд 6Рекурсия в математике:
Треугольник Серпиньского
фрактал, один из двумерных аналогов
множества Кантора предложенный польским математиком В. Серпиньским в 1915 году. Также известен как «решётка» или «салфетка» Серпиньского.
Слайд 8Рекурсия в математике:
Алгебраические фракталы
Множество Мандельброта .
Алгоритм построения основан
на простом итеративном выражении: Z[i+1] = Z[i] * Z[i] + C, где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости.
Слайд 9Примеры рекурсивных определений
1. Сумма первых N натуральных чисел
S(N)=1+2+3+…+(N-1)+N
S(N)=
2. Степень с натуральным показателем
Xn = Xn-1*X
Xn =
Слайд 10Рекурсивные правила в ПРОЛОГе
Рекурсивное правило
Рекурсивная часть
(обращение к себе)
нерекурсивная часть
(остановка рекурсии)
Слайд 11Примеры рекурсивных правил:
Вычисление факториала
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.
fact (0, 1):- !.
% рекурсивная часть правила: n! = (n-1)!*n
fact (N, FN):- M=N–1, fact (M, FM), FN=FM*N.
n!=
Слайд 12 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
Слайд 13Примеры рекурсивных правил:
Числа Фибоначчи
F(1)=1, Ff(2)=1, F(n)=F(n-1)+F(n-2).
1, 1, 2, 3, 5,
8, 13, 21,...
F(n) =
F(n) =
Слайд 14Правило для вычисления 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.
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.
Слайд 15Задача о Ханойских башнях
(1)А → В:
Разложение исходной задачи на подзадачи:
(1)
Переложить 1,2-й диски с А на В (А→В)
(2) Переложить 3-й диск с А на С (А→С)
(3) Переложить 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
Слайд 16Рекурсивное правило для 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).
Слайд 17Задача о Ханойских башнях
А
В
С
Перенести диск с 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
Перенести диск с 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
