0

我对整体计划还是很陌生，在确定学校作业时遇到了一些问题。所以请不要完整的答案，只是寻找一点见解或朝着正确的方向轻推，这样我就可以自己解决这个问题。

问题如下：给定一个数字列表，确定两个子集是否可以从这些相等的总和和项目数组成。例如，如果给定的集合是 (1 1)，那么我的程序应该返回 #t，否则返回 #f。

这是我到目前为止所写的（即使它目前没有输出）

(define l (list '(7 5)))

(define s1 0)
(define s2 0)
(define l1 0)
(define l2 0)

(define two-subsets
  (lambda (l s1 s2 l1 l2)
    (if (null? l)
          (if (and (= s1 s2) (= l1 l2))
              (#t))
          (if (not (and (= s1 s2) (= l1 l2)))
              (#f)))
    (or ((two-subsets(cdr l) (+ s1 1) s2 (+ l1 1) l2) (two-subsets(cdr l) s1 (+s2 1) l1 (+ l2 1))))))

我的函数应该递归地将项目添加到子集 1 (s1, l1) 或子集 2 (s2, l2)，直到它达到确定子集大小和总和是否相等的基本情况。我觉得我的逻辑在那里/关闭，但我不确定如何在方案中正确实施这些想法。

编辑我应该补充一点，作为作业的一部分，我必须使用递归。我希望 DrRacket 提供更多调试信息，因为当我点击运行时它没有给出错误，但也没有输出。

4

2 回答 2

2

问题

您的代码中存在一些问题。

第一的

这将创建一个列表列表：

(list '(7 5))  ; => ((7 5))

其中一个cdr始终是一个空列表。

(cdr (list '(7 5)))  ; => ()

以这种方式创建一个列表：

(define l (list 7 5))

或者这样：

(define l '(7 5))

第二

您在 Scheme 中使用括号进行应用。这个：

(#t)

意思是“执行功能#t”。但#t不是一个函数，它是一个布尔值。并且不能执行布尔值。

您可以直接返回一个布尔值

#t

或者您可以返回一个返回值的函数

(lambda () #t)

但你不能执行真实。

第三

中的同样问题or。以下代码：

(or ((two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
     (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1))))

意思是：two-subsets必须返回一个函数。第一次two-subsets调用返回的函数与第二次调用返回的函数一起执行two-subsets。并且单个结果值被传递给or. 这可能不是你想要的。

如果要or两次调用的两个返回值，则two-subsets必须删除两个括号。

(or (two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
    (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1)))

提示

  • 定义一个与您的结束条件匹配的函数。该函数接受两个列表参数并检查它们是否具有相同的大小 ( length) 和总和（您可以使用apply将列表传递给+）。剧透
  • 编写一个遍历所有可能子集的函数。并使用每个组合调用您的匹配函数。迭代是通过 Scheme 中的递归来完成的。要么定义一个调用自身的函数，要么使用一个命名的let.
于 2017-04-27T13:12:27.350 回答
1

对于第一遍，您可能希望避免尝试将“子集”逻辑耦合到“将两个子集添加到相同的值”逻辑。小程序比长程序更容易编写。

但这可能是一个复杂的问题。

一种接近它的方法被称为“一厢情愿”。我们将从头开始工作：解决这个问题的最后一步是什么？比较两个相同长度的子集总和是否相同。所以，让我们解决这个问题。然后我们对所有相同长度的子集执行此操作。但是现在我们需要知道：所有相同长度的子集组是什么？如果我们解决了这个问题，那么一切都结束了。所以让我们解决这个问题。然后我们将其应用于所有子集的集合。但是现在我们需要知道：我们如何得到所有子集的集合？如果我们解决了这个问题，那么一切都结束了。我们将把它应用到我们的集合中。但是现在我们需要知道：我们的集合是什么？-哦！这就是问题本身。所以我们完成了！

实际上在细节上有点棘手，但是通过上面的阐述我想你可以看到这个链的逻辑：

(find-first-equal-sum ; we can stop as soon as #t, if there is #t
  (make-pairs ; problem only wants us to consider pairs
    (sum-subsets ;we need sums eventually
       (at-least-two-in-a-group ; can't make pairs without at least two in a group
        (group-by-length ; only care about matching subsets of the same length
         (at-least-length-2 ; singles can't match because each element of a set is unique
          (subsets problem-set)))))))

注意：我确实编写了这个程序并在发布之前对其进行了测试。上面的“大纲”是直接从 DrRacket 复制过来的。

于 2017-04-27T00:31:06.177 回答