-1

示例: (reverse-list (list 1 2 3 4)) => 4321 注意:我不允许使用 string->num 或 num->string 或 reverse。

所以列表被消耗并创建了相反的数字(不再是列表)

我在递归逻辑上遇到了麻烦。

(define (reverse-list lofd)
 (cond [(empty? lofd) empty]
       [else (+ (* (exp 10 (something that starts at 0 and adds one extra everytime))
                   (first lofd))
                (convert-to-decimal (rest lofd)))]))

我的代码开始并将第一个数字转换为 num1*10^0 ,然后添加递归的数字。

我遇到的问题是我将如何做到这一点,以便在递归中指数为 10^0,然后上升到 1、2、3 ......直到列表的长度减去 1?我的逻辑/模板也对吗?谢谢!

4

3 回答 3

4

强烈建议:在精神上和字面上遵循列表结构的设计秘诀。这个问题对你来说很新奇,你不会轻易得到它。您需要设计配方步骤让您经历的额外支持。

在这种特定情况下,您确实需要一套很好的示例(测试用例)来帮助您,因为解决此问题的方法并不是立即显而易见的。比较棘手是因为这个函数不是从列表到列表:它是从列表到数字,所以你必须有一个强大的套件来帮助你发现愚蠢的错误。

例如,应该做什么?

(check-expect (reverse-list empty) <fill-me-in>)

是?我们甚至应该考虑空列表吗?这是一个奇怪的输入吗?有道理吗?合约是说我们必须处理空列表作为输入,还是可以保证它只接受非空列表?这是您需要预先解决的问题!您现在在代码中的内容不一定是正确的,因为您的合同类型......好吧,您还没有正式表达合同,但是一旦您这样做了,您就会发现基本情况必须不同比你到目前为止所写的。

在引用的关于设计秘诀的链接中,第 5 部分至关重要:一旦有了函数的模板,您就需要了解自然递归正在计算什么样的东西。使用具体的测试用例来提供帮助。从您的代码来看,您可能跳过了这一步,因为您编写的代码似乎没有考虑以下问题:“自然递归计算什么?”


具体来说,如果我们这样做:

(reverse-list (list 1 2 3 4))

我们想要的答案是什么?你自己说的:

(reverse-list (list 1 2 3 4))   ==>   4321

考虑一下自然递归将是什么:

(reverse-list (list 2 3 4))

这有什么价值?我们知道它必须是

(reverse-list (list 2 3 4))     ==>   432

一旦你弄清楚了,问问自己:自然递归的值与原始问题的答案有任何关系吗?

鉴于我们正在尝试解决:

(reverse-list (list 1 2 3 4))   ===>   4321

我们有碎片1(列表的第一部分)和432(来自自然递归),我们可以放在一起1432以某种方式得到4321吗?


重复这几个例子。少数,我的意思是不止一个。:) 对这些示例具体执行此操作,您的大脑将更好地进行模式匹配和概括,以找出递归案例的代码必须是什么。

也就是说,一旦您进行了足够的练习,弄清楚如何为具体案例获得正确答案,就去看看您是否可以将您正在使用的具体值表达回程序中的原始术语。例如,如果您发现:

we want to get 4321 out of 1 and 432:
    => 1 + 10 * 432

...  other examples you worked out...

让我们用前缀表示法重新表达这些:

we want to get 4321 out of 1 and 432:
    => (+ 1 (* 10 432))

...  other examples you worked out...

哪些部分发生了变化?哪些部分保持不变?第一个变化的部分代表什么?第二个变化部分代表什么?那是:

we want to get 4321 out of 1 and 432:
    => (+ 1 (* 10 432))

...  other examples you worked out ...

we want to get (reverse-list lst) out of (first lst) and (reverse-list (rest lst))
    ==> ???

一旦你看到了模式,那么你就已经弄清楚了递归案例的代码需要是什么。但请注意,您在这里确实需要一套示例:试图从一个特定示例中进行概括并不足以让您的大脑看到模式。您的大脑需要重复计算多个示例才能开始看到模式。

于 2013-03-19T03:47:15.117 回答
1

除了输入列表之外,您还需要传递另一个参数。如果需要,创建一个新的辅助过程(或内部过程,或命名let等)以使其工作。这两个参数将跟踪列表中的当前位置,以及 10 的当前指数。大致如下:

(define (reverse-list lofd n)
  (cond [(empty? lofd) ; what do we return if the list is empty?
         <???>]        ; not the empty list! we're building a number
        [else          ; otherwise add this term, taking the
         (<???> <???>  ; current element times current 10^n and
            (reverse-list <???> <???>))])) ; advance recursion over lofd and n

使用此初始值调用该过程:

(reverse-list (list 1 2 3 4) 0)
=> 4321
于 2013-03-19T03:41:02.167 回答
1

这是一个方案解决方案;它使用诸如 null?、car 和 cdr 之类的具有历史重要性但不在您的“学习球拍”词汇表中的东西。也许它会说明一种方法。

(define (list->reverse-number l)
  (if (null? l)
      0
      (+ (car l) (* 10 (list->reverse-number (cdr l)))))

如果您坚持尝试使用,expt那么您可能会尝试这样的事情(使用named-let,这可能超出您的水平):

(define (list->reverse-number l)
  (let reversing ((l l) (n 0))
    (if (null? l)
        0
        (+ (* (expt 10 n) (car l))
           (reversing (cdr l) (+ n 1))))))

但我不知道上述是否可行。实际上,这也有效。

于 2013-03-19T06:15:28.187 回答