查找缺少的整數 - Prolog

我想獲取一個整數列表並創建一個整數列表，它們位於前列表中的整數之間（或間隔內）。例如，我想?- findmissing([1,3,4,5,6],X).導致X = [2]。我將如何實現這樣的功能？查找缺少的整數 - Prolog

2011-10-07 Hunterhod

邏輯編程的第一個竅門是從最小的情況開始並進行處理。

這裏的基本情況很容易，如果列表中少於兩個元素，沒有什麼缺失。

findmissing([], []). 
findmissing([_], []).

第二招是分而治之。爲了找到列表中每對之間缺失的所有東西，我們需要一個謂詞（比如（X，Y，List）/ 3）中的數字，它給出給定數字對之間的所有數字，然後在每個數字對在輸入列表中配對。使用內置的append（）/ 3，而不是令人擔憂的有關如何實現numbersbetween（）/ 3的那一刻，我們就可以把：

findmissing([X, Y|In], Out) :- 
    numbersbetween(X, Y, Between), 
    findmissing([Y|In], After), 
    append(Between, After, Out).

（有一點這裏的照顧，以確保我們考慮每一對，在列表[1,2,3]中，我們需要檢查[1,2]和[2,3] - 這就是爲什麼recusive步驟不僅僅需要In [Y | In]）。

那麼只剩下在（）/ 3之間定義數字的挑戰。如果您碰巧知道（）/ 3（如果X < Z < Y爲true）和setof（）/ 3（它可以從所有解決方案生成列表）之間的內置謂詞，則可以使用：

numbersbetween(X, Y, List) :- setof(B, between(X, Y, B), List).

如果您不知道這些函數，您可以使用Prolog的算術「is」在（）之間構造自己的數字。

來源

2011-10-07 02:42:40

康拉德歐文在這裏給出了遞歸解決問題的一個很好的分析，但假設輸入列表按升序排序（Hunterhod示例中就是這種情況）。

關於未分類輸入的可能性的思考提出了一種方法，除了在應用康拉德技術之前對輸入進行分類之外。

找到InputList的Minimum和Maximum元素。
創建連續整數列表BetweenList = [Minimum,...,Maximum]。從BetweenList
提取的所有條目不是InputList成員形成MissingList。

來源

2011-10-09 13:11:09 hardmath

查找缺少的整數 - Prolog

回答

相關問題