 |
Произвольные структуры (деревья)
|
|
|
|
УДК 004.4 (076.1)
Васяшин А.В. Сборник задач по курсу «Логическое программирование». Учебное пособие. – Обнинск: ИАТЭ, 2009. – 73 с.
Пособие представляет собой сборник лабораторных работ по логическому программированию. Каждой из пяти лабораторных работ соответствует свой набор индивидуальных заданий (задач).
Первые четыре лабораторные работы посвящены работе со списками и структурами языка «Пролог» и основным методом решения этих задач является рекурсия. Задачи последнего раздела посвящены работе с базой данных «Пролога», а основным приёмом их решения является «вынуждаемый возврат».
Рецензенты: к.т.н. О.А. Мирзеабасов,
с.н.с. Г.М. Жердев.
Темплан 2009, поз. 9
© Обнинский государственный технический университет атомной энергетики, 2009.
© А.В. Васяшин, 2009.
Предисловие
Все представленные ниже лабораторные работы разбиты на четыре темы. Первые три темы, а именно, «Списки и строки», «Бинарные деревья», «Произвольные структуры» включают в себя наборы задач на основной прием программирования в Прологе – рекурсию. При выполнении работ по этим темам допускается использовать любой тип рекурсии (входящую или исходящую). Последняя тема «Файлы и разделы базы данных» предполагает использование в качестве основного приема программирования «вынуждаемый возврат».
Описание каждой задачи состоит из трех частей:
ü словесная формулировка задачи;
ü список аргументов;
ü примеры запросов к разработанной процедуре в среде интерпретатора и получаемые ответы.
При выполнении лабораторных работ требуется строго выполнять два требования:
ü нельзя изменять количество и смысл аргументов;
ü нельзя решать задачу для частных случаев.
|
|
|
Последнее требование означает, что разработанная процедура должна быть универсальна. Так для задачи № 1 (см. ниже) процедура должна работать со списками произвольной длины, содержащими любые термы Пролога.
В примерах запросов все процедуры имеют имя pred. Это не является требованием. Напротив, рекомендуется называть процедуру так, чтобы в наименовании отражался смысл ее работы. Для задачи № 1, например, диалог в интерпретаторе Пролога может быть таким:
?- sorted([a,b,d,f]).
yes
?- sorted([[a,f,b,d]).
no
?-
Списки и строки
1. Определить, является ли список упорядоченным по возрастанию.
Аргументы: исходный список.
?- pred([a,b,d,f]).
yes
?- pred([[a,f,b,d]).
no
?-
2. Определить, имеет ли список четное число элементов, не прибегая к подсчету длины списка.
Аргументы: исходный список.
?- pred([a,b,d,f]).
yes
?- pred([[a,b,d]).
no
?-
3. Перевести число из десятичной системы счисления в двоичную.
Аргументы: число в десятичной с.с.;
число в двоичной с.с. (список).
?- pred(26,X).
X = [1,1,0,1,0]
yes
?-
4. Найти в неупорядоченном списке вещественных чисел ближайших соседей – два числа, расстояние между которыми на вещественной оси является минимальным среди всех возможных пар.
Аргументы: исходный список;
ближайшие соседи (список из двух чисел).
?- pred([0.1,0.04,8.6,7.56,8.11],X).
X = [8.6,8.11]
yes
?-
5. Перевести число из двоичной системы счисления в десятичную.
Аргументы: число в двоичной с.с. (список);
число в десятичной с.с.
?- pred([1,1,0,1,0],X).
X = 26
yes
?-
6. Перевести число из десятичной системы счисления в римскую.
Аргументы: число в десятичной с.с.;
число в римской с.с. (список).
?- pred(24,X).
X = [x,x,i,v]
yes
?-
7. Перевести число из римской системы счисления в десятичную.
Аргументы: число в римской с.с. (список);
число в десятичной с.с.
?- pred([x,x,i,v],X).
X = 24
yes
?-
8. Перевести число из двоичной системы счисления в шестнадцатеричную.
Аргументы: число в двоичной с.с. (список);
число в шестнадцатеричной с.с. (список).
?- pred([1,1,0,1,0],X).
X = [1,a]
yes
?-
|
|
|
9. Перевести число из шестнадцатеричной системы счисления в двоичную.
Аргументы: число в шестнадцатеричной с.с. (список);
число в двоичной с.с. (список).
?- pred([1,a],X).
X = [1,1,0,1,0]
yes
?-
10. Определить, является ли первый список подмножеством второго. Списки не имеют дубликатов.
Аргументы: первый список;
второй список.
?- pred([a,b,c],[s,a,e,c,d,b]).
yes
?-
11. Удалить из списка элементы с четными номерами.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [a,c,e]
yes
?-
12. Удалить из списка те элементы, которые не имеют дубликатов.
Аргументы: исходный список;
результирующий список.
?- pred([a,e,c,d,e],X).
X = [e,e]
yes
?-
13. Дан числовой список – [ A, B, C, D, E,…]. Посчитать результат по формуле R=A+B−C+D−E+ ….
Аргументы: исходный список;
результат вычислений.
?- pred([1,2,3,4,5],X).
X = -1
yes
?-
14. Сформировать по заданному мужскому имени отчество.
Аргументы: исходная строка (имя);
результирующая строка (отчество).
?- pred(’Иван’,X).
X = Иванович
yes
?-
15. Дан список, содержащий списки одинаковой длины (матрица). Построить транспонированную матрицу.
Аргументы: матрица (список);
транспонированная матрица (список).
?- pred([[1,2,3],[4,5,6],[7,8,9]],X).
X = [[1,4,7],[2,5,8],[3,6,9]]
yes
?-
16. Дан список, содержащий списки одинаковой длины (квадратная матрица). Посчитать детерминант.
Аргументы: матрица (список);
детерминант.
?- pred([[1,2],[4,5]],X).
X = -3
yes
?-
17. Удалить из числового списка элементы, меньшие заданного числа.
Аргументы: исходный список;
число;
результирующий список.
?- pred([3,1,5,4,8],5,X).
X = [5,8]
yes
?-
18. Удалить из списка элемент с заданным порядковым номером.
Аргументы: исходный список;
порядковый номер;
результирующий список.
?- pred([a,b,c,d,e],4,X).
X = [a,b,c,e]
yes
?-
19. Поместить в результирующий список каждый элемент исходного списка с заданной вероятностью.
Аргументы: исходный список;
вероятность вхождения;
результирующий список.
?- pred([a,b,c,d,e],0.5,X).
X = [a,c,d]
yes
?- pred([a,b,c,d,e],0.5,X).
X = [b,c,d,e]
yes
?-
20. Выполнить циклический сдвиг списка влево на заданное количество элементов.
Аргументы: исходный список;
количество элементов;
результирующий список.
?- pred([a,b,c,d,e],3,X).
X = [d,e,a,b,c]
yes
?-
21. Выполнить циклический сдвиг списка вправо на заданное количество элементов.
Аргументы: исходный список;
количество элементов;
результирующий список.
?- pred([a,b,c,d,e],3,X).
X = [c,d,e,a,b] ->;
yes
?-
|
|
|
22. Получить целое число из строки, использующей числительные русского языка.
Аргументы: строка;
целое число.
?- pred(’Пять тысяч восемьсот одиннадцать’,X).
X = 5811
yes
?-
23. Даны два списка. Каждый из списков не имеет дубликатов и, следовательно, их можно рассматривать как множества. Построить симметрическую разность (объединение минус пересечение) списков.
Аргументы: первый список;
второй список;
результирующий список.
?- pred([a,b,c,d,e],[e,w,q,c],X).
X = [a,b,d,w,q] ->;
yes
?-
24. Дан список, содержащий числовые списки одинаковой длины (матрица), и числовой список (вектор). Перемножить матрицу и вектор.
Аргументы: матрица (список);
вектор (список);
результат перемножения (список).
?- pred([[1,2],[4,5]],[2,3],X).
X = [8,23]
yes
?-
25. Дан числовой список [ a, b, c, d, … ] и число x. Посчитать значение полинома R = a+bx+cx 2 +dx 3 + ….
Аргументы: список;
число;
результат вычислений.
?- pred([1,2,4,1],3,X).
X = 70
yes
?-
26. Преобразовать целое число в строку с использованием числительных русского языка.
Аргументы: целое число;
строка.
?- pred(5811,X).
X = Пять тысяч восемьсот одиннадцать
yes
?-
27. Выполнить циклический сдвиг списка влево.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [b,c,d,e,a] ->;
X = [c,d,e,a,b] ->;
X = [d,e,a,b,c] ->;
X = [e,a,b,c,d] ->;
X = [a,b,c,d,e] ->;
X = [b,c,d,e,a] ->;
…
…
?-
28. Выполнить циклический сдвиг списка вправо.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [e,a,b,c,d] ->;
X = [d,e,a,b,c] ->;
X = [c,d,e,a,b] ->;
X = [b,c,d,e,a] ->;
X = [a,b,c,d,e] ->;
X = [e,a,b,c,d] ->;
…
…
?-
29. Найти порядковый номер максимального элемента числового списка.
Аргументы: исходный список;
порядковый номер.
?- pred([3,5,8,1,4],X).
X = 3
yes
?-
30. Найти все возможные пары элементов списка.
Аргументы: исходный список;
пара элементов (список).
?- pred([a,b,c,d,e],X).
X = [a,b] ->;
X = [a,c] ->;
X = [a,d] ->;
X = [a,e] ->;
X = [b,c] ->;
X = [b,d] ->;
X = [b,e] ->;
X = [c,d] ->;
X = [c,e] ->;
X = [d,e] ->;
no
?-
31. Найти все возможные перестановки элементов списка.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c],X).
X = [a,b,c] ->;
X = [a,c,b] ->;
X = [b,a,c] ->;
X = [b,c,a] ->;
X = [c,a,b] ->;
X = [c,b,a] ->;
no
?-
32. Строка текста на русском языке содержит «лишние» пробелы. Удалить избыточные пробелы.
|
|
|
Аргументы: исходная строка;
результирующая строка.
?- pred(’Мы будем рады узнать ваше мнение!’,X).
X = ’Мы будем рады узнать ваше мнение!’
yes
?-
33. Даны два числовых списка, содержащие коэффициенты двух полиномов. Соответствие между элементами списка и коэффициентами полинома можно отобразить следующим образом: a 0 +a 1 x+a 2 x 2 +a 3 x 3 +a 4 x 4 +… ®[ a 0, a 1, a 2, a 3, a 4,…]. Перемножить полиномы. Результирующий полином должен представлять собой список коэффициентов, составленный по тому же правилу, что и списки для исходных полиномов.
Аргументы: первый полином (список);
второй полином (список);
результирующий полином.
?- pred([3,5,8],[1,4],X).
X = [3,17,28,32]
yes
?-
34. Дан список и число N. Построить сочетания по N элементов из исходного списка.
Аргументы: исходный список;
целое число;
результирующий список.
?- pred([3,5,8,1],3,X).
X = [3,5,8]
X = [3,5,1]
X = [3,8,1]
X = [5,8,1]
no
?-
35. Преобразовать предложение на русском языке в список слов.
Аргументы: исходная строка;
список слов (строк).
?- pred(’Это будет работать, но возникнут две проблемы.’,X).
X = [Это,будет,работать,но,возникнут,две,проблемы]
yes
?-
36. Восстановить по отчеству имя.
Аргументы: исходная строка (отчество);
результирующая строка (имя).
?- pred(’Иванович’,X).
X = Иван
yes
?-
37. Подсчитать количество вхождений каждой буквы в строку текста на русском языке и собрать результаты в список.
Аргументы: исходная строка;
список пар вида «Буква: целое число».
?- pred(’Это будет работать’,X).
X = [Э:1,т:4,о:2,б:2,у:1,д:1,е:1,р:1,а:2,ь:1]
yes
?-
38. Произвести перекодировку строки текста на русском языке из кодировки DOS в кодировку Windows.
Аргументы: исходная строка (DOS);
результирующая строка (Windows).
?- pred(’Перевод получен’,X).
X =??а?ўR¤ ЇR<гз?-
yes
?-
39. Дан числовой список, содержащий первые N членов ряда, и порядковый номер элемента ряда K. Расчитать K -ый элемент ряда при условии, что каждый член ряда равен сумме N предыдущих его членов (за исключением N первых членов).
Аргументы: список первых членов ряда;
порядковый номер члена ряда;
член ряда.
?- pred([0,1,2],4,X).
X = 3
yes
?-
40. Произвести замену всех вхождений заданной подстроки в исходную строку на новую подстроку.
Аргументы: исходная строка;
подстрока для поиска;
подстрока для замены;
результирующая строка.
?- pred(’голод, холод’, ’од’, ’одом’,X).
X = ’голодом, холодом’
yes
?-
41. Дано предложение на русском языке. Построить список слов предложения. Список не должен содержать повторов слов и знаков препинания.
Аргументы: исходная строка;
список слов.
?- pred(’Что воля, что неволя...’,X).
X = [’что’,’воля’,’неволя’]
yes
?-
42. Дан список точек плоскости. Каждая точка задается парой координат (X, Y) и, таким образом, исходный список имеет вид [(X 1, Y 1),(X 2, Y 2),(X 3, Y 3), … ]. Преобразовать исходный список в список относительных координат вида [(X 1, Y 1),(D X 2,D Y 2),(D X 3,D Y 3), … ], где первая точка задается абсолютными координатами, а все последующие – в виде пары (сдвиг по оси X, сдвиг по оси Y) относительно предыдущей точки (D Xk=Xk−Xk- 1,D Yk=Yk−Yk- 1).
|
|
|
Аргументы: исходный список абсолютных координат;
список относительных координат.
?- pred([(1,2),(3,5),(2,0),(0,0)],X).
X = [(1,2),(2,3),(1,-5),(-2,0)]
yes
?-
Бинарные деревья
43. Определить наличие на каком-либо из путей от корня до листа хотя бы двух узлов с одинаковым именем.
Аргументы: произвольное бинарное дерево.
?- pred(a(f(a(m,k),r),n)).
yes
?- pred(a(f(d(m,k),r),n)).
no
?-
44. Определить наличие хотя бы двух узлов с одинаковым именем на одной глубине.
Аргументы: произвольное бинарное дерево.
?- pred(s(f(b(m,k),a),n(b,g))).
yes
?- pred(s(f(b(m,k),a),n(t,g))).
no
?-
45. Определить наличие двух одинаковых путей от корня до листа.
Аргументы: произвольное бинарное дерево.
?- pred(s(f(b(m,k),a),f(a,g))).
yes
?- pred(s(f(y(m,k),a),f(t,g))).
no
?-
46. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) над комплексными числами. Следует использовать имя «isс» для операции извлечения результата и стандартные «+, -, *, /, ^» для арифметических операций.
Аргументы: арифметическое выражение;
свободная переменная.
?- X isс (1.6, 4.5) + (2.8, 7.1).
X = (4.4, 11.6)
yes
?-
47. Определить глубину дерева.
Аргументы: произвольное бинарное дерево;
глубина дерева.
?- pred(s(f(b(m,k),a),f(a,g)),X).
X = 4
yes
?-
48. Определить, являются ли два заданных дерева равными с точностью до перестановки левого и правого поддерева в каждом узле.
Аргументы: первое дерево;
второе дерево.
?- pred(s(t(b(m,k),a),f(a,g)), s(t(b(k,m),a),f(g,a))).
yes
?- pred(s(t(b(m,k),a),f(a,g)), s(t(a,b(k,m)),f(g,a))).
yes
?-
49. Собрать все узлы в список.
Аргументы: произвольное бинарное дерево;
список узлов.
?- pred(s(f(b(m,k),a),f(a,g)),X).
X = [s,f,b,m,k,a,f,a,g]
yes
?-
50. В каждом узле дерева поменять при необходимости поддеревья местами так, чтобы в результирующем дереве в каждом узле выполнялось требование – количество узлов в левом поддереве не больше, чем в правом.
Аргументы: произвольное бинарное дерево;
результирующее дерево.
?- pred(s(f(b(m,k),a),t(a,g)),X).
X = s(t(a,g),f(a,b(m,k)))
yes
?-
51. Найти максимум количества узлов лежащих на одной глубине.
Аргументы: произвольное бинарное дерево;
количество узлов.
?- pred(s(f(b(m,k),a),t(r,w)),X).
X = 4
yes
?-
52. Собрать в список имена всех узлов дерева, лежащих на заданной глубине.
Аргументы: произвольное бинарное дерево;
необходимая глубина;
список узлов.
?- pred(s(f(b(m,k),a),t(a,g)),1,X).
X = [s]
yes
?- pred(s(f(b(m,k),a),t(a,g)),3,X).
X = [b,a,a,g]
yes
?- pred(s(f(b(m,k),a),t(a,g)),5,X).
X = []
yes
?-
53. Обрезать дерево на заданной глубине.
Аргументы: произвольное бинарное дерево;
необходимая глубина;
результирующее дерево.
?- pred(s(f(b(m,k),a),t(a,g)),2,X).
X = s(f,t)
yes
?- pred(s(f(b(m,k),a),t(a,g)),3,X).
X = s(f(b,a),t(a,g))
yes
?-
54. Произвести следующую процедуру над деревом, начиная обработку с корня: в текущем узле с заданной вероятностью принимается решение об усечении дерева в этом узле (узел становится листом).
Аргументы: произвольное бинарное дерево;
вероятность усечения;
результирующее дерево.
?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s(f,t(a,g))
yes
?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s(f(b,a),t)
yes
?- pred(s(f(b(m,k),a),t(a,g)),0.5,X).
X = s
yes
?-
55. Заданный узел в дереве сделать корнем дерева с той же связностью узлов, что и в исходном дереве. Результирующее дерево не является бинарным.
Аргументы: произвольное бинарное дерево;
имя узла;
результирующее дерево.
?- pred(s(f(b(m,k),w),t(a,g)),s,X).
X = s(f(b(m,k),w),t(a,g))
yes
?- pred(s(f(b(m,k),w),t(a,g)),f,X).
X = f(b(m,k),w,s(t(a,g)))
yes
?- pred(s(f(b(m,k),w),t(a,g)),a,X).
X = a(t(s(f(b(m,k),w)),g)
yes
?-
56. Подсчитать количество узлов дерева, лежащих на заданной глубине.
Аргументы: произвольное бинарное дерево;
необходимая глубина;
количество узлов.
?- pred(s(f(b(m,k),a),t(a,w)),1,X).
X = 1
yes
?- pred(s(f(b(m,k),a),t(a,w)),3,X).
X = 4
yes
?- pred(s(f(b(m,k),a),t(a,w)),4,X).
X = 2
yes
?-
57. Произвести обработку дерева в каждом узле по следующему правилу. Если узел имеет заданное имя, то все его дочерние узлы должны стать дочерними узлами его родительского узла, а сам этот узел удаляется из дерева.
Аргументы: произвольное бинарное дерево;
имя узла;
результирующее дерево.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,X).
X = s(f(u(i,o),v,k,a),t(g))
yes
?-
58. Подсчитать количество узлов с заданным именем.
Аргументы: произвольное бинарное дерево;
имя узла;
количество узлов.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,X).
X = 3
yes
?-
59. Определить путь между двумя заданными узлами.
Аргументы: произвольное бинарное дерево;
имя первого узла;
имя второго узла;
путь (список).
?- pred(s(f(w(b(u(i,o),v),k),a),t(r,g)),w,r,X).
X = [w,f,s,t,r]
yes
?- pred(s(f(w(b(u(i,o),v),k),a),t(r,g)),i,o,X).
X = [i,u,o]
yes
?-
60. Переименовать все узлы, имеющие заданное имя.
Аргументы: произвольное бинарное дерево;
старое имя узла;
новое имя узла;
результирующее дерево.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g)),b,r,X).
X = s(f(r(r(u(i,o),v),k),a),t(r,g))
yes
?-
61. Найти все поддеревья заданного дерева.
Аргументы: произвольное бинарное дерево;
поддерево.
?- pred(a(f(a(m,k),r),n(i,o)),X).
X = a(f(a(m,k),r),n(i,o)) ->;
X = f(a(m,k),r) ->;
X = a(m,k) ->;
X = m ->;
X = k ->;
X = r ->;
X = n(i,o) ->;
X = i ->;
X = o ->;
no
?-
62. Найти все пути в дереве от корня до его листьев.
Аргументы: произвольное бинарное дерево;
путь (список).
?- pred(a(f(a(m,k),r),n(i,o)),X).
X = [a,f,a,m] ->;
X = [a,f,a,k] ->;
X = [a,f,r] ->;
X = [a,n,i] ->;
X = [a,n,o] ->;
no
?-
63. Найти все пути от корня до его листьев, лежащих на максимальной глубине.
Аргументы: произвольное бинарное дерево;
путь (список).
?- pred(a(f(a(m,k),r),n(i,o)),X).
X = [a,f,a,m] ->;
X = [a,f,a,k] ->;
no
?-
64. Найти все поддеревья, имеющие глубину не больше заданной.
Аргументы: произвольное бинарное дерево;
максимальная глубина;
поддерево.
?- pred(a(f(a(m,k),r),n(i,o)),2,X).
X = a(m,k) ->;
X = m ->;
X = k ->;
X = r ->;
X = n(i,o) ->;
X = i ->;
X = o ->;
no
?-
65. Выполнить перебор листьев в порядке убывания их глубины.
Аргументы: произвольное бинарное дерево;
лист дерева.
?- pred(a(f(a(m,k),r),n(i(d,e),o)),X).
X = m ->;
X = k ->;
X = d ->;
X = e ->;
X = r ->;
X = o ->;
no
?-
66. Произвести приведение полинома.
Аргументы: исходный полином;
результирующий полином.
?- pred(2+6*x^3-7*x^2-4+x^3+6*x^2,X).
X = -2-x^2+7*x^3
yes
?-
67. Произвести символьное дифференцирование полинома, который задается структурой вида: a+b*x+c*x^ 2 +d*x^ 3 +…
Аргументы: исходный полином;
результирующий полином.
?- pred(2+6*x-7*x^3,X).
X = 6-21*x^2
yes
?-
68. Произвести деление полиномов. Исходные полиномы задаются структурами вида: a+b*x+c*x^ 2 +d*x^ 3 +…
Аргументы: первый полином;
второй полином;
результирующий полином, остаток от деления.
?- pred(2+6*x-7*x^3,1+x,X,Y).
X = -7*x^2+7*x-1
Y = 3
yes
?-
69. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) над множествами (списки). Следует использовать следующие имена операций: «iss» – операция извлечения результата; «+» – операция объединения; «*» – операция пересечения; «-» – операция вычитания.
Аргументы: арифметическое выражение (в арифметике множеств);
свободная переменная.
?- X iss [a,s,d,f] * [d,g,f] + [p,f].
X = [d,f,p]
yes
?-
70. Расширить синтаксис языка Пролог, введя операции (см. встроенный предикат op/3) модульной арифметики (арифметики вычетов, см. приложение В). Следует использовать имя «ism» для операции извлечения результата и стандартные «+, -, *, /» – для арифметических операций. Для хранения модуля, по которому производятся вычисления, необходимо использовать факт ism/1. В качестве модуля предполагается использовать только простые числа.
Аргументы: арифметическое выражение;
свободная переменная.
?- ism(X).
X = 3
yes
?- X ism (24+38)/2.
X = 1
yes
?-
71. Произвести перестановку поддеревьев в каждом узле дерева.
Аргументы: произвольное бинарное дерево;
результирующее дерево.
?- pred(s(f(b(m,k),a),f(a,g)),X).
X = s(f(g,a),f(a,b(m,k)))
yes
?-
Произвольные структуры (деревья)
72. Определить наличие на каком-либо из путей от корня до листа хотя бы двух узлов с одинаковым именем.
Аргументы: произвольное дерево.
?- pred(a(f(i(m,k),r,a(t)),n)).
yes
?- pred(a(f(i(m,k),r,o(t)),n)).
no
?-
73. Определить наличие хотя бы двух узлов с одинаковым именем на одной глубине.
Аргументы: произвольное дерево.
?- pred(s(f(b(m,k),a),n(b,g),r(u))).
yes
?- pred(s(f(b(m,k),a),n(t,g),r(u))).
no
?-
74. Определить наличие двух одинаковых путей от корня до листа.
Аргументы: произвольное дерево.
?- pred(s(f(b(m,k),a),f(a,g),n(h))).
yes
?- pred(s(f(y(m,k),a),f(t,g),n(h))).
no
?-
75. Определить глубину дерева.
Аргументы: произвольное дерево;
глубина дерева.
?- pred(s(f(b(m(i),k),a),f(a,g),h(y)),X).
X = 5
yes
?-
76. Определить, являются ли два заданных дерева равными с точностью до перестановки поддеревьев в каждом узле.
Аргументы: первое дерево;
второе дерево.
?- pred(s(t(b(m,k),a),f(a,g)), s(t(b(w,k,m),a),f(g))).
yes
?- pred(s(t(b(m,k),a),f(a,g)), s(t(a,b(k,m,w)),f(g))).
yes
?-
77. Собрать все узлы в список.
Аргументы: произвольное дерево;
список узлов.
?- pred(s(f(b(m,k,n),a(r)),f(a,g)),X).
X = [s,f,b,m,k,n,a,f,a,r,g]
yes
?-
78. Найти максимум количества узлов, лежащих на одной глубине.
Аргументы: произвольное дерево;
количество узлов.
?- pred(s(f(b(m,k(e),n),a),t(r,w)),X).
X = 4
yes
?-
79. Обрезать дерево на заданной глубине.
Аргументы: произвольное дерево;
необходимая глубина;
результирующее дерево.
?- pred(s(f(b(m,k),a),t(a,g),j(u)),2,X).
X = s(f,t,j)
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),3,X).
X = s(f(b,a),t(a,g),j(u))
yes
?-
80. Собрать в список имена всех узлов дерева, лежащих на заданной глубине.
Аргументы: произвольное дерево;
необходимая глубина;
список узлов.
?- pred(s(f(b(m,k),a),t(a,g),j(u)),1,X).
X = [s]
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),3,X).
X = [b,a,a,g,u]
yes
?- pred(s(f(b(m,k),a),t(a,g),j(u)),5,X).
X = []
yes
?-
81. Произвести следующую процедуру над деревом, начиная обработку с корня: в текущем узле с заданной вероятностью принимается решение об усечении дерева в этом узле (узел становится листом).
Аргументы: произвольное дерево;
вероятность усечения;
результирующее дерево.
?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s(f,t(a))
yes
?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s(f(b,a),t)
yes
?- pred(s(f(b(m,k),a),t(a)),0.5,X).
X = s
yes
?-
82. Найти в дереве все поддеревья, являющиеся бинарными.
Аргументы: произвольное дерево;
поддерево.
?- pred(a(f(a(m,k(v)),r),n(i(d,e,z(q,w)),o)),X).
X = z(q,w) ->;
no
?-
83. Сделать в дереве заданный узел корнем дерева с той же связностью узлов, что и в исходном дереве.
Аргументы: произвольное дерево;
имя узла;
результирующее дерево.
?- pred(s(f(b(m,k),w),t(a)),s,X).
X = s(f(b(m,k),w),t(a))
yes
?- pred(s(f(b(m,k),w),t(a)),f,X).
X = f(b(m,k),w,s(t(a)))
yes
?- pred(s(f(b(m,k),w),t(a)),a,X).
X = a(t(s(f(b(m,k),w)))
yes
?-
84. Подсчитать количество узлов дерева, лежащих на заданной глубине.
Аргументы: произвольное дерево;
необходимая глубина;
количество узлов.
?- pred(s(f(b(m,k),a),t(a)),1,X).
X = 1
yes
?- pred(s(f(b(m,k),a),t(a)),3,X).
X = 3
yes
?- pred(s(f(b(m,k),a),t(a)),4,X).
X = 2
yes
?-
85. Подсчитать количество узлов с заданным именем.
Аргументы: произвольное дерево;
имя узла;
количество узлов.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g,b(i))),b,X).
X = 4
yes
?-
86. Произвести обработку дерева в каждом узле по следующему правилу. Если узел имеет заданное имя, то все его дочерние узлы должны стать дочерними узлами его родительского узла, а сам этот узел удаляется из дерева.
Аргументы: произвольное дерево;
имя узла;
результирующее дерево.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b,g),b),b,X).
X = s(f(u(i,o),v,k,a),t(g))
yes
?-
87. Определить путь между двумя заданными узлами.
Аргументы: произвольное дерево;
имя первого узла:
имя второго узла;
путь (список).
?- pred(s(f(w(b(u(i,o,d),v),k),a),t(r(u),g),m),w,r,X).
X = [w,f,s,t,r]
yes
?- pred(s(f(w(b(u(i,o,d),v),k),a),t(r(u),g),m),i,d,X).
X = [i,u,d]
yes
?-
88. Переименовать все узлы, имеющие заданное имя.
Аргументы: произвольное дерево;
старое имя узла;
новое имя узла;
результирующее дерево.
?- pred(s(f(b(b(u(i,o),v),k),a),t(b(e),g),b),b,r,X).
X = s(f(r(r(u(i,o),v),k),a),t(r(e),g),r)
yes
?-
89. Найти все поддеревья.
Аргументы: произвольное дерево;
поддерево.
?- pred(a(f(a(m,k,v),r),n(i)),X).
X = a(f(a(m,k,v),r),n(i)) ->;
X = f(a(m,k,v),r) ->;
X = a(m,k,v) ->;
X = m ->;
X = k ->;
X = v ->;
X = r ->;
X = n(i) ->;
X = i ->;
no
?-
90. Найти в дереве все пути от корня до его листьев.
Аргументы: произвольное дерево;
путь (список).
?- pred(a(f(a(m,k),r),n(i,o,v(x))),X).
X = [a,f,a,m] ->;
X = [a,f,a,k] ->;
X = [a,f,r] ->;
X = [a,n,i] ->;
X = [a,n,o] ->;
X = [a,n,v,x] ->;
no
?-
91. Найти в дереве все пути от корня до его листьев, лежащих на максимальной глубине.
Аргументы: произвольное дерево;
путь (список).
?- pred(a(f(a(m,k,v),r),n(i,o)),X).
X = [a,f,a,m] ->;
X = [a,f,a,k] ->;
X = [a,f,a,v] ->;
no
?-
92. Найти в дереве все поддеревья, имеющие глубину не больше заданной.
Аргументы: произвольное дерево;
максимальная глубина;
поддерево.
?- pred(a(f(a(m,k),r,v(g)),n(i,o)),2,X).
X = a(m,k) ->;
X = m ->;
X = k ->;
X = r ->;
X = v(g) ->;
X = g ->;
X = n(i,o) ->;
X = i ->;
X = o ->;
no
?-
93. Выполнить перебор листьев в порядке убывания их глубины.
Аргументы: произвольное дерево;
лист дерева.
?- pred(a(f(a(m,k(v)),r),n(i(d,e,z),o)),X).
X = v ->;
X = m ->;
X = k ->;
X = d ->;
X = e ->;
X = z ->;
X = r ->;
X = o ->;
no
?-
94. Найти узел, имеющий максимальное количество потомков.
Аргументы: произвольное дерево;
узел дерева.
?- pred(a(f(a(m,k(v)),r),n(i(d,e,z(q,w,t)),o)),X).
X = i ->;
X = z ->;
no
?-
95. Составить описание каждого узла дерева (потомки нумеруются слева направо).
Аргументы: произвольное дерево;
описание узла (атом).
?- pred(a(f(a(m,k(v)),r),n(i(d,e,z)),o),X).
X = a ->;
X = 1:f ->;
X = 1:1:a ->;
X = 1:1:1:m ->;
X = 1:1:2:k ->;
X = 1:1:2:1:v ->;
X = 1:2:r ->;
X = 2:n ->;
X = 2:1:i ->;
X = 2:1:1:d ->;
X = 2:1:2:e ->;
X = 2:1:3:z ->;
X = 3:o ->;
no
?-
96. Дана строка, которая с помощью предиката string_term/2 (см. пример) корректно преобразуется в терм. Предполагается, что строка может преобразовываться в структуру любой арности, содержащую свободные переменные. Собрать из исходной строки в список имена свободных переменных.
Аргументы: исходная строка;
список имен переменных.
?- string_term(’r(T,m(T,K))’,B).
B = r(_70,m(_70,_84))
yes
?- pred(’r(T,m(T,K))’,X).
X = [’T’,’K’]
yes
?-
97. Сформировать графическое представление дерева в виде строки, используя символы псевдографики (см. приложение В).
Аргументы: произвольное дерево;
строка.
?- pred(a(f(a(m,k(v)),r),n(i(d,e,z)),o),X).
X =
a
├─f
│ ├─a
│ │ ├─m
│ │ └─k
│ │ └─v
│ └─r
├─n
│ └─i
│ ├─d
│ ├─e
│ └─z
└─o
yes
?-
|
|
|
