檢查第二個列表是否是第一個列表大小的一半

我是一個noob prolog程序員，面臨着一個難題，我在這本書中已經給出了一個基本問題。這個問題。這個問題基本上要求我們寫下一個以兩個列表作爲參數的Prolog過程，並且如果第一個列表的大小是第二個列表大小的兩倍，並且這兩個列表以相同的元素開始，則成功。如果兩個列表爲空，該過程應該返回false。檢查第二個列表是否是第一個列表大小的一半

a2b([a,a,a,a],[a,b]).

，並會失敗，並查詢：

例如，如果我們通過查詢應該返回true

a2b([a,a],[a,b,b,b]).

我不知道如何遞歸解決這個問題，任何幫助，將不勝感激。謝謝！

來源

2015-05-28 BleachedAxe

首先，對長度的要求：

/* empty list fulfills request */ 
a2b_length([],[]). 
/* non-empty: discard two elements of first list, 
       one of second list, and verify 
       remainder */ 
a2b_length([_,_|Q1],[_|Q2]) :- 
    a2b_length(Q1,Q2).

現在，我們可以添加規定「開始由同一個長期的和非空」，並寫了最後一句：

a2b([X,_|Q1],[X|Q2]) :- 
    a2b_length(Q1,Q2).

來源

2015-05-28 18:48:11

您的解決方案表明，給定兩個空列表，其中一個是另一個的兩倍。但是你在正確的軌道上。 –

我絕對相信，如果第一個列表的長度爲零，第二個的長度爲零，則第一個長度是第二個長度的一個。 –

您發佈的子句如何爲空列表返回false？我無法得到那部分。 – BleachedAxe

可愛的問題。它可以使用下面的代碼來解決：

% fail of the first element of each list don't unify 
% or if one or both lists are empty 
a2b([First| List1], [First| List2]) :- 
    % calculate the length of the second list 
    % while traversing both lists in parallel 
    a2b_first(List2, 1, N, List1, Rest1), 
    % check that the length of the rest of the first 
    % list is equal to the length of the second list 
    a2b_second(Rest1, N). 

a2b_first([], N, N, Tail1, Tail1). 
a2b_first([_| Tail2], N0, N, [_| Tail1], Rest1) :- 
    N1 is N0 + 1, 
    a2b_first(Tail2, N1, N, Tail1, Rest1). 

a2b_second([], 0). 
a2b_second([_| Tail1], N) :- 
    M is N - 1, 
    a2b_second(Tail1, M).

當然，還有一個更簡單的（但不是有趣的代碼！）解決方案：

% fail of the first element of each list don't unify 
% or if one or both lists are empty 
a2b([First| List1], [First| List2]) :- 
    length([First| List1], N1), 
    length([First| List2], N2), 
    N1 is 2 * N2.

的length/2謂語通常可無論是作爲一個建在謂詞中或作爲圖書館謂詞。

對於學習Prolog，研究第一個解決方案很有趣。例如，它舉例說明了如何利用第一參數索引以及如何使用累加器來編寫尾遞歸（從而節省空間）的謂詞。

此外，第一個解決方案可以比第二個解決方案更高效。在第二種解決方案中，我們總是遍歷兩個列表以找到它們的長度。但是，在第一種解決方案中，這並非總是必要的。

來源

2015-05-28 17:59:38

知道了！畢竟哈哈，現在看起來不那麼糟糕。非常感謝好友！ :) – BleachedAxe

歡迎你。但我會選擇其他答案（通過「passabe por aqui」;可愛的用戶名！:-)作爲接受的答案。雖然它使用三個子句，而基於「length/2」的答案使用一個子句，但它很高效，並且很好地說明了使用容易獲得的內置/庫謂詞並不總是產生最優雅的解決方案。 –

這兩個版本都不會終止'a2b（Xs，[a]）。 – false

不要推翻事物：只描述解決方案，讓Prolog整理出來。

該解決方案不需要計數或謂詞以外的其微不足道的自我。這都是模式匹配。我們有一個特殊的（終止的情況下），聲稱長度爲2的列表是兩次只要長度爲1（這應該是很明顯的）的列表：

is_twice_as_long_as([_,_] , [_]) .

再有就是一般情況下，斷言給定兩個任意長度的列表，左邊是右邊的IF的兩倍長度（A）從左邊移除2個項目，（B）從右邊移除1個項目，遞歸地斷言它們各自的餘數同樣是兩倍長：

is_twice_as_long_as([_,_|A] , [_|B]) :- is_twice_as_long_as(A , B) .

給人的成品：

is_twice_as_long_as([_,_] , [_] ) . 
is_twice_as_long_as([_,_|A] , [_|B]) :- is_twice_as_long_as(A , B) .

簡單！

編輯注意兩個列表以相同的元素開始要求：

取決於如何被解釋......

這需要列出有一個共同的頭在每次迭代中：

is_twice_as_long_as([A,_] , [A] ) . 
is_twice_as_long_as([A,_|L] , [A|R]) :- is_twice_as_long_as(L , R) .

這樣做只檢查一次共同頭部：

is_twice_as_long_as([A|As] , [A|Bs]) :- 
    is_2x([A|As],[A|Bs]) . 

is_2x([_,_] , [_]) . 
is_2x([_,_|L] , [_|R]) :- is_2x(L , R) .

來源

2015-05-28 19:35:33

這個問題指出「a2b（[a，a，a，a]，[a，b]）」。是真實的，因此你可以放棄第一個選項在「取決於如何解釋......」 –

檢查第二個列表是否是第一個列表大小的一半

回答

相關問題