1

私はSchemeの初心者で、今SICPを読んでいます.ウェブサイトで質問を見つけました.2日かけて考えましたが、それでも助けてもらえませんか?

次の質問:

コンピューター サイエンスの一般的なタスクは、データ セット内のパターンのインスタンスを見つけることです。この問題では、空間内のサブリストのすべてのインスタンスの先頭のインデックスのリストを順番に返す手順 (find-sublist space sublist) を記述します。[ ]の例のように、サブリストのインスタンスが重複する場合があることに注意してください。スペースにリストが含まれている場合、以下の例の 1 つにあるように、スペース内のリストでサブリストを見つける必要はありません [ *]。サブリストは空ではないと想定できます。

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

空欄を埋めて、自分で答えを見つけるためのヒントをいくつか教えます。最初のステップは、問題を 2 つに分割することです。まず、 が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 に答える