Подсчет вхождений в прологе двоичного дерева - PullRequest
Новая
       45

Подсчет вхождений в прологе двоичного дерева

0 голосов
/ 04 августа 2020

Я хочу реализовать код, который будет определять количество вхождений числа во всем дереве, например: 

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), N).
N = 1;

как мне go это сделать?

Ответы [ 2 ]

1 голос
/ 04 августа 2020

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

treeToList(Tree, List) :-
    % I use an accumulator, starting with an empty list.
    treeToList(Tree, [], List).

% The bottom is reached: The accumulated elements are the result.
treeToList(nil, Accu, Accu).

treeToList(bt(E, Left, Right), Accu0, List) :-
    Accu1 = [E|Accu0],              % prepend the accumulator with the current element
    treeToList(Left, Accu1, Accu2), % prepend elements of the left node
    treeToList(Right, Accu2, List). % prepend elements of the right node

?- treeToList(bt(6, bt(2, bt(1, nil, nil),
                          bt(3, nil, nil)),
                    bt(8, bt(7, nil, nil),
                          bt(9, nil, nil))), L).
L = [9, 7, 8, 3, 1, 2, 6].

Подсчет в отсортированном списке намного проще, чем подсчет несортированного списка. Prolog имеет для этого встроенный предикат sort / 2 . 

?- sort([9, 7, 8, 3, 1, 2, 6], L).
L = [1, 2, 3, 6, 7, 8, 9].

Вы можете подсчитать количество соседних значений и получить оставшиеся разные значения за один шаг: 

removeFromFrontAndCount(_, [], [], N, N).

removeFromFrontAndCount(E, [F|Out], [F|Out], N, N) :-
    E \= F.

removeFromFrontAndCount(E, [E|In], Out, N0, N2) :-
    N1 is N0 + 1,
    removeFromFrontAndCount(E, In, Out, N1, N2).

?- removeFromFrontAndCount(1, [1,1,1,2,3,4], L, 0, N).
L = [2, 3, 4],
N = 3 ;
false.

Использование этого помощника - это предикат countAdjacent / 3: 

countAdjacent(List0, E, N) :-
    [E0|List1] = List0,
    removeFromFrontAndCount(E0, List1, List2, 1, CountE),
    (   % a semicolon is an either-or operator
        E = E0, N = CountE;
        countAdjacent(List2, E, N)
    ).

?- countAdjacent([1,1,1,2,2,3], E, N).
E = 1, N = 3 ;
E = 2, N = 2 ;
E = 3, N = 1 ;
false.

И для объединения всего: 

numberOfOccurrences(E, Tree, N) :-
    treeToList(Tree, List),
    sort(List, SortedList),
    countAdjacent(SortedList, E, N).

?- numberOfOccurrences(E, bt(6, bt(2, bt(1, nil, nil),
                                bt(3, nil, nil)),
                          bt(8, bt(7, nil, nil),
                                bt(9, nil, nil))), L).
E = 1, L = 1 ;
E = 2, L = 1 ;
E = 3, L = 1 ;
E = 6, L = 1 ;
E = 7, L = 1 ;
E = 8, L = 1 ;
E = 9, L = 1 ;
false.

Весь код : 

numberOfOccurrences(E, Tree, N) :-
    treeToList(Tree, List),
    sort(List, SortedList),
    countAdjacent(SortedList, E, N).


treeToList(Tree, List) :-
    treeToList(Tree, [], List).

treeToList(nil, Accu, Accu).

treeToList(bt(E, Left, Right), Accu0, List) :-
    treeToList(Left, [E|Accu0], Accu1),
    treeToList(Right, Accu1, List).


countAdjacent(List0, E, N) :-
    [E0|List1] = List0,
    removeFromFrontAndCount(E0, List1, List2, 1, CountE),
    (
        E = E0, N = CountE;
        countAdjacent(List2, E, N)
    ).


removeFromFrontAndCount(_, [], [], N, N).

removeFromFrontAndCount(E, [F|Out], [F|Out], N, N) :-
    E \= F.

removeFromFrontAndCount(E, [E|In], Out, N0, N2) :-
    N1 is N0 + 1,
    removeFromFrontAndCount(E, In, Out, N1, N2).
1 голос
/ 04 августа 2020

Вы пробовали определить 

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), 1).

? Вы пробовали определить 

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), N) :- 
                   N = 1.

? Вы пробовали определить 

numberOfOccurrences(7, T, N) :-
                   T = bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))),
                   N = 1.

? А может даже 

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   TL =      bt(2, bt(1, nil, nil),    %%
                                   bt(3, nil, nil)),
                   TR =      bt(8, bt(7, nil, nil),    %%
                                   bt(9, nil, nil)),
                   N = 1.

? Вы также пробовали определить 

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,                             %%
                   TL =      bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                   NL = 0,                             %%
                   TR =      bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil)),
                   NR = 1,                             %%
                   N is N1 + NL + NR.                  %%

? Разве не должно быть также и 

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,
                   TL =      bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                   numberOfOccurrences(7, TL, NL),     %%
                   NL = 0,
                   TR =      bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil)),
                   numberOfOccurrences(7, TR, NR),     %%
                   NR = 1,
                   N is N1 + NL + NR.

? А также просто 

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,
                                                       %%
                   numberOfOccurrences(7, TL, NL),
                                                       %%
                   numberOfOccurrences(7, TR, NR),
                                                       %%
                   N is N1 + NL + NR.

? Вы пробовали обобщать его дальше, удаляя последние искусственно конкретные значения, заменяя их также переменными logi c, 

numberOfOccurrences( X, T, N) :-                       %%
                   T = bt( Y, TL, TR),                 %%
                   count_one_possible_occurrence( X, Y, N1),
                   numberOfOccurrences( X, TL, NL),    %%
                   numberOfOccurrences( X, TR, NR),    %%
                   N is N1 + NL + NR.

? Не могли бы вы продолжить эту мысль?

...