lisp - 在子列表中查找总和

Question

Given a list L=(M,A1,A2,...,An). Find sublist if they exist L1=(Ai,Ai+1,...,Ai+k), i+k<=N, i>=1, for which M=Ai+Ai+1+...Ai+k

For example: L=(1 3 -16 5 7 8 2 2), M=12 Result: L1=(1 3 -16)
L1=(5 7)
L1=(8 2 2)
for 5+7=12, 1+3-16=12, 8+2+2=12

如何在 lisp 中解决这个问题？

Answer 1

先试试

让我们先尝试找到一个子列表。

Sum  = 10
List = (2 4 3 3 1)

如果你尝试递归怎么办？列表是 (2 . (4 3 3 1))，减去 2。

Sum  = 8
List = (4 3 3 1)

再次:

Sum  = 4
List = (3 3 1)

再次:

Sum  = 1
List = (3 1)

最后:

Sum  = -2
List = (1)

我们失败了，因为总和是负数。

丢弃第一个元素

我们再试一次，但这次我们跳过了第一个元素:

Sum  = 10
List = (4 3 3 1)

...等等

Sum  = 0
List = (1)

现在我们成功了，因为总和为零，而且我们没有到达空列表。

提示和问题

• 我们需要通过跳过一些 N 个第一个元素来尝试所有可能的起始位置；
• 我们可以递归解决子问题，同时减少总和；
• 有不同的基本情况，有总和也有列表；
• 当总和为零时，表示我们遍历了我们要查找的子列表；
• 我们需要以某种方式收集该子列表，我们可以在哪里构建它？
• 我们如何收集所有可能的子列表？

我的看法，混淆了

(d.... s...... (s.. l...)
  (l.....
      ((s...... (s.. l... r.....)
         (c...
           ((m..... s..) n..)
           ((z.... s..) (l... (n....... r.....)))
           ((c.... l...) (d............-.... (h... . t...) l...
                           (s...... (- s.. h...) t... (l...* h... r.....))))
           (t n..))))
    (m..... (l..... (l...) (s...... s.. l... n..)) l...)))