LCS (самая длинная общая подпоследовательность) в схеме - PullRequest
Новая
       7

LCS (самая длинная общая подпоследовательность) в схеме

0 голосов
/ 01 июля 2018

Я пытаюсь использовать Scheme для реализации алгоритма LCS, но есть ошибка.

(определить X (список # \ A # \ B # \ C # \ B # \ D # \ A # \ B))

(определить Y (список # \ B # \ D # \ C # \ A # \ B # \ A))

(определить префикс (лямбда, я) (если (= i 0) «() (минусы (машины) (префикс (- i 1) (cdr s))))))

(определить (выбрать) (если (= ih 1) (машины) (выберите (- 1-й) (cdr s))))

(определить (LCS x y) (определите (оптимальный i j) (cond ((или (= i 0) (= j 0)) 0) ((eq? (выберите I x) (выберите j y)) (+ 1 (оптимальный (- я 1) (- j 1)))) (иначе (max (LCS (префикс (- i 1) x) y) (LCS x (префикс (- j 1) y)))))) (оптимальный (длина х) (длина у)))

1] => (загрузить "lcs.scm")

; Загрузка "lcs.scm" ... сделано ; Значение: lcs

1] => (lcs X Y)

; Значение: 5

Результат должен быть 4, я не знаю, где ошибка.

1 Ответ

0 голосов
/ 01 июля 2018

Вы получаете ошибку, потому что ваш последний рекурсивный вызов в оптимальном является неправильным. Вы берете префикс i-1 для x или j-1 для y, но как насчет другого? 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)))
...