如何使用Prolog在数字列表中找到N的最小倍数？

Question

我需要在数字列表中找到N的最小倍数.

leastMultiple/2
leastMultipleOfThree/2, 
arg1= list of numbers,arg2= X (X is what we want to find, the least multiple of 3 in a list of numbers). 

例如,在[7,9,15,22]中找到3的最小倍数.我已经盯着这个很长一段时间了,我不确定从哪里开始.如果你能简单地帮我解决一下这个问题,我会非常感激.

Answer 1

我的答案的早期版本被使用"最小倍数"这个词弄糊涂了.您想在列表中找到倍数,并检索最小值.我现在知道了.

首先,我们必须检测N的倍数.我们可以通过使用模运算符分割和查看余数来完成此操作,如下所示:

?- X is 7 mod 3.
X = 1.

?- X is 9 mod 3.
X = 0.

我将为此定义一个方便的方法,is_multiple_of:

% multiple_of(X, N) is true if X is a multiple of N
multiple_of(X, N) :- 0 is X mod N.

现在我们可以简单地说:

?- multiple_of(7, 3).
false.

?- multiple_of(9, 3).
true.

现在有两种方法可以继续.有效的方法,可以很容易地使尾递归以获得更好的性能,是使用累加器将列表移动一次以保持当前的最小值.代码密集度较低的方法是将列表过滤到所有倍数并对其进行排序.让我们看看这两种方法:

% less code: using setof/3
leastMultipleOfThree(List, Result) :-
    setof(X, (member(X, List), multiple_of(X, 3)), [Result|_]). 

setof/3尽可能多次评估其第二个术语,每次在第一个术语中检索变量以包含在结果中,第三个术语.为了使列表唯一,setof/3对结果进行排序,因此最小值将在第一个位置结束.我们使用的member(X, List), multiple_of(X, 3)是一个非常简单的生成测试模式.所以它很简洁,但它看起来不太好,并且与构建列表和排序相关的成本意味着它不是最佳的.但这很简洁!

% more code: using an accumulator
leastMultipleOfThree(List, Result) :- leastMultipleOfThree(List, null, Result).

% helper
leastMultipleOfThree([], Result, Result) :- Result \= null.
leastMultipleOfThree([X|Xs], C, Result) :-
    multiple_of(X, 3) 
        -> (C = null -> leastMultipleOfThree(Xs, X, Result)
                      ; (Min is min(X, C), 
                         leastMultipleOfThree(Xs, Min, Result)))
         ; leastMultipleOfThree(Xs, C, Result).

这是相当多的代码,因为有几种情况需要考虑.第一条规则是清单熄灭的基本情况; 我null任意选择代表我们还没有看到三个的倍数的情况.右侧的测试确保如果列表为空并且我们从未找到三个的倍数,则我们会失败.

第二条规则实际上处理了三种情况.通常我会将它们分解为单独的谓词,但会有很多重复.它看起来像这样:

leastMultipleOfThree([X|Xs], null, Result) :-
  multiple_of(X, 3), 
  leastMultipleOfThree(Xs, X, Result).
leastMultipleOfThree([X|Xs], C, Result) :-
  multiple_of(X, 3),
  C \= null,
  Min is min(X, C),
  leastMultipleOfThree(Xs, Min, Result).
leastMultipleOfThree([X|Xs], C, Result) :-
  \+ multiple_of(X, 3),
  leastMultipleOfThree(Xs, C, Result).

这可能会或可能不会更具可读性(我更喜欢)但它肯定会表现更差,因为这些规则中的每一个都会创建一个选择点,即规则中的if/else条件表达式不会.使用削减来改善这一点是很诱人的,但如果你尝试的话,你肯定会陷入一个地狱般的迷宫中.

我希望在这一点上它是相当不言自明的.:)