1

好吧，我是一个 Scheme 新手，我现在正在阅读 SICP。我在网站上发现了一个问题。我花了 2 天时间考虑，但仍然不知道你们能帮忙吗？

以下问题：

计算机科学中的一项常见任务是在数据集中查找模式的实例。在这个问题中，您将编写一个过程（find-sublist space sublist），它按顺序返回空间中子列表的所有实例的开始索引的列表。请注意，子列表的实例可能会重叠，如给定 [ ] 的示例之一。如果空间包含列表，则无需像下面的示例 [ *] 中那样在空间的列表中查找子列表。您可以假设子列表不为空。

Examples:
(find-sublist '(7 1 2 3 4 1 2 1 2) '(1 2)) ; should return '(2 6 8)
(find-sublist '(“a” “b” “c” “b” “d”) '(“d”)) ; should return '(5)
(find-sublist '((1 2) (3 4) (5 . 6) 7 #f) '((3 4) (5 . 6))) ; should return '(2)
(find-sublist '(1 1 1 2 1) '(1 1)) ; [*] should return '(1 2)
(find-sublist '(9 1 2 3 (5 1 2 3) 1 2 3) '(1 2 3)) ; [**]should return '(2 6)
(find-sublist '() '(#t #f #f)) ; should return '()
4

2 回答 2

3

我会给你一些提示，让你自己找到答案，填空。第一步是将问题分成两部分，首先是一个判断是否sublst在 中的谓词，lst从 中的第一个位置开始lst：

(define (sublist? lst sublst)
  (cond (<???> <???>)  ; if sublst is empty return true
        ((and <???>    ; if lst is not empty and
              <???>)   ; the first element is equal in both lists
         (sublist? <???> <???>)) ; advance recursion over both lists
        (else <???>))) ; otherwise return false

现在是主程序：这个程序检查每个位置space是否有一个从那里开始的子列表（使用前面的程序）。如果是这样，构建一个列表作为元素传递当前索引。请注意，我们需要在一个额外的参数中跟踪当前索引：

(define (find-sublist space sublist)
  (let loop ((space space)            ; initialize iteration variables
             (idx 1))
    (cond (<???> <???>)               ; if space is empty return the empty list
          ; if the list starting at current position is the sublist
          ((sublist? space sublist) 
           (cons <???>                ; cons current index, advance recursion
                 (loop <???> <???>))) ; over the list and increment index
          (else                       ; otherwise just advance the recursion
           (loop <???> <???>)))))     ; same as before
于 2013-04-06T22:15:24.447 回答
0

你问自己一个问题：我的列表的第一个元素是否与模式匹配？如果是，记录索引。如果您解决了该问题，那么您将相同的逻辑应用于列表的其余部分。这是一个简单的解决方案。

(define (find-sublist list sub)
  (define (sublist? list sub)
    (or (null? sub)
        (and (not (null? list))
             (equal? (car sub) (car list))
             (sublist? (cdr list) (cdr sub)))))

  (let walking ((list list) (index 1) (indices '()))
    (if (null? list)
        (reverse indices)
        (walking (cdr list)
                 (+ 1 index)
                 (if (sublist? list sub)
                     (cons index indices)
                     indices)))))

这使用了一种称为“尾递归”的技术，使其在计算上等同于迭代。

于 2013-04-07T03:01:44.837 回答