文章/答案/技术大牛

发布

社区首页 >问答首页 >有没有人能为初学者解释一种简单的方法，比如暴力方法？

问有没有人能为初学者解释一种简单的方法，比如暴力方法？
EN

Stack Overflow用户

提问于 2021-10-01 09:41:48

回答 1查看 96关注 0票数 0

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

Π (x_i - x_j), where i < j

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

这是我尝试过的：

对于空列表：

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

对于包含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))))))

common-lisp

回答 1

Stack Overflow用户

发布于 2021-10-02 08:18:09

通常，如果我们只需要知道列表是空的((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的代码。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/69403766

复制

相似问题

问有没有人能为初学者解释一种简单的方法，比如暴力方法？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问有没有人能为初学者解释一种简单的方法，比如暴力方法？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问有没有人能为初学者解释一种简单的方法，比如暴力方法？
EN