Prolog查找列表中的中間元素

我正在嘗試使用prolog謂詞並找到給定列表的中間元素。我的想法是使用遞歸來減少列表的第一個和最後一個元素。不幸的是我不知道如何正確處理遞歸調用。Prolog查找列表中的中間元素

delete_last(L, L1) :- 
append(L1, [_], L). 
delete_first(L,L1) :- 
    append([_],L1,L). 
check_len(L) :- 
    length(L,LEN), \+ 1 is LEN. 


delete_both([],_):- 
    false. 
delete_both([_,_],_) :- 
    false. 
delete_both([X],X):- 
    true, write('MidElement'). 

delete_both(L,L2) :- 
    delete_first(LT,L2), delete_last(L,LT),check_len(LT) 
    ->write('here should be recursive call only when length is more than one').

我將不勝感激任何幫助。

來源

2016-03-08 Dago

你是否支持所有大小的列表（偶數和奇數）？如果是這樣，請看相關的問題「如何獲得列表方案和序言的第一個，中間和最後一個元素？」（http://stackoverflow.com/questions/30112114/how-to-get-the-first-middle-and-last-element-of-a-list-scheme-and-prolog/30117040#30117040）和這個答案特別是http://stackoverflow.com/a/30117040/4609915。 HTH！ – repeat

可以收緊你有相當多的如下：

delete_last(L, L1) :- 
    append(L1, [_], L). 
delete_first([_|L], L). 

% No need to check length of 1, since we only need to check 
% if L = [X] in the caller, so we'll eliminate this predicate 
%check_len(L) :- 
% length(L, 1).   % No need for an extra variable to check length is 1 

% Clauses that yield false are not needed since clauses already fail if not true 
% So you can just remove those 
% 
delete_both([X], X) :- 
    write('MidElement'). 

% Here you need to fix the logic in your main clause 
% You are deleting the first element of the list, then the last element 
% from that result and checking if the length is 1. 

delete_both(L, X) :- 
    delete_first(L, L1), % Remove first and last elements from L 
    delete_last(L1, LT), 
    ( LT = [X]   % Check for length of 1 
    -> true 
    ; delete_both(LT, X) % otherwise, X is result of delete_both(LT, X) 
    ).

有了結果：

| ?- delete_both([a,b,c,d,e], X). 

X = c 

yes 
| ?- delete_both([a,b,c,d,e,f], X). 

no

一個DCG解決方案也是行之有效的位置：

% X is the middle if it is flanked by two sequences of the same length 
% 
middle(X) --> seq(N), [X], seq(N). 

seq(0) --> []. 
seq(N) --> [_], { N #= N1 + 1 }, seq(N1). 

middle(List, X) :- phrase(middle(X), List).

有結果：

| ?- middle([a,b,c,d,e], X). 

X = c ? ; 

(1 ms) no 
| ?- middle(L, a). 

L = [a] ? ; 

L = [_,a,_] ? ; 

L = [_,_,a,_,_] ? 
...

另一種可能的解決方案是使用SWI序言的 append/2謂詞，其中追加名單列表（假設你使用SWI）：

middle(L, X) :- 
    same_length(Left, Right), 
    append([Left, [X], Right], L). 

same_length([], []). 
same_length([_|T1], [_|T2]) :- same_length(T1, T2).

在上述所有的解決方案，如果列表具有偶數個元素，謂詞將失敗。既然這就是你原來的解決方案，我認爲這是必需的。如果偶數名單有特殊要求，則需要明確說明。

來源

2016-03-08 02:06:09 lurker

這將節省大量的輸入，如果你檢查列表的長度，計算出中間元素的位置，才把走過列表以獲得在該位置的元素。對於SWI-Prolog，這將是：

?- length(List, Len), 
    divmod(Len, 2, N, 1), 
    nth0(N, List, a). 
List = [a],         Len = 1, N = 0 ; 
List = [_G2371, a, _G2377],     Len = 3, N = 1 ; 
List = [_G2371, _G2374, a, _G2380, _G2383], Len = 5, N = 2 . % and so on

此解決方案確保列表具有奇數長度。如果你需要自己定義它，你可以看到documentation of divmod/4。或者，如果列表不必具有奇數，長度，只需使用N is Len div 2即可。如果由於某種原因，您不允許使用nth0/3，那麼實施起來仍然比您想要做的更容易。

來源

2016-03-08 08:03:53

Prolog查找列表中的中間元素

回答

相關問題