谁能给初学者解释一个简单的方法，比如蛮力方法?

Question

我需要创建一个LISP函数，给定一个整数列表(x_1 x_2 ... x_n)，计算元素之间所有差异的乘积，

Π (x_i - x_j), where i < j

例如，对于列表:(4 3 2)，函数应计算:(4-2)(4-3)(3-2) = 2。如果列表为空，函数应该返回1。

这是我尝试过的:

对于空列表:

(defun dprod0 (lst) 
(if (null lst)
1))

For list with 1:

(defun dprod1 (lst)
(if (= (list-length lst) 1)
1))

这是我目前看到的

(defun dprod (lst)
(cond
((null lst) 1)
((= (list-length lst) 1) 1)
(t (let ((a (first lst)) 
(b (second lst)) 
(r (cdr lst)))
(* (- a b) (dprod r))))))

Answer 1

如果我们只需要知道它是空的((null lst))还是只包含一个元素((null (cdr lst)))，那么通常我们尽量不要不必要地测量整个列表的lst长度。因此你的代码变成了

(defun dprod (lst)
(cond
((null lst) 1)
((null (cdr lst)) 1)
(t (let ((a (first lst)) 
(b (second lst)) 
(r (cdr lst)))
(* (- a b) 
(dprod r))))))

这是一个完美的代码，但它计算什么呢?我们将潦草地写一些例子来看看是怎么回事。我们将使用{...}来指示转换:

{ [  ] }  ==>  1
{ [ 2 ] }  ==>  1
{ [ 3, 2 ] }  ==>  (* (- 3 2) { [2] } ) ==> (3-2)*1

到目前为止一切顺利。接下来,

{ [ 4, 3, 2 ] }  ==>  (* (- 4 3) { [3,2] } ) ==> (4-3)*(3-2)*1

，这是错误的。我们需要(4-2)*(4-3)*(3-2)*1。这与(4-3)*(4-2)*(3-2)*1相同。

这意味着在形成差异(4-3,3-2)时，我们只将第一个元素4与后面的元素3配对。但我们也需要把它和其他的配对起来。你的代码是这样做的:

{ [ 5, 4, 3, 2 ] }  ==>  (5-4)*(4-3)*(3-2)*1

但是它必须这样做:

{ [ 5, 4, 3, 2 ] }  ==>  (5-4)*(5-3)*(5-2)*
(4-3)*(4-2)*
(3-2)*
1

因此我们必须将其扩充为

(defun dprod (lst)
(cond
((null lst) 1)
((null (cdr lst)) 1)
(t (let ((a (first lst)) 
(b (second lst)) 
(r (cdr lst)))
(* (diffs a r)         ;; NB <<<----------
(dprod r))))))

以便计算

{ [ 5, 4, 3, 2 ] }  ==>  (5-4)*(5-3)*(5-2)*    ==  (diffs 5 [4,3,2])*
(4-3)*(4-2)*    ==  (diffs 4 [3,2])*
(3-2)*    ==  (diffs 3 [2])*
1   ==  (dprod [2])

现在您需要编写这个diffs函数。

之后，您还可以简化dprod的代码。