Пример 3. Ханойские башни

Имеется три стержня: A, B и C. На стержне А надеты N дисков разного диаметра, надетые друг на друга в порядке убывания диаметров. Необходимо переместить диски со стержня А на стержень С, используя В как вспомогательный, если перекладывать можно только по одному диску и нельзя больший диск класть на меньший.

Решение:

Составим правило move, определяющее порядок переноса дисков.

Нерекурсивная часть правила определяет действие, если на стержне находится 1 диск.

Рекурсивная часть правила перемещает сначала верхние (N-1) диск на стержень B, используя С как вспомогательный, затем оставшийся диск на стержень C и, наконец, диски со стержня B на C, используя А как вспомогательный.

PREDICATES

move(integer, char, char, char)

CLAUSES

move(1, A, B, C): - write(“Perenesti disk c”, A, “ na ”, C), nl,!.

move(N, A, B, C): - M=N-1, move(M, A, C, B), write(“Perenesti disk c”, A, “ na ”, C), nl, move(M, B, A, C).

GOAL

write(“Xanoiskie bashni”), nl, write(“Kolichestvo diskov: ”), readint(N), nl, move(N, ‘A’, ‘B’, ‘C’).

Результат выполнения программы (рис. 5):

Ханойские башни

Количество дисков: 3

Перенести диск с A на C

Перенести диск с A на B

Перенести диск с C на B

Перенести диск с A на C

Перенести диск с B на A

Перенести диск с B на C

Перенести диск с A на C

Рис. 5. Вывод результата программы «Ханойские башни»

Контрольные задания:

Напишите программу, которая передаёт ту же информацию, что и следующие факты и предложения, на языке Пролог согласно варианту, выданному преподавателем:

Вариант 1. Вычислить сумму 1+2+3+…+N.

Вариант 2. Подсчитать сумму ряда целых четных чисел от 2 до N.

Вариант 3. Вычислить сумму ряда целых нечетных чисел от 1 до n.

Вариант 4. Найти значение произведения: 2*4*6*...*26.

Вариант 5. Найти значение произведения: 1*3*5*...*11.

Вариант 6. Используя базу данных и правило предок, составить правило для определения всех предков-дедушек.

Вариант 7. Используя базу данных и правило предок, составить правило для определения всех предков-бабушек.

Вариант 8. Используя базу данных и правило предок, составить правило для определения всех потомков-мужчин.

Вариант 9. Используя базу данных и правило предок, составить правило для определения всех потомков-женщин.

Контрольные вопросы:

1. Что такое рекурсивная процедура?

2. Из каких частей состоит рекурсия, охарактеризуйте их?

3. Что такое граничное условие?

4. Где обычно применяется рекурсия?

5. Назовите преимущества рекурсии.

6. В чем недостаток рекурсии?

7. Что называют оптимизацией обратной рекурсии?