scheme - MIT スキームの中央値手順

Question

list-ref を使用せずに、リストの中央値を見つける手順をどのように定義しますか? たとえば、(median '(1 2 2))2 を(median '(1 2 3 4 5 6))返し、3.5 を返します。ソートされた整数のリストであると想定できます。

これは宿題の質問なので、実際のコードを投稿しないでください。私が探しているのは、私を正しい方向に導くためのヒントまたは疑似コードだけです。タイトルで述べたように、私は MIT スキームを使用しています。前もって感謝します。

Answer 1

亀とうさぎのアルゴリズムの使い方を知っていますか？もしそうなら、あなたのアルゴリズムが完了した後、あなたのカメはリストの真ん中になります。

あなたが本当に立ち往生しているなら、私は実用的な実装を持っています。または、ここにいくつかの擬似コードのようなものがあります：

(define (median lst)
  (if (null? lst) #f                         ;; oops, empty list
      (let loop ((tortoise <???>)
                 (hare <???>))
        (cond ((eq? tortoise hare) #f)       ;; oops, circular list
              ((null? hare) <???>)           ;; median value here
              ((null? (cdr hare)) <???>)     ;; average of middle two elements
              (else (loop <???> <???>))))))  ;; keep going

Answer 2

中央値がリストの中央の 2 つの要素の平均である場合、list-ref の使用は非効率的です。その理由は、リストの前半を 2 回スキップして、中間の 2 つの要素を見つけるためです。

1 つの解決策は、リストの最初の要素(drop-list a-list n)を削除するヘルパー関数を作成することです。n例えば(drop-list '(a b c d e) 2)です'(c d e)。you を使用drop-listして、次のことができるようになりました。

1. リストの長さを見つける
2. 長さが奇数の場合、list-ref を使用して中央の要素を選択します
3. 長さが偶数の場合は、drop-list を使用して中央の 2 つの要素の前にある要素を削除し、結果の最初の 2 つの要素の平均を計算します。