1

我有一个作业，我需要计算输入中的对数。

这是我到目前为止所拥有的：

(define x 0)

(define number-of-pairs
  (lambda (v)
    (if (pair? v)
        (+ x 1)
        (+ x 0))))

然后我按如下方式使用它：

(number-of-pairs (cons (cons 'a 'b) 'c))

在这里它应该产生 2，但它却产生 1，因为它只通过函数一次。如果我尝试

(number-of-pairs 10)

它产生 0，因为没有对。

4

3 回答 3

5

您必须考虑两种情况：

  1. 如果当前元素不是一对会发生什么？
  2. 如果当前元素是一对会发生什么？

对于第二种情况，我们可以在总数中加一个，因为我们知道当前元素是一对，然后我们在这对的两个部分上调用递归——因为我们不知道其中任何一个是否在转一对。

以下是需要做什么的总体思路，请填空：

(define (number-of-pairs v)
  (if (not (pair? v))
      <???>
      (+ <???>
         (number-of-pairs <???>)
         (number-of-pairs <???>))))

使用这些示例来测试您的程序：

(number-of-pairs 10)
> 0

(number-of-pairs (cons (cons 'a 'b) 'c))
> 2

(number-of-pairs '(a b c))
> 3

(number-of-pairs (cons 'a (cons 'b (cons (cons 'c (cons (cons 'd '()) '())) '()))))
> 6
于 2012-04-30T19:21:43.733 回答
2

使用武力，卢克！

呃。我的意思是使用设计配方。

请参阅如何设计程序中的 9.3 和 9.4 节：

http://htdp.org/2003-09-26/Book/curriculum-ZH-13.html#node_sec_9.3

如果您不熟悉 HtDP，那么其理念是为您提供系统编写程序的工具，而不仅仅是提供示例。

于 2012-04-30T18:31:59.237 回答
0

正如现在所写的那样，您的代码只会返回 1 或 0。为了使此过程按预期工作，您需要了解有关方案的两个重要事项：递归调用如何工作，以及赋值如何工作。

任务：

我在方案中写了一个非常深入的赋值分解，但在这种情况下，简短的版本是你没有改变x你调用时的值(+ x 1)。如果您想实际更改方案中绑定的值，则必须使用该set!过程（但在这种情况下您确实不需要这样做）。

递归：

回想一下，递归是当您从自身内部调用过程时。递归解决方案有两个必要元素：空值和归约公式。

在加法或减法的情况下，你的 null 值是 0，对于乘法它是 1，因为cons它是空列表'()。

减少公式是您如何将问题分解为更简单的部分，或者如何让问题更接近于每一步的解决。

例子：

(define count-elements
    (lambda (lst)
        (if (null? lst) 0 ; <-- I'm done? return the null value
            (+ 1 (count-elements (cdr lst)))))) ;<-- otherwise +1 and reduce the problem

由于这是家庭作业，我不会为您明确解决这个问题，但您的答案应该与计数元素的形式基本相同，您只需要另一个谓词来确定您是否真的需要添加任何东西。

于 2012-04-30T18:42:56.963 回答