Бинарные деревья
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
?-