0

被称为戴克路径。它是 x 和 y 轴的平面，其中每一步将只有 (x+1,y+1) 或 (x+1,y-1) 并且将始终保持在 x 轴上方

K 应该表示 Dyck 路径的峰值。当 K 为 2 时，应该意味着峰值为 2 和 3。

形成匹配括号 a = '(', and b = ')' 的合法序列列表，长度为 2N

例如。[a,a,b,b] 和 [a,b,a,b] 是 N = 2 的合法列表 [a,b,b,a] 和 [b,a,b,a] 不满足N = 2

需要定义谓词 listFind(L,K,N) 当 L 具有 2N 阶的列表时满足，对于某些 k >= K

例如

|?- listFind(L,1,3).
L = [a,b,a,b,a,b] ? ;
L = [a,b,a,a,b,b] ? ;
L = [a,a,b,b,a,b] ? ;
L = [a,a,b,a,b,b] ? ;
L = [a,a,a,b,b,b] ? ;
no


|?- listFind(L,2,3).
L = [a,a,b,b,a,b] ? ;
L = [a,a,b,a,b,b] ? ;
L = [a,a,a,b,b,b] ? ;
no

提前致谢。

4

1 回答 1

1

K我不清楚这个角色的作用。无论如何，这是一个满足您的测试用例的片段：

listFind(L, K, N) :-
    N2 is N*2,
    length(L, N2),
    phrase(dyck, L),
    % satisfy condition on K
    run_length_encoded(L, RLE),
    [X-a|_] = RLE, X >= K.

% DCG for Dyck' language over alphabet `a,b`    
dyck --> [] ; [a], dyck, [b], dyck.

run_length_encoded([X|S], C) :-
    run_length_encoded(S, X, 1, C).

run_length_encoded([Y|S], X, N, E) :-
    (   X == Y
    ->  M is N + 1,
        run_length_encoded(S, X, M, E)
    ;   E = [N-X|T],
        run_length_encoded(S, Y, 1, T)
    ).
run_length_encoded([], X, C, [C-X]).

如您所见，K的解释是

  • 序列必须以至少K连续的开头a
于 2013-09-02T06:31:06.460 回答