Scheme中的LCS(longest common subsequence)

Question

我尝试用Scheme实现LCS算法，但是有一个bug

（定义 X (列表#\A#\B#\C#\B#\D#\A#\B))

(定义Y (列表#\B#\D#\C#\A#\B#\A))

(定义前缀（拉姆达（我是）（如果（=我0） '() （缺点（汽车）（前缀 (- i 1) (cdr s))))))

(定义(选择第一个) （如果（= 第 1 个）（汽车）（选择（- 第 1 个） (cdr s))))

（定义（LCS x y）（定义（最优 i j） (条件 ((或 (= i 0) (= j 0)) 0) ((eq? (选 i x) （选择 j y）） (+ 1 （最优 (- i 1) (-j 1)))) (else (max (LCS (prefix (- i 1) x) y) (LCS x (前缀 (- j 1) y)))))) （最佳（长度 x） (长度y)))

1 ]=> (load "lcs.scm")

;Loading "lcs.scm"... done ;Value: lcs

1 ]=> (lcs X Y)

;Value: 5

结果应该是4，不知道bug在哪里

Answer 1

您收到此错误是因为您在最优中的最终递归调用不正确。您正在为 x 使用前缀 i-1 或为 y 使用 j-1 但另一个呢？ j 和 i 可能小于各自字符串的长度，因此，您需要相应地为参数添加前缀。

以下代码可以正常工作。

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (LCS (prefix (- i 1) x) (prefix j y)) (LCS (prefix i x) (prefix (- j 1) y))))))
  (optimal (length x) (length y)))

请注意，此问题的存在只是因为您混合了两种不同类型的调用。一个在前缀上调用 LCS，另一个在前缀上调用 optimal，i 和 j 较小。您可以将 LCS 调用替换为最佳解决方案以获得更简单的解决方案。

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (optimal (- i 1) j) (optimal i (- j 1))))))
  (optimal (length x) (length y)))

Scheme中的LCS(longest common subsequence)

LCS(longest common subsequence) in Scheme

scheme

lcs