0

MITスキームを扱うプログラミングコースの模擬試験を受けています。質問の1つは尋ねます：

「リスト ls を返す手順 (インオーダー ls) を完了します。ただし、ls の前の値よりも厳密に大きくない最初の値の直前で停止することを除きます。つまり、インオーダーは、ls の次の部分を返す必要があります。厳密に昇順でソートされた先頭. ls には負でない整数のみが含まれていると仮定します."

次に、質問にいくつかの例を示します。

(in-order '(1 2 3 4)) ; should return (1 2 3 4)
(in-order '(1 2 3 3 4 5)) ; should return (1 2 3)
(in-order '(3 2)) ; should return (3)
(in-order '(3)) ; should return (3)

これは私の解決策です：

(define (in-order ls)
  (cond ((null? ls) ls)
        ((< (car ls) (cadr ls)) 
         (cons (car ls) (cons (in-order (cdr ls)) ())))
        ((>= (car ls) (cadr ls)) (car ls))
        (else "Nothing")))

2 番目と 3 番目の例ではほとんど問題なく動作しますが、1 番目と 4 番目の例では完全に失敗します。引数の一部として null を渡そうとし続けることは知っていますが、これを回避する方法がわかりません。それ以外に、私が間違っていることは他にありますか？

4

1 に答える 1

2

これでそこに着きます：

(define (in-order ls)
  (if (null? ls)
      '()
      (let looking ((result (list (car ls))) (ls (cdr ls)))
        (if (or (null? ls) (not (< (car result) (car ls))))
            (reverse result)
            (looking (cons (car ls) result)
                     (cdr ls))))))

末尾再帰lookingは、結果の として常に最後の値を持ちますcar。したがって、停止の比較は次のようになります(not (< (car result) (car ls)))

あなたのコードで(cons (in-order ...) ())は、ほぼ確実に間違っています。述語(< (car ls) (cadr ls))は次のような場合に失敗します-それを回避するには、'(3)次のようなものが必要です。(null? (cdr ls))

あなたのような非末尾再帰アルゴリズムでは、次のようになります。

(define (in-order ls)
  (cond ((or (null? ls) (null? (cdr ls))) ls)     ; nothing left
        ((< (car ls) (cadr ls))                   ; extend and continue
         (cons (car ls) (in-order (cdr ls))))
        (else (list (car ls)))))                  ; last one
于 2013-04-14T17:23:57.610 に答える