0

我正在参加与麻省理工学院计划有关的编程课程的练习考试。其中一个问题是：

“完成过程（按顺序 ls）以返回列表 ls，除了在第一个不严格大于ls 中的前一个值的值之前停止。换句话说，按顺序应该返回 ls 的部分从严格按递增顺序排序的开头。假设ls 仅包含非负整数。

然后问题显示了几个示例：

(in-order '(1 2 3 4)) ; should return (1 2 3 4)
(in-order '(1 2 3 3 4 5)) ; should return (1 2 3)
(in-order '(3 2)) ; should return (3)
(in-order '(3)) ; should return (3)

这是我尝试的解决方案：

(define (in-order ls)
  (cond ((null? ls) ls)
        ((< (car ls) (cadr ls)) 
         (cons (car ls) (cons (in-order (cdr ls)) ())))
        ((>= (car ls) (cadr ls)) (car ls))
        (else "Nothing")))

它接近于使用第二个和第三个示例，但在第一个和第四个示例中完全失败了。我知道它一直试图传递一个 null 作为参数的一部分，但我不确定如何解决这个问题。除此之外，还有什么我错了吗？

4

1 回答 1

2

这会让你到达那里：

(define (in-order ls)
  (if (null? ls)
      '()
      (let looking ((result (list (car ls))) (ls (cdr ls)))
        (if (or (null? ls) (not (< (car result) (car ls))))
            (reverse result)
            (looking (cons (car ls) result)
                     (cdr ls))))))

尾递归looking总是将最后一个值作为结果car。所以停止的比较变成(not (< (car result) (car ls)))

在您的代码中，(cons (in-order ...) ())几乎肯定是错误的。谓词(< (car ls) (cadr ls))将在任何类似的情况下失败'(3)- 你需要类似的东西(null? (cdr ls))来避免这种情况。

在类似于您的非尾递归算法中，它将是：

(define (in-order ls)
  (cond ((or (null? ls) (null? (cdr ls))) ls)     ; nothing left
        ((< (car ls) (cadr ls))                   ; extend and continue
         (cons (car ls) (in-order (cdr ls))))
        (else (list (car ls)))))                  ; last one
于 2013-04-14T17:23:57.610 回答