Scheme groupSum 函数

Question

我正在尝试编写一个 Scheme 函数，它接受两个参数，一个数字列表和另一个数字，并且 returns 如果列表的一个子集加起来等于该数字，则为真。

示例输出：

> (groupSum '(1 2 5) 7)
> #t
> (groupSum '(1 2 5) 4)
> f

到目前为止，我所能做的就是获取列表中所有数字的总和。我需要如何处理我的代码才能获得示例输出？

到目前为止，这是我的代码：

(define (groupSum elemList)
  (if
    (null? elemList)
    0
    (+ (car elemList) (groupSum (cdr elemList)))
  ))

我的代码是什么returns：

> (groupSum '(1 2 5))
> 8

Answer 1

所以你要问的是，给定列表的子集是否存在（在位置意义上，即保留重复项，如果有的话）加起来等于给定的数字。

遍历子集是 powerset 函数的工作，除了我们想要跳出它并且 return #t 一旦我们检测到成功。否则最后就是return#f

在此站点上从 one of my other answers 增加幂集函数，我们得到

(define (group-adds-to aL aN)
  (call/cc
   (lambda (......)  ;; 2.
     (letrec 
        ([...... (lambda (aL)  ;; 4.
           (cond
             [(empty? aL) (list empty)]
             [else
              (add-into   ;; 5b.
                        (powerset (rest aL))  ;; 3b.
                        (first aL))]))]

         [...... (lambda (r a)  ;; 6.       ; `r` is recursive result, `a` an element
           (cond
             [(empty? r) empty]             ; nothing to add `a` to
             [else
              (cons (add a (first r)) ;; 7. ; either add `a`,
                    (cons (first r)         ;   or not, to the first in `r`
                          (add-into  ;; 5a. ; and recursively proceed
                           (rest r)         ;   to add `a` into the rest of `r`
                           a )))]))]

         [......                      ;; 8.
                  (lambda (......)       ;; 9...
                     (let ([sum ......])   ;; 10...
                       (if (= sum aN)  ;; 11.
                           (return #t)  ;; 1.
                           sum)))])

       (powerset aL)  ;; 3a.
       #f))))   ;; 12.

填空！

测试：

> (group-adds-to '(1 2 5) 7)
#t
> (group-adds-to '(1 2 5) 4)
#f

如果您需要，只需进行一些细微的更改即可使 #r5rs 兼容。

当然可以通过使用更多的内置函数来精简和缩短这段代码。在这里去掉 call/cc 也很简单。您还可以花哨并添加检查以缩短临时列表，检测并删除可能无法促成成功结果的子组（子集）。

好的，如何填空。

return？那是什么？
这是call/cc给我们设置的逃生延续。当调用 (if) 时，如 ;; 1.，值 #t 立即被 returned 作为整个 group-adds-to 函数调用，无论此时我们在递归中有多深。递归刚刚被放弃，结果只是returned.
如果从未调用 return，因为从未检测到等式 (= sum aN) ;; 11.，则递归将结束其过程并且 #f 将正常 returned，作为中的最后一个表达式函数体，位于 ;; 12..
_a,b. powerset? 那个是什么？
这是我们定义的内部函数
_a,b. add-into?
它也是，在这里定义。
和add?
是的。
自己动手。看看它是如何使用的，在;; 7，它的参数是什么，它必须是什么return。
自己动手。你可以的！

Scheme groupSum 函数

Scheme groupSum Function

scheme

racket

r5rs