时间戳

首页 > 解决方案 > DrRacket - 找到最长的递增子序列

recursion - DrRacket - 找到最长的递增子序列

问题描述

我想创建用于查找 LIS 的代码。我的代码不能很好地工作。例如，如果输入是'(1 3 5 10 9 6 7)，输出应该是'(1 3 5 6 7)，但我的程序返回'(1 3 5 10)。我究竟做错了什么？我是否编写了二叉树然后找到更高的高度？或者我可以用最简单的方式编写这个程序吗？

(define (return_sequence N lst)
  (cond
    [(empty? lst) '()]
    [(< N (first lst)) (cons                           
                           (first lst)
                           (return_sequence (first lst) (rest lst))
                           )]
    [else (return_sequence N (rest lst))]
  )
)

(define (find_longest lst1 lst2)
  (cond
    [(empty? lst1) lst2]
    [(empty? lst2) lst1]
    [(< (length lst1) (length lst2)) lst2]
    [else lst1]
  )
)

(define (LIS lst) 
  (cond
    [(empty? lst) '()]
    [else (find_longest
           (cons
            (first lst)
            (return_sequence (first lst) (rest lst)))
           (LIS (rest lst))
          )]
  )
)

标签： recursionschemeracket

解决方案

在我们开始之前，一个问题。你认为'(1 1)是一个递增的序列吗？现在，我假设你没有。

首先，注意我们可以简化find-longest如下：

(define (find-longest lst1 lst2)
  (if (<= (length lst1)
          (length lst2))
      lst1
      lst2))

这是非常低效的，但我们暂时不用担心。它至少看起来比你的代码更干净。

我假设您正在尝试将其定义(return_sequence N lst)为最长的递增子序列，以lst使所述子序列的所有元素都大于N. 我建议你看看当你尝试时会发生什么(return_sequence 1 '(4 2 3))。我们应该期待结果是这样的'(2 3)，但事实就是如此'(4)。

你需要仔细考虑你想如何处理这种情况，(< N (first lst))并确保你没有犯一个愚蠢的错误（剧透——你犯了一个愚蠢的错误）。

编辑：假设(< N (first lst)). lst所有元素都大于N包含(first lst)或不包含的最长递增子序列。为了找到不存在的最长子序列，我们计算(return_sequence N (rest lst)). 为了找到最长的子序列，我们计算(cons (first lst) (return_sequence (first lst) (rest lst))。相关cond条款变为

[(< N (first lst)) (find_longest 
                      (cons (first lst) 
                            (return_sequence (first lst) (rest lst)))
                      (return_sequence N (rest lst)))]

这解决了你的问题。

另一方面，添加 的值非常有帮助，minus-infinity条件是该值始终小于任何其他值。在这种情况下，我们可以这样做

(define (LIS lst)
   (return_sequence minus-infinity lst))

这样做需要一点聪明，但这是可能的。

事实上，一种巧妙的相加方法minus_infinity是传入return_sequence的不是数字N，而是函数(lambda (x) (< N x))。然后，代替 line (< N (first list))，您将改为编写(less_than_N (first list)). 然后，您可以(define (minus_infinity x) #t).

也可以使用创建一个新符号gensym并拥有它minus_infinity。然后你会想做一些相当厚颜无耻的事情

(define minus_infinity (gensym))

(define (return_sequence N lst)
 (let ((< (lambda (a b) (or (equal? a minus_infinity) (< a b)))))
   cond ...)

(define (LIS lst)
  (return_sequence minus_infinity lst))

厚颜无耻的一点是我们没有(<)递归定义 -<发生在(lambda (a b) (or (equal? a minus_infinity) (< a b)))原始的<.

最后，你正在尝试的算法真的很慢。O(n log n)可以在where中解决这个问题n = (length lst)。您的解决方案将是指数级的，但改进它是非常重要的。

推荐阅读